Rotting Oranges / Zombie Spread

Problem Statement

You are given an m x n grid where each cell is:

0 — empty
1 — fresh orange
2 — rotten orange

Every minute, a rotten orange contaminates its 4-directionally adjacent fresh orange neighbors. Return the minimum number of minutes until no fresh oranges remain. Return -1 if some fresh orange can never rot.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange at (2,0) is isolated and can't rot.

Constraints:

1 <= m, n <= 10
grid[i][j] is 0, 1, or 2.

Difficulty: Medium

Pattern Recognition

What is the structure of the input? A 2D grid with multiple "infected" starting cells.
What are we computing? Minimum time to reach every reachable fresh cell.
What pattern does this suggest? Multi-source BFS — all rotten cells are seeded at time 0 and propagate in layers.
Why does this pattern fit? The first time any rotten neighbor touches a fresh cell, that's the cell's true rotten time. BFS layer-counting gives exactly that.

Approach

Brute Force — Repeated grid scans

Each minute, scan the grid for rotten cells and infect their neighbors. Stop when a full pass infects nothing.

Time: O((mn)^2) in the worst case — each scan is O(mn), and you may need up to O(m*n) passes. Space: O(1) extra. Why insufficient: Wastes work rescanning cells you've already checked.

Optimal — Multi-source BFS

Key Insight: Push every initially rotten cell into the queue first. BFS naturally handles multiple sources — the first time a fresh cell is reached, it's by the earliest rotten source, which is exactly the minute it rots.

Step-by-step:

Enqueue every rotten cell and count fresh cells upfront.
If there are no fresh cells, return 0.
BFS in layers. Each layer is one minute. For every cell dequeued, mutate fresh neighbors to rotten, decrement fresh, and enqueue them.
After the BFS, if fresh == 0, return minutes; else return -1.

Time: O(m * n). Space: O(m * n).

Walkthrough

Grid [[2,1,1],[1,1,0],[0,1,1]]. Initial fresh count: 6. Initial queue: [(0,0)].

Minute	Queue drained	Neighbors rotted	Fresh left
0	[(0,0)]	(0,1), (1,0)	4
1	[(0,1),(1,0)]	(0,2), (1,1)	2
2	[(0,2),(1,1)]	(no new — (0,2) neighbors are rotten/empty; (1,1) rotts nothing new via (2,1)) actually let's redo

Let me recompute carefully. After minute 0 queue: [(0,0)].

Process level with size 1 — pop (0,0), neighbors (0,1) and (1,0) become rotten. Queue: [(0,1),(1,0)]. Fresh=4. Minutes++.

Process level size 2 — pop (0,1), rot (0,2). Pop (1,0), rot (1,1). Queue: [(0,2),(1,1)]. Fresh=2. Minutes++.

Process level size 2 — pop (0,2), no fresh neighbors. Pop (1,1), rot (2,1). Queue: [(2,1)]. Fresh=1. Minutes++.

Process level size 1 — pop (2,1), rot (2,2). Queue: [(2,2)]. Fresh=0. Minutes++.

Loop ends because fresh == 0. Answer: 4.

Implementation

TypeScriptC++

typescript

function orangesRotting(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const queue: Array<[number, number]> = [];
  let fresh = 0;
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }

  if (fresh === 0) return 0;
  let minutes = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

  while (queue.length > 0 && fresh > 0) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const [r, c] = queue.shift()!;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] === 1) {
          grid[nr][nc] = 2;
          fresh--;
          queue.push([nr, nc]);
        }
      }
    }
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

cpp

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        queue<pair<int,int>> q;
        int fresh = 0;
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == 2) q.push({r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        if (fresh == 0) return 0;
        vector<pair<int,int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        int minutes = 0;
        while (!q.empty() && fresh > 0) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                auto [r, c] = q.front(); q.pop();
                for (auto [dr, dc] : dirs) {
                    int nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        fresh--;
                        q.push({nr, nc});
                    }
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }
};

Watch out: Incrementing minutes even when the queue is drained and no new cells rotted. Guard with fresh > 0 in the loop condition to avoid counting a bonus minute.

Watch out: Forgetting to handle the "no fresh to start with" case. Return 0 before the BFS.

Watch out: Single-source BFS. You must seed all rotten cells at once, not one at a time — otherwise you measure distance from one source and it's wrong.

Complexity Analysis

	Time	Space
Brute Force (repeated scans)	O((mn)^2)	O(1)
Multi-source BFS	O(mn)	O(mn)

Bottleneck: Every cell is enqueued and dequeued at most once.

Edge Cases

No fresh oranges — Return 0 immediately.
No rotten oranges but fresh exist — BFS never fires; fresh count stays positive; return -1.
Isolated fresh orange — After BFS, fresh > 0; return -1.
Entire grid rotten already — fresh = 0 at start; return 0.
1x1 grid — Single cell; handle all three values correctly.

LC 286 — Walls and Gates: Multi-source BFS from gates, fill nearest distance.
LC 1730 — Shortest Path to Get Food: Single-source BFS, same grid traversal skeleton.
LC 542 — 01 Matrix: Multi-source BFS from zeros, distance to nearest zero.
LC 1162 — As Far from Land as Possible: Multi-source BFS, maximize min distance.

What Is Expected at Each Level?

Junior / New Grad: Recognize BFS. Might seed only one source; should realize multi-source with a nudge. Track minutes correctly.

Mid-level: Write multi-source BFS cleanly, manage the fresh counter, and correctly handle the "no fresh" shortcut and -1 case.

Senior: Discuss variants like per-source spread rates (switch to Dijkstra), barriers (just additional blocked cells), or minimizing minutes with k extra "injections" you can place. Note the time complexity of .shift() in JS (O(n)) and offer a real deque if performance matters.

Rotting Oranges / Zombie Spread ​

Problem Statement ​

Pattern Recognition ​

Approach ​

Brute Force — Repeated grid scans ​

Optimal — Multi-source BFS ​

Walkthrough ​

Implementation ​

Complexity Analysis ​

Edge Cases ​

Related Problems ​

What Is Expected at Each Level? ​