Graphs - BFS· 25 min

Rotting Oranges

LeetCode #994 · Medium · Solution walkthrough with Java and Python code

Graphs - BFS · Medium

LeetCode 994: Rotting Oranges — solution

Solve LeetCode 994 with a multi-source BFS that starts from every rotten orange at once and advances one level per minute — O(m · n) time and space.

Problem in plain words

A grid holds 0 (empty), 1 (fresh orange) and 2 (rotten orange). Each minute, every rotten orange makes its fresh up/down/left/right neighbours rotten. Return how many minutes pass until no fresh orange is left, or -1 if some fresh orange can never be reached.

Example: the single row [2, 1, 1, 0, 1]. After minute 1 the second cell rots, after minute 2 the third. The last orange is cut off by the empty cell, so the answer is -1. Without that last orange, [2, 1, 1] would take 2 minutes.

Intuition

Rot spreads like a wave that advances one cell per minute from all rotten oranges simultaneously. That is a BFS with multiple sources: put every initially rotten orange in the queue before starting. Processing the queue level by level, each level is one minute. Keep a count of fresh oranges; when it drops to zero you have the answer, and if the BFS stalls while fresh oranges remain, return -1.

Approach

  1. Scan the grid: enqueue every 2, count every 1 as fresh.
  2. Set minutes = 0. While the queue is non-empty and fresh > 0: increment minutes, then process exactly the current queue size.
  3. For each popped cell, rot every fresh neighbour: set it to 2, decrement fresh, enqueue it.
  4. Return minutes if fresh == 0, otherwise -1.

Dry run

Grid [[2, 1], [1, 1]], fresh = 3.

MinuteRotten this minutefresh left
0(0,0) at start3
1(0,1), (1,0)1
2(1,1)0

Fresh hits zero after minute 2, so the answer is 2.

Java solution

java
class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        int fresh = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) {
                    queue.offer(new int[] {r, c});
                } else if (grid[r][c] == 1) {
                    fresh++;
                }
            }
        }
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int minutes = 0;
        while (!queue.isEmpty() && fresh > 0) {
            minutes++;
            for (int i = queue.size(); i > 0; i--) {
                int[] cell = queue.poll();
                for (int[] d : dirs) {
                    int r = cell[0] + d[0];
                    int c = cell[1] + d[1];
                    if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 1) {
                        grid[r][c] = 2;
                        fresh--;
                        queue.offer(new int[] {r, c});
                    }
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
}

Python solution

python
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue = deque()
        fresh = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    queue.append((r, c))
                elif grid[r][c] == 1:
                    fresh += 1
        minutes = 0
        while queue and fresh > 0:
            minutes += 1
            for _ in range(len(queue)):
                r, c = queue.popleft()
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 2
                        fresh -= 1
                        queue.append((nr, nc))
        return minutes if fresh == 0 else -1

Complexity

MeasureCostWhy
TimeO(m · n)Every cell is scanned once and each orange enters the queue at most once.
SpaceO(m · n)In the worst case the queue holds most of the grid.

Edge cases and common mistakes

  • No fresh oranges at all — the answer is 0, even if there are no rotten ones either. The fresh > 0 loop guard handles it.
  • Counting one extra minute — if you loop until the queue is empty, the final level (which rots nothing) adds a phantom minute. Stopping when fresh == 0 avoids it.
  • Running a BFS from each rotten orange separately — that is slower and gives the wrong timing; all sources must start together.
  • Fresh oranges but no rotten ones — the queue starts empty, so the answer is -1.
›Why not DFS?

The answer is a shortest-time question across many sources. BFS naturally processes cells in order of distance from the nearest rotten orange; DFS would need extra bookkeeping to compute the minimum time per cell.

48 / 75