Rotting Oranges

A crate of oranges is described by a grid of integers, where each cell holds:

• 0: an empty spot,
• 1: a fresh orange,
• 2: a rotten orange.

Every minute, each rotten orange spoils all fresh oranges directly above, below, left or right of it (not diagonally). Newly spoiled oranges start spreading the rot from the following minute.

Return the number of minutes that pass until no fresh orange remains. If some fresh orange can never be reached by the rot, return -1. If there are no fresh oranges to begin with, the answer is 0.

Example 1

Example 2

Example 3

Constraints

• 1 <= m, n <= 50 (m rows, n columns)
• grid[i][j] is 0, 1 or 2

Pattern Path · Graphs: Traversal · problem 132 of 169

Start simple

Repeatedly scan the whole grid, spoiling neighbours of rotten oranges, until nothing changes: O((m·n)²) in the worst case (a long winding line of oranges).

The key idea

The rot spreads exactly like a breadth-first search: an orange spoils at minute t if it is at grid distance t from the nearest initially rotten orange. With several rotten oranges, they all spread simultaneously, so put every rotten orange into the queue before starting. This is called a multi-source BFS: it behaves as if one imaginary source connected to all of them.

Count the fresh oranges first. Then process the queue level by level, where each level is one minute: for each orange in the current level, spoil any fresh neighbour, decrement the fresh count and enqueue it for the next level. Mark a neighbour rotten the moment you enqueue it, so it is never added twice.

Increase the minute counter only when a level actually spoiled something. When the queue runs dry, if fresh oranges remain they were unreachable and the answer is -1; otherwise the number of minutes counted is the answer. Every cell enters the queue at most once, so the run time is linear in the grid size.

Complexity

• Time: O(m · n)
• Space: O(m · n) for the queue

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))  # every rotten orange is a source
                elif grid[r][c] == 1:
                    fresh += 1

        minutes = 0
        while queue and fresh > 0:
            minutes += 1
            for _ in range(len(queue)):  # one BFS level = one minute
                i, j = queue.popleft()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == 1:
                        grid[ni][nj] = 2
                        fresh -= 1
                        queue.append((ni, nj))

        return minutes if fresh == 0 else -1

JavaScript

var orangesRotting = function(grid) {
  const rows = grid.length, cols = grid[0].length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let level = [];
  let fresh = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) level.push([r, c]); // every rotten orange is a source
      else if (grid[r][c] === 1) fresh++;
    }
  }

  let minutes = 0;
  while (level.length > 0 && fresh > 0) {
    minutes++;
    const next = []; // oranges that rot during this minute
    for (const [i, j] of level) {
      for (const [di, dj] of dirs) {
        const ni = i + di, nj = j + dj;
        if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] === 1) {
          grid[ni][nj] = 2;
          fresh--;
          next.push([ni, nj]);
        }
      }
    }
    level = next;
  }

  return fresh === 0 ? minutes : -1;
};

What the interviewer is checking

The interviewer is checking whether you see that simultaneous spreading is a multi-source BFS, and whether you can count BFS levels as time correctly.

Mistakes to avoid

• Running a separate BFS from each rotten orange instead of one BFS from all of them.
• Counting one extra minute for the final level that spoils nothing.
• Returning -1 when there are no fresh oranges at all; the answer is 0.
• Spoiling oranges in place during a full-grid scan so that rot travels several cells in one minute.

Follow-ups to expect

• Return the minute each orange rots? (Store BFS distance per cell.)
• What if some oranges take two minutes to rot? (0-1 BFS or Dijkstra.)
• Distance from every cell to the nearest gate or exit? (Same multi-source BFS.)

In real software

Spreading processes such as fire, infection or signal propagation on a grid, and computing distance maps to the nearest of several sources (e.g. nearest hospital), use multi-source BFS.

Practice next