Pattern visualizer

Rotting Oranges

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. 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?.

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

time O(rows * cols)space O(rows * cols)step 1 / 11

6 fresh, 1 already rotten, 2 empty

0,0

0,1

0,2

1,0

1,1

2,1

2,2

line 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.

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

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap