DSA Tracker

Visualize

Rotting Oranges

Multi-source BFS: every rotten orange spreads at once, one level per minute

time O(rows * cols)space O(rows * cols)

Treat EVERY already-rotten orange as a BFS source at the same time, not one BFS per orange — that is what makes 'minutes' line up with BFS levels: draining one full level of the queue is exactly one minute passing, because every cell on that level rotted simultaneously. Empty cells are not nodes at all here, since rot can never cross them; a fresh orange the graph below can never reach is exactly the case that forces the answer to -1.

Details

Animated on: grid = [[2,1,1],[1,1,0],[0,1,1]] (0 empty, 1 fresh, 2 rotten) — how many minutes until no fresh orange remains, or -1 if some can never be reached?

Problem:Rotting OrangesMedium

Pattern:Graph BFS and DFS

Multi-source BFS: every rotten orange spreads at once, one level per minute

step 1 / 11

6 fresh, 1 already rotten, 2 empty

A 3x3 grid: 6 fresh oranges, 1 already rotten (0,0), and 2 empty cells that block the rot completely — they never become nodes in this picture at all.

Pseudocode
1FUNCTION orangesRotting(grid):
2  queue <- EVERY (r, c) WHERE grid[r][c] = 2
3  fresh <- COUNT (r, c) WHERE grid[r][c] = 1
4  minutes <- 0
5  WHILE queue NOT EMPTY AND fresh > 0
6    REPEAT LENGTH(queue) TIMES
7      (r, c) <- REMOVE FIRST FROM queue
8      FOR EACH (nr, nc) IN NEIGHBORS(r, c)
9        IF grid[nr][nc] = 1
10          grid[nr][nc] <- 2
11          fresh <- fresh - 1
12          APPEND (nr, nc) TO queue
13    minutes <- minutes + 1
14  RETURN fresh = 0 ? minutes : -1

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. A 3x3 grid: 6 fresh oranges, 1 already rotten (0,0), and 2 empty cells that block the rot completely — they never become nodes in this picture at all.
  2. Every already-rotten orange is a source at once — this is multi-source BFS, not one BFS per orange. Queue 0,0 together and count 6 fresh oranges that still need reaching.
  3. Cell 0,0 spreads rot to its fresh neighbors THIS SAME MINUTE — that simultaneity, not one-at-a-time spreading, is why the level size is captured before the loop starts.
  4. 1,0 and 0,1 caught the rot this minute, dropping fresh to 4. 1,0, 0,1 carry the rot into minute 2.
  5. Cells 1,0, 0,1 all spread rot to their fresh neighbors THIS SAME MINUTE — that simultaneity, not one-at-a-time spreading, is why the level size is captured before the loop starts.
  6. 1,1 and 0,2 caught the rot this minute, dropping fresh to 2. 1,1, 0,2 carry the rot into minute 3.
  7. Cells 1,1, 0,2 all spread rot to their fresh neighbors THIS SAME MINUTE — that simultaneity, not one-at-a-time spreading, is why the level size is captured before the loop starts.
  8. 2,1 caught the rot this minute, dropping fresh to 1. 2,1 carries the rot into minute 4.
  9. Cell 2,1 spreads rot to its fresh neighbors THIS SAME MINUTE — that simultaneity, not one-at-a-time spreading, is why the level size is captured before the loop starts.
  10. 2,2 caught the rot this minute, dropping fresh to 0. None remain — the grid is fully rotten.
  11. The queue only ran out once every fresh orange was gone, so RETURN 4.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Rotting Oranges in the editorAll Graph problemsBack to roadmap