Multi-Source BFS Solution to Rotting Oranges

Problem Summary

You’re given an m x n grid where each cell is empty (0), fresh (1), or rotten (2). Every minute, each fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. The goal is to compute the minimum number of minutes required until no fresh orange remains. If any fresh orange can never be reached by rot, return -1.

Constraints are small but realistic for grid BFS. Grid dimensions satisfy m, n in [1, 10], and grid values are limited to 0, 1, or 2.

This is a classic propagation problem where multiple sources spread simultaneously. That “simultaneous” keyword is the hint.

My Approach

Breadth-first search from all initially rotten oranges at once solves the problem cleanly. The technique is called multi-source BFS. Instead of picking one rotten orange and expanding, we put all rotten oranges into the queue on day zero. Then we run BFS level by level, where each level corresponds to one minute passing. Any fresh neighbor of a rotten orange becomes rotten and is enqueued for the next minute.

There are two common ways to track minutes.

• Maintain a “time” matrix storing the minute each cell becomes rotten. The time for a neighbor is the parent’s time plus one.
• Or track BFS levels explicitly with queue size or by pushing (cell, time) pairs.

The provided code uses the first option. It keeps a dp matrix of the same shape as the grid. dp[x][y] is the minute at which cell (x, y) rots. Initially rotten cells have time 0. Each time we rot a neighbor, we set its time to the current cell’s time plus one.

At the end, we scan the grid. If any fresh orange remains, answer is -1. Otherwise the answer is the maximum value stored in dp for cells that are rotten, which is when the last orange turned rotten.

This approach handles simultaneity automatically because BFS processes all nodes at distance d before touching nodes at distance d+1.

Why This Works

The process is equivalent to finding the shortest time (in minutes) from any initial rotten orange to each fresh orange, where moving to a neighbor costs 1 minute and you can move in four directions. Multi-source BFS computes minimum distances from a set of starting points to every reachable cell. That’s exactly what we need.

• If a fresh orange is unreachable from any initial rotten orange, BFS never marks it and the final scan finds a 1. Returning -1 is correct because the rot cannot cross empty space diagonally or jump across gaps.
• If a fresh orange is reachable, the first time BFS visits it is along a shortest path. The dp value for that cell is the earliest minute it rots. The maximum such value over the grid is the time when the last reachable fresh orange turns rotten.
• Simultaneity is baked in. All oranges at minute t infect their neighbors, which are assigned to minute t+1. No neighbor can be marked for a later minute if an earlier infection path exists, because BFS always visits nodes in nondecreasing distance order.

Because each cell is visited at most once and we only consider four neighbors per visit, the runtime is linear in the number of cells.

Code Walkthrough

Below is the C++ solution using multi-source BFS and a time matrix.

C++
Copy
1
class Solution {
2
public:
3
    
4
    int orangesRotting(vector<vector<int>>& grid) {
5
        // Get the dimensions of the grid
6
        const int m = (int)grid.size(), n = (int)grid[0].size();
7
        // Initialize a dp grid to track the minutes taken for each orange to rot
8
        vector<vector<int>> dp(m, vector<int>(n, 0));
9
        // Queue to perform BFS on rotten oranges
10
        queue<pair<int,int>> q;
11
        // Fill the queue with initial rotten oranges' coordinates
12
        for (int i = 0; i < m; ++i) {
13
            for (int j = 0; j < n; ++j) {
14
                if (grid[i][j] == 2) q.push({i, j});
15
            }
16
        }   
17
18
        // Directions array for 4-directional movement
19
        int dx[4] = {1,-1,0,0};
20
        int dy[4] = {0,0,1,-1};
21
22
        // Perform BFS to rot fresh oranges
23
        while(!q.empty()) {
24
            int size = q.size();
25
            for (int i = 0; i < size; ++i) {
26
                // Get the current rotten orange's position
27
                auto p = q.front();
28
                q.pop();
29
                int x = p.first, y = p.second;
30
                // Check all four possible directions
31
                for (int j = 0; j < 4; ++j) {
32
                    int nx = x + dx[j], ny = y + dy[j];
33
                    // Continue if the next position is out of bounds or not a fresh orange
34
                    if (nx < 0 || ny < 0 || nx >= m || ny >= n || grid[nx][ny] != 1) continue;
35
                    // Rot the fresh orange
36
                    grid[nx][ny] = 2;
37
                    // Update dp with the time taken to rot this orange
38
                    dp[nx][ny] = dp[x][y] + 1;
39
                    // Push the newly rotted orange's position into the queue
40
                    q.push({nx,ny});
41
                }
42
            }
43
        }
44
45
        // Calculate the maximum time of rotting and check for fresh oranges
46
        int ans = 0;
47
        for (int i = 0; i < m; ++i) {
48
            for (int j = 0; j < n; ++j) {
49
                if (grid[i][j] == 2) {
50
                    ans = max(ans, dp[i][j]); // Update ans with the max time
51
                } else if (grid[i][j] == 1) return -1; // Found a fresh orange, impossible to rot all
52
            }
53
        }
54
55
        // Return the maximum time taken to rot all oranges
56
        return ans;
57
    }
58
};

