LeetCode 994 · Medium · Graphs

Rotting Oranges

Each cell of a grid is empty (0), a fresh orange (1) or a rotten one (2). Every minute, rot spreads from each rotten orange to the fresh oranges next to it. Return the minutes until no fresh orange is left, or -1 if some can never rot.

O(m·n)time
O(m·n)space
multi-source BFS1 level = 1 minute

rows of 0 / 1 / 2 separated by ; · 1–7 rows × 1–8 columns · LeetCode's [[2,1,1],...] works too

Queue front at the left · blue = this minute, green = next minute

public int orangesRotting(int[][] grid) { Queue<int[]> q = new ArrayDeque<>(); int fresh = 0; int time = 0; for (int r = 0; r < grid.length; r++) { for (int c = 0; c < grid[0].length; c++) { if (grid[r][c] == 1) { fresh++; } if (grid[r][c] == 2) { q.add(new int[] { r, c }); } } } int[][] dirs = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; while (fresh > 0 && !q.isEmpty()) { int size = q.size(); // one minute for (int i = 0; i < size; i++) { int[] cell = q.poll(); int r = cell[0]; int c = cell[1]; for (int[] d : dirs) { int row = r + d[0]; int col = c + d[1]; if (row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && grid[row][col] == 1) { grid[row][col] = 2; q.add(new int[] { row, col }); fresh--; } } } time++; } return fresh == 0 ? time : -1;}
time
0
fresh
0
q.size()
0
(r, c)
—

Why it works

  1. Brute force simulates minute by minute: scan the whole grid, rot every fresh orange next to a rotten one, repeat. Each minute costs O(m·n) and there can be O(m·n) minutes: O((m·n)²).
  2. Invariant: the queue holds exactly one minute's frontier at the start of each outer loop. All rotten oranges start in the queue together (multi-source BFS), so an orange rots at the minute equal to its distance to the nearest rotten one.
  3. O(m·n) time and space: each orange enters the queue once and checks 4 neighbours once; size is frozen before the inner loop, so the oranges added during a minute wait for the next one.
  4. Pitfall: rot the neighbour (grid[row][col] = 2) when you enqueue it, not when you pop it, or two oranges can enqueue the same cell. And stop when fresh hits 0: the last batch in the queue has nothing left to rot, so it must not add a minute.
  5. Related: Walls and Gates (286) is the same multi-source BFS that writes the level number into each room; 01 Matrix (542) asks for the distance to the nearest 0.