Start learning free

LESSON 471 OF 535 · GRAPHS

Rotting Oranges in C++: Multi-Source BFS in O(m * n)

Practice O(m · n) Read the full explanation

You are given a grid grid with m rows and n columns: a vector of rows, where each row is a vector of integers. Rows are numbered from 0, top to bottom, and columns from 0, left to right. Every cell holds one of three values:

  • 0: an empty cell,
  • 1: a fresh orange,
  • 2: a rotten orange.

Every minute, each fresh orange that is next to a rotten orange (up, down, left or right, not diagonally) becomes rotten.

Return the number of minutes that pass until no cell holds a fresh orange. If some orange can never rot, return -1.

 

Example 1:

Input: grid = [
  [2, 1, 1],
  [1, 1, 0],
  [0, 1, 1]
]
Output: 4
Explanation: The grid after each minute:
  start      minute 1   minute 2   minute 3   minute 4
  2 1 1      2 2 1      2 2 2      2 2 2      2 2 2
  1 1 0      2 1 0      2 2 0      2 2 0      2 2 0
  0 1 1      0 1 1      0 1 1      0 2 1      0 2 2
In minute 1 the two oranges next to the rotten one in the corner rot; in each later minute the
oranges next to those rot in turn. After minute 4 no orange is fresh.

Example 2:

Input: grid = [
  [2, 1, 1],
  [0, 1, 1],
  [1, 0, 1]
]
Output: -1
Explanation: The orange in the bottom left corner, [2, 0], has an empty cell above it and to
its right. Rot doesn't spread diagonally, so nothing ever reaches it: it stays fresh forever.

Example 3:

Input: grid = [[0, 2]]
Output: 0
Explanation: No orange is fresh at the start, so no minute has to pass.

 

Constraints:

  • 1 <= m, n <= 300
  • Every row has n values.
  • Every grid[r][c] is 0, 1 or 2.

Note:

Your algorithm should run in O(m · n) time and use O(m · n) extra space.

Simulating the grid minute by minute, with a scan of every cell in each minute, can cost O((m · n)2): think of a long winding line of oranges that the rot creeps along one cell per minute. The tutorial uses a BFS that starts from all the rotten oranges at once, as the BFS in 01 Matrix starts from all the zeros, and goes through it level by level: the oranges that rot in minute 1 are the first level, the oranges they rot are the second level, and so on, so the number of levels is the number of minutes. A count of the fresh oranges, lowered each time one rots, tells at the end whether some orange never rotted. Each cell joins the queue at most once.

STEP 1 OF 22
    Ctrl + Enter to check

    C++ · GRAPHS

    Rotting Oranges in C++, explained

    Problem overview

    The function orangesRotting receives a grid as a vector<vector<int>>. Each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange that is directly next to a rotten one, up, down, left or right, becomes rotten. The function returns how many minutes pass until no fresh orange is left, or -1 if some orange can never rot.

    For the grid {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}} the answer is 4. In minute 1 the two neighbours of the corner orange rot, and in each later minute the neighbours of the newly rotten oranges rot. For {{2, 1, 1}, {0, 1, 1}, {1, 0, 1}} the answer is -1: the orange at the bottom left has an empty cell above and to its right, and rot does not spread diagonally. For {{0, 2}} the answer is 0, because nothing is fresh at the start.

    Approach: spread the rot level by level

    The simple simulation scans the whole grid every minute and rots the neighbours of each rotten orange. A long winding line of oranges makes that slow: the rot creeps one cell per minute, so there can be about m * n minutes, each costing a scan of m * n cells. The statement asks for O(m * n).

    The fix is a breadth-first search (BFS) that starts from all the rotten oranges at once. The oranges that are rotten at minute 0 form the first level. The fresh oranges they rot in minute 1 form the second level, the ones those rot in minute 2 form the third, and so on. The number of minutes is the number of levels that rot something. A queue handles this: oranges leave in the order they rotted, so one minute's oranges come out before the ones they rot.

    A counter fresh tracks the oranges that are still fresh. When it reaches 0, the search stops. If the queue empties while fresh is still above 0, no chain of oranges links the rest to a rotten one, so they never rot and the answer is -1.

    For the first example, the grid after the search is all rotten except the empty cells:

    2 2 2
2 2 0
0 2 2

    For the second example the search stops with the bottom-left orange still fresh:

    2 2 2
