Rotting Oranges

The problem

grid is a box of oranges. Each cell holds 0 for an empty cell, 1 for a fresh orange or 2 for a rotten orange. Every minute, each fresh orange that has a rotten orange directly above, below, left or right of it becomes rotten. Return the number of minutes that pass until no fresh orange is left. If there is no fresh orange at the start, return 0. If some fresh orange can never rot, return -1.

What to write

function solve(grid: number[][]): number

Input
grid = [[2,1,1],[1,1,0],[0,1,1]]

Output
4

Input
grid = [[2,1,1],[0,1,1],[1,0,1]]

Output
-1

Constraints

Cells are 0 empty, 1 fresh, and 2 rotten.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   An orange changes only once: from fresh to rotten, never back. Empty cells never change, and rot cannot cross them. So no orange needs to be handled more than once. Notice the edge cases too: several oranges can be rotten at the start, or none, and there may be no fresh orange at all.

2. Hint 2: Ask a smaller question

   Take the single row [2, 1, 1, 1, 2]. Work out by hand the minute in which each of the three fresh oranges rots. Then look at one of them: what in the row decided its minute?

3. Hint 3: Name the pattern

   The minute an orange rots is its distance, in steps through oranges, from the nearest orange that starts rotten. Finding step counts by spreading outwards one step at a time, from all the starting points at once, is breadth-first search by distance. The signal is something that spreads to neighbors once per time unit. Read the lesson on breadth-first search by distance.

4. Hint 4: State the invariant

   Keep the rotten oranges in a queue: a line where you add at the back and take from the front. The queue holds them in the order they rotted, so the minutes never go down from front to back. An orange is marked rotten the moment it joins, so it joins once, with its earliest minute.

5. Hint 5: Sketch the pseudocode

   Queue every rotten orange with minute 0, count the fresh ones, set last = 0. While the queue has oranges: take the front one and set last to its minute. For each fresh orange next to it: mark it rotten, lower the count, queue it with minute last + 1. Return -1 if the count is not 0, otherwise last.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Start breadth-first search from all rotten oranges simultaneously. BFS distance gives the infection minute.

The slow way

Play it out minute by minute. Scan the whole grid, collect every fresh orange that has a rotten orange next to it, turn them all rotten together and count one minute. Stop when a scan changes nothing. It is correct, but every minute costs a full scan of the grid, and a long winding line of oranges takes many minutes.

The insight

An orange's minute is its distance, in steps through oranges, from the nearest orange that starts rotten. So let the rot spread from all the starting oranges at once, always handling nearer oranges before farther ones. The first time the rot reaches an orange then gives its minute. This nearest-first spreading is called breadth-first search.

Step by step

1. Put every rotten orange in a queue with minute 0; count the fresh ones. A queue is a line: you add at the back and take from the front. Every orange that starts rotten spreads from minute 0, so they all go in first. The count shows at the end whether one stayed fresh.
2. Take the orange at the front: its minute is the latest so far. Oranges leave the queue in the order they rotted, so each one rotted no earlier than those before it. When the queue runs empty, the minute remembered here is the minute of the last orange to rot.
3. Look at the four cells next to it. Rot passes only to the cells directly above, below, left and right, never diagonally. Some of these four positions may lie outside the grid; the test in the next step leaves those out.
4. A fresh neighbor rots one minute later: mark it and queue it. The orange taken out rotted at its minute, so a fresh orange beside it rots one minute later and leaves the fresh count. Marking that orange rotten right away keeps another rotten orange from queueing it a second time.
5. Return -1 if a fresh orange is left, otherwise the last minute. When the queue is empty nothing changes again, so a fresh orange still counted can never rot. With none left, the answer is the minute of the last orange taken out, which stays 0 if nothing was ever taken.

The same numbered steps are the comments in each solution.

