On this page
Description
Rotten oranges infect their fresh neighbors every minute. How long until all are rotten? Or: how far is every grid cell from its nearest 0? Both have many starting points spreading at the same speed. A BFS from each source repeats work. One BFS that starts from all of them at once does it directly: put every source in the queue before the first step.
We'll go from simple to more technical:
- The pattern: Rotting Oranges, with every source at minute 0 and one layer per minute.
- A second flavor: distance from every cell to its nearest source.
- Where it shows up (nearest facility, flood fill, spread simulations, game distance maps).
- What breaks it: one source at a time, marking on dequeue, an empty extra layer, unreachable cells.
The approach
Put every source in the queue at minute 0, then process the queue one layer at a time. Each layer is one minute. Here is a 3 x 3 grid with rotten oranges in two opposite corners and fresh ones everywhere else:
| Minute | Newly rotten | Fresh left |
|---|---|---|
| 0 | the two corners, (0, 0) and (2, 2) | 7 |
| 1 | (0, 1), (1, 0), (1, 2), (2, 1) | 3 |
| 2 | (0, 2), (1, 1), (2, 0) | 0 |
The answer is 2; from (0, 0) alone it would take 4.
Java
int orangesRotting(int[][] grid) {
int rows = grid.length, cols = grid[0].length, fresh = 0;
ArrayDeque<int[]> queue = new ArrayDeque<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) queue.add(new int[]{r, c}); // every rotten orange starts at minute 0
else if (grid[r][c] == 1) fresh++;
}
}
int minutes = 0;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!queue.isEmpty() && fresh > 0) { // stop once nothing is left to rot
for (int size = queue.size(); size > 0; size--) { // one layer = one minute
int[] cell = queue.poll();
for (int[] d : dirs) {
int r = cell[0] + d[0], c = cell[1] + d[1];
if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 1) {
grid[r][c] = 2; // mark when enqueued, not when dequeued
fresh--;
queue.add(new int[]{r, c});
}
}
}
minutes++;
}
return fresh == 0 ? minutes : -1;
}
Python
from collections import deque
def oranges_rotting(grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
queue = deque() # deque: popleft is O(1); list.pop(0) is O(n)
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c)) # every rotten orange starts at minute 0
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while queue and fresh > 0: # stop once nothing is left to rot
for _ in range(len(queue)): # one layer = one minute
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2 # mark when enqueued, not when dequeued
fresh -= 1
queue.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1
The condition fresh > 0 stops before an extra, empty layer. Without it, the last wave runs one more round that rots nothing and adds a minute. Counting fresh oranges up front also covers the edge cases: none means 0 minutes, and any never reached means -1.
A second flavor: distance to the nearest source
For the distance from every cell to its nearest 0, every 0 is a source at distance 0. The first time BFS reaches a cell gives its distance:
Java
int[][] updateMatrix(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
int[][] dist = new int[rows][cols];
ArrayDeque<int[]> queue = new ArrayDeque<>();
for (int i = 0; i < rows; i++) {
Arrays.fill(dist[i], -1);
for (int j = 0; j < cols; j++) if (grid[i][j] == 0) { dist[i][j] = 0; queue.add(new int[]{i, j}); }
}
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int r = cell[0] + d[0], c = cell[1] + d[1];
if (r >= 0 && r < rows && c >= 0 && c < cols && dist[r][c] == -1) {
dist[r][c] = dist[cell[0]][cell[1]] + 1;
queue.add(new int[]{r, c});
}
}
}
return dist;
}
Python
from collections import deque
def update_matrix(grid: list[list[int]]) -> list[list[int]]:
rows, cols = len(grid), len(grid[0])
dist = [[-1] * cols for _ in range(rows)]
queue = deque()
for i in range(rows):
for j in range(cols):
if grid[i][j] == 0:
dist[i][j] = 0
queue.append((i, j))
while queue:
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return dist
Searching outward from each 1 is O(cells^2) in the worst case. Seeding from the 0s visits each cell once. It's ordinary BFS from an imaginary "super source" joined to every 0.
Where you'll see it
The distance from every location to the nearest hospital or warehouse, spread simulations from several seeds, and game distance maps are multi-source BFS. Weighted versions start Dijkstra with every source at 0.
Which tool for which job?
| You need | Use |
|---|---|
| Time for several sources to spread everywhere | multi-source BFS, layer by layer |
| Distance to the nearest source for every cell | multi-source BFS seeded with all sources |
| Which source is nearest to each cell | carry the source's label with each cell |
| Sources that start at different times, or weighted edges | Dijkstra seeded with each start time |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| A BFS per source | 100 sources on 200 x 200 visit 4,000,000 cells | one BFS seeded with all of them |
| Marking on dequeue | 179,401 enqueues instead of 90,000 on a 300 x 300 grid | mark when enqueuing |
| Counting the last empty layer | one minute too many | stop when nothing is left to reach |
| Ignoring unreachable cells | a walled-off orange reports a time | check what's left, return -1 |
| Seeding sources with different start times at 0 | the wrong burn times | Dijkstra with each start time |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why put every source in the queue before the first step?
Show answer
So all sources spread in lockstep. A cell's first visit then comes from its nearest source, and each layer is one unit of time for all of them.
2. Why mark a cell when it's enqueued rather than when it's dequeued?
Show answer
Several neighbors can reach the same cell in one layer. Marking on dequeue lets duplicates into the queue and can decrement the fresh count twice.
3. What does Rotting Oranges return for a grid with no fresh oranges, and for one where a fresh orange is walled off?
Show answer
0, since nothing needs to rot. -1, since the BFS ends with a fresh orange that can never rot.
Key takeaways
- Seed every source at distance 0 and run one BFS - O(cells) for any number of sources.
- A layer is one unit of time; stop when nothing is left to reach.
- Mark on enqueue.
- Distance to the nearest 0: seed the 0s, not the 1s.