0 2 2
1 0 2

    Step by step

    1. Store the grid's size in rows (grid.size()) and cols (grid[0].size()). Every row has the same length, so the first row gives the number of columns.
    2. Create the queue q of pair<int, int> values, (row, column) pairs. It holds the rotten oranges that are about to spread the rot. It is named q because queue is the name of the type.
    3. Create fresh, an int starting at 0, to count the fresh oranges.
    4. Scan the whole grid with nested loops over r and c. One pass finds the oranges that start rotten and counts the fresh ones.
    5. Push every cell equal to 2 onto q with q.push({r, c}). All the starting rotten oranges spread the rot in the first minute, so they all go in before the search begins.
    6. Count every cell equal to 1 with fresh++. Empty cells are neither.
    7. List the four moves in directions, a vector<pair<int, int>> of (row change, column change) pairs. Each changes only the row or only the column, so diagonal oranges are not neighbours.
    8. Create minutes, starting at 0. If nothing is fresh at the start, 0 is the answer.
    9. Loop while !q.empty() && fresh > 0. Each turn is one minute. Without fresh > 0 the loop would count an extra minute after the last orange rots, while the last rotten oranges look for fresh neighbours that no longer exist.
    10. Add 1 to minutes and save q.size() in levelSize. These are the oranges that spread the rot in this minute. Oranges that rot during the minute join the same queue but only spread in the next one, so the minute handles exactly levelSize oranges.
    11. Loop levelSize times. One pass of this loop handles one BFS level.
    12. Take the front orange with auto [row, col] = q.front() and remove it with q.pop(). pop returns nothing, so the front is read first.
    13. Try each direction and compute nextRow and nextCol.
    14. Check the neighbour: it must be inside the grid and hold a fresh orange. The bounds come first in the condition, so the grid is read only for cells that exist.
    15. Rot it: set it to 2 right away, subtract 1 from fresh and push it onto q. Marking it at once means no other orange rots it again or queues it a second time.
    16. After the loop, return -1 if fresh is still above 0, and minutes otherwise.

    The solution in C++

    class Solution {
public:
    int orangesRotting(vector<vector<int>> &grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        queue<pair<int, int>> q;
        int fresh = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) {
                    q.push({r, c});
                }
                if (grid[r][c] == 1) {
                    fresh++;
                }
            }
        }
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int minutes = 0;
        while (!q.empty() && fresh > 0) {
            minutes++;
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                auto [row, col] = q.front();
                q.pop();
                for (auto [dr, dc] : directions) {
                    int nextRow = row + dr;
                    int nextCol = col + dc;
                    if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && grid[nextRow][nextCol] == 1) {
                        grid[nextRow][nextCol] = 2;
                        fresh--;
                        q.push({nextRow, nextCol});
                    }
                }
            }
        }
        if (fresh > 0) {
            return -1;
        }
        return minutes;
    }
};

    The C++ details worth a closer look:

    • Structured bindings. auto [row, col] = q.front() names the two members of the pair, a C++17 feature. It copies the pair, which matters because q.pop() destroys the queue's element right after. A reference taken from front() would dangle after the pop.
    • Brace initialization. q.push({r, c}) builds the pair<int, int> in place. The same braces fill directions with four pairs.
    • &grid. The grid is passed by reference, so orangesRotting changes the caller's grid: the oranges that rotted are 2 afterwards. The result does not need the original, but a caller that does should pass a copy.
    • int levelSize = q.size(). The size is saved before the inner loop, because q.size() changes as oranges are pushed during the minute.
    • && short-circuits. When nextRow is -1, the rest of the condition is not evaluated, so grid[-1] is never read. Reading outside a vector is undefined behaviour in C++, not an exception.

    Complexity

    Let the grid have m rows and n columns.

    Time: O(m * n). The first scan visits every cell. In the search, each cell joins the queue at most once, because it is marked rotten when it joins, and each cell looks at 4 neighbours.

    Space: O(m * n). In the worst case, such as a grid of all rotten oranges, the queue holds every cell.

    Edge cases and common mistakes

    • No fresh oranges. {{0, 2}}, {{0}} and {{2, 2}, {2, 2}} all return 0,.
    • No rotten oranges. {{1}} returns -1: the queue is empty, so the loop never runs, and fresh is still 1.
    • Fresh oranges cut off by empty cells. {{2, 0, 1}} returns -1, because the empty cell between them stops the spread.
    • An off-by-one in the minutes. {{2, 1, 1, 1, 1}} returns 4: four fresh oranges in a row, one per minute. Without the fresh > 0 condition the loop would run one more turn and count 5.
    • Marking the orange when it leaves the queue. It should be marked when it joins. Otherwise several neighbours can queue the same orange, and fresh is reduced more than once for it.
    • Diagonal spreading. The four moves are the only ones. Adding diagonals would let the bottom-left orange of the second example rot through the orange at its upper right, which is not what the rules say.
    • Not using the level size. Popping one orange per minute instead of a whole level counts a minute per orange.

    Testing

    • {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}} gives 4.
    • {{2, 1, 1}, {0, 1, 1}, {1, 0, 1}} gives -1.
    • {{0, 2}} gives 0.
    • {{1}} gives -1.
    • {{2, 1, 1, 1, 1}} gives 4.
    • {{2, 0, 1}} gives -1.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free