Walkthrough of the main parts.

• Initialization. We read the grid dimensions and create dp with zeros. dp will store when each cell turned rotten. We then enqueue coordinates of all initially rotten oranges. This forms the set of BFS sources.

• BFS loop. We repeatedly pop a cell (x, y) and try to infect its four neighbors. For any neighbor that is a fresh orange (value 1), we flip it to rotten (set to 2), record its infection minute dp[nx][ny] = dp[x][y] + 1, and enqueue it.

• Visited marking. The grid itself is used as the visited set. As soon as a fresh orange becomes rotten, we mark it to 2 to avoid adding it again. That keeps each cell from being processed more than once.

• Answer computation. After BFS finishes, two possibilities remain. If there is any fresh orange left in the grid, then it was unreachable, so return -1. Otherwise the answer is the maximum dp value over all rotten cells, which is the time when the last orange got infected.

Complexity is straightforward. Each cell enters the queue at most once and we inspect at most four neighbors, so O(mn) time. The dp matrix and the queue can hold O(mn) elements, so O(m*n) space.

A small observation about the code. It uses a level loop with size but it doesn’t rely on it to compute time, since time is carried by dp from parents. You could remove the size-based outer loop and the behavior wouldn’t change, because dp enforces correct minutes. Or you could drop dp and use that size-based loop to maintain a minute counter per layer. Both are valid.

Alternative Approaches

There are a few other ways to implement or reason about this problem. The BFS above is the standard tool because it ensures minimal time spread from multiple sources. Here’s how the suggested alternatives compare and when you might use them.

• DFS with state tracking. You could try to recursively spread from each rotten orange and compute infection times. The challenge is that DFS does not naturally compute shortest paths in unweighted grids. You’d need memoization of best time per cell and careful pruning to avoid revisiting with worse times. Even then, managing interleaving infections from different sources becomes messy. I wouldn’t pick this for production or interview use. It’s useful as a thought exercise to see why BFS is the right fit.

• Dynamic programming after BFS. If the idea is to do a DP pass independent of BFS to compute distances, that’s hard to get right because the infection front expands from multiple points and obstacles shape the frontier in complex ways. Two-pass DP tricks work on Manhattan-distance-like metrics without obstacles, but here you need actual shortest-path computation. A single multi-source BFS already gives the DP you want. If you do want a DP array of times, fill it during BFS as the solution does.

• Simulation with a queue per minute. One could simulate minute by minute by scanning the entire grid, collecting all new infections for the next minute, and repeating. This works and is simple to write. The downside is that you end up scanning the full grid each minute, even if only a few cells change, so it can do more work than BFS. On these small constraints it still passes. On larger grids, BFS with a single work queue of changing cells is more efficient.

Two practical variants of the BFS worth mentioning.