function solve(grid) {
  // 1. Put every rotten orange in a queue with minute 0; count the fresh ones
  // The queue is an array of [row, column, minute]. Removing the first item
  // of an array is slow, so nothing is removed: it is read in order instead.
  const q = [];
  let fresh = 0;
  for (let r = 0; r < grid.length; r++)
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === 2) q.push([r, c, 0]);
      if (grid[r][c] === 1) fresh++;
    }
  // 2. Take the orange at the front: its minute is the latest so far
  let time = 0;
  // i is the position of the front of the queue; push adds at the back.
  for (let i = 0; i < q.length; i++) {
    const [r, c, t] = q[i];
    time = t;
    // 3. Look at the four cells next to it
    for (const [a, b] of [
      [r + 1, c],
      [r - 1, c],
      [r, c + 1],
      [r, c - 1],
    ])
      // 4. A fresh neighbor rots one minute later: mark it and queue it
      // A cell outside the grid reads as undefined, which is not 1.
      if (grid[a]?.[b] === 1) {
        grid[a][b] = 2;
        fresh--;
        q.push([a, b, t + 1]);
      }
  }
  // 5. Return -1 if a fresh orange is left, otherwise the last minute
  return fresh ? -1 : time;
}

function solve(grid: number[][]): number {
  // 1. Put every rotten orange in a queue with minute 0; count the fresh ones
  // The queue is an array of [row, column, minute]. Removing the first item
  // of an array is slow, so nothing is removed: it is read in order instead.
  const q: number[][] = [];
  let fresh = 0;
  for (let r = 0; r < grid.length; r++)
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === 2) q.push([r, c, 0]);
      if (grid[r][c] === 1) fresh++;
    }
  // 2. Take the orange at the front: its minute is the latest so far
  let time = 0;
  // i is the position of the front of the queue; push adds at the back.
  for (let i = 0; i < q.length; i++) {
    const [r, c, t] = q[i];
    time = t;
    // 3. Look at the four cells next to it
    for (const [a, b] of [
      [r + 1, c],
      [r - 1, c],
      [r, c + 1],
      [r, c - 1],
    ])
      // 4. A fresh neighbor rots one minute later: mark it and queue it
      // A cell outside the grid reads as undefined, which is not 1.
      if (grid[a]?.[b] === 1) {
        grid[a][b] = 2;
        fresh--;
        q.push([a, b, t + 1]);
      }
  }
  // 5. Return -1 if a fresh orange is left, otherwise the last minute
  return fresh ? -1 : time;
}

from collections import deque


def solve(grid):
    # 1. Put every rotten orange in a queue with minute 0; count the fresh ones
    rows, cols = len(grid), len(grid[0])
    # A deque is a list that is fast at both ends: append adds at the back,
    # popleft takes from the front. Each entry is (row, column, minute).
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh += 1
    # 2. Take the orange at the front: its minute is the latest so far
    minutes = 0
    while queue:
        r, c, minutes = queue.popleft()
        # 3. Look at the four cells next to it
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            # 4. A fresh neighbor rots one minute later: mark it and queue it
            # The two 0 <= checks matter: Python reads row -1 as the last row.
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                queue.append((nr, nc, minutes + 1))
    # 5. Return -1 if a fresh orange is left, otherwise the last minute
    return -1 if fresh else minutes

Example 1, traced

Input
grid = [[2,1,1],[1,1,0],[0,1,1]]

Output
4

Why it works

Oranges leave the queue in the order they rotted: all of minute 0, then all of minute 1, and so on. So the rot first reaches a fresh orange from the rotten neighbor with the smallest minute, and one more than that is the orange's true minute. Marking at once keeps that first minute. The last orange taken out has the largest minute.

Time and space

Time O(rows · cols), extra space O(rows · cols). The first scan reads every cell once. Then each orange joins the queue at most once and looks at four cells when it is taken out, so the time is O(rows · cols). The queue can hold every cell, so the space is O(rows · cols) too.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Mark an orange rotten when it joins the queue, not when it leaves. Marked late, the center orange of example 1 joins twice and is counted twice, the fresh count ends below zero, and the answer comes out as -1.
• Check the fresh count before you return. Without that check example 2 returns 4, the minute of the last orange that did rot, although the orange in the bottom-left corner stays fresh.
• Start from all the rotten oranges together. Started from the left one only, the row [2, 1, 1, 1, 2] gives 3 instead of 2, because the orange beside the right end is reached from the far side.

Pattern

Breadth-first search by distance. Builds on Binary Tree Level Order Traversal and Number of Islands.

Keep going