994. Rotting Oranges

At a Glance

Topic: graphs
Pattern: BFS (multi-source, layered)
Difficulty: Medium
Companies: Amazon, Microsoft, Google, Meta, Apple
Frequency: High
LeetCode: 994

Problem (one-liner)

Grid 0 empty, 1 fresh orange, 2 rotten. Each minute, rotten infects 4-neighbors. Return minutes until no fresh remain, or -1 if impossible.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Simultaneous propagation — minute cadence = BFS levels
Multiple sources — enqueue all 2 initially

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

DFS timestamp — messy with correctness — avoid.
Optimal — multi-source BFS — O(nm) time, O(nm) queue.

Optimal Solution

Go

func orangesRotting(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])
	queue := make([][2]int, 0)
	fresh := 0
	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if grid[row][col] == 2 {
				queue = append(queue, [2]int{row, col})
			} else if grid[row][col] == 1 {
				fresh++
			}
		}
	}
	if fresh == 0 {
		return 0
	}
	minutesElapsed := 0
	directions := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	head := 0
	for len(queue)-head > 0 && fresh > 0 {
		waveCount := len(queue) - head
		for step := 0; step < waveCount; step++ {
			cell := queue[head]
			head++
			for _, delta := range directions {
				nextRow := cell[0] + delta[0]
				nextCol := cell[1] + delta[1]
				if nextRow < 0 || nextCol < 0 || nextRow >= rows || nextCol >= cols {
					continue
				}
				if grid[nextRow][nextCol] != 1 {
					continue
				}
				grid[nextRow][nextCol] = 2
				fresh--
				queue = append(queue, [2]int{nextRow, nextCol})
			}
		}
		minutesElapsed++
	}
	if fresh > 0 {
		return -1
	}
	return minutesElapsed
}

JavaScript

function orangesRotting(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let fresh = 0;
  for (let row = 0; row < rows; row += 1) {
    for (let col = 0; col < cols; col += 1) {
      if (grid[row][col] === 2) {
        queue.push([row, col]);
      } else if (grid[row][col] === 1) {
        fresh += 1;
      }
    }
  }
  if (fresh === 0) {
    return 0;
  }
  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  let minutesElapsed = 0;
  let head = 0;
  while (queue.length - head > 0 && fresh > 0) {
    const waveCount = queue.length - head;
    for (let step = 0; step < waveCount; step += 1) {
      const cell = queue[head];
      head += 1;
      for (const [deltaRow, deltaCol] of directions) {
        const nextRow = cell[0] + deltaRow;
        const nextCol = cell[1] + deltaCol;
        if (nextRow < 0 || nextCol < 0 || nextRow >= rows || nextCol >= cols) {
          continue;
        }
        if (grid[nextRow][nextCol] !== 1) {
          continue;
        }
        grid[nextRow][nextCol] = 2;
        fresh -= 1;
        queue.push([nextRow, nextCol]);
      }
    }
    minutesElapsed += 1;
  }
  return fresh === 0 ? minutesElapsed : -1;
}