• Level-based time tracking. Keep an integer minutes that increments after processing one BFS level, measured by queue size. Avoid the dp matrix entirely and return minutes at the end. This needs careful handling of the off-by-one when there are no changes.

• Queue of (cell, time). Push {x, y, t} and track max t while visiting neighbors. This is easy to read, and you also avoid dp. Mark visited in the grid to prevent reprocessing.

Pitfalls and Edge Cases

Small logical slips cause wrong answers here. A checklist helps.

• Not starting from all rotten oranges. If you seed the queue with only one source, you’ll overcount minutes for oranges that could have been infected earlier by another initial rotten.

• Failing to mark visited immediately. If you enqueue a fresh neighbor without turning it rotten or otherwise marking it visited, it could be enqueued multiple times in the same minute or from different parents. That leads to redundant work or incorrect times.

• Wrong minute counting. There are two consistent patterns. Use dp[parent] + 1 or use BFS levels to increment minutes after finishing a layer. Mixing them or incrementing both can cause off-by-one errors.

• Early return of 0 in all cases with no initial rotten. If there are fresh oranges and no rotten oranges, the answer should be -1 since nothing can start the infection. Only return 0 when there are no fresh oranges at all.

• Assuming diagonal infection. Infection is strictly up, down, left, right. Diagonals don’t count.

• Mutating the grid when you still need original values. In this solution, we intentionally mutate grid to mark visited. If a separate pass relied on original fresh locations, you’d need a copy or a different visited structure. Here it’s safe.

• Ignoring empty cells. Zeros are not barriers to movement by themselves, but they are empty, not oranges. Infection only propagates to fresh oranges, and you still must respect bounds.

Useful edge cases to test.

• All zeros. Answer is 0 because there are no fresh oranges to rot.
• No rotten oranges but at least one fresh orange. Answer is -1.
• Already fully rotten. Answer is 0.
• A fresh orange surrounded by zeros with no adjacent rotten. Answer is -1.
• Multiple initial rotten sources each infecting different regions. The maximum dp should reflect the farthest region’s time.

Further Thinking

If you want more practice on similar patterns, here are problems that exercise multi-source BFS, shortest paths on grids, or propagation timing. Each includes a hint for the approach.

• 01 Matrix. Given a binary matrix, compute the distance to the nearest zero for each cell. Use multi-source BFS starting from all zeros and expand outward.

• Walls and Gates. Fill each empty room with the distance to its nearest gate. Same technique, enqueue all gates first and BFS to fill distances.

• As Far from Land as Possible. Given a grid of water and land, find the water cell farthest from any land. Enqueue all land cells and BFS; the last popped water cell’s distance is the answer.

• Shortest Path in Binary Matrix. Move in eight directions through zeros to reach the bottom-right from top-left. Standard single-source BFS for shortest path length.

• Minimum Time to Infect Binary Tree. Starting from a target node, infection spreads to parent and children each minute. BFS over the implicit undirected graph after mapping parent pointers.

• Spread of Fire or Gas in a Grid. Fire starts at multiple cells and spreads each minute, and you try to escape. Solve two BFS passes, one for fire times and one for your movement while respecting fire arrival times.

• Knight’s Minimum Moves on a Chessboard. Compute the minimum knight moves between two squares. BFS on the grid with knight moves as edges.

• Multi-source Dijkstra for weighted grids. If moving to neighbors had varying costs instead of uniform 1, swap BFS with Dijkstra starting from all sources at cost zero.

The common thread is modeling state as nodes in a graph and using BFS to capture the earliest time or minimum number of steps. Once you recognize that structure, these problems become much more mechanical to solve.

Example 1

• input: grid = [[2,1,1],[1,1,0],[0,1,1]]
• output: 4

<strong class="

Example 2

• input: grid = [[2,1,1],[0,1,1],[1,0,1]]
• output: -1
• explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

<strong class="

Example 3

• input: grid = [[0,2]]
• output: 0
• explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.