Stage 2: Recursive Thinking·Graphs: BFS & DFS

Medium#9946 min readGraphsBFSMulti-source BFSLeetCode

Rotting Oranges

Multi-source BFS starting from every rotten orange

Multi-source BFS. All rotten oranges start in the queue simultaneously.

Published Apr 16, 2026

Problem

Given an m × n grid where each cell is 0 (empty), 1 (fresh orange), or 2 (rotten orange), every minute any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum number of minutes until no cell has a fresh orange, or -1 if it's impossible.

Input

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

Output

Input

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

Output

-1

Explanation

The bottom-left fresh orange can never be reached.

Input

grid = [[0,2]]

Output

Explanation

No fresh oranges; 0 minutes.

Intuition

Each "minute" rotten oranges spread one step in parallel. That's textbook BFS except with more than one source — every starting rotten orange is a level-0 node.

Multi-source BFS seeds the queue with every rotten orange up front. Process the queue in level order; each level is one minute. Track fresh-orange count as you go; at the end, if any remain, return -1, otherwise return the number of levels minus one (the first level was already rotten).

Multi-source BFS is the same distance-from-nearest-source algorithm you'd use for "distance from nearest gate" (#286) or "walls and gates".

Approach

Multi-source BFS

TimeO(m·n)

SpaceO(m·n)

Recommended

Queue every rotten orange's coordinate at time 0. BFS layer by layer; each layer is one minute.

Key details:

Count fresh oranges upfront — if zero, return 0 immediately.
Increment the minute counter once per full layer, not per cell.
On an infected cell, mark grid[nr][nc] = 2 immediately to dedupe.

use std::collections::VecDeque;

impl Solution {
    pub fn oranges_rotting(grid: Vec<Vec<i32>>) -> i32 {
        let rows = grid.len();
        let cols = grid[0].len();
        let mut grid = grid;
        let mut q: VecDeque<(usize, usize)> = VecDeque::new();
        let mut fresh = 0;
        for r in 0..rows {
            for c in 0..cols {
                match grid[r][c] {
                    2 => q.push_back((r, c)),
                    1 => fresh += 1,
                    _ => {}
                }
            }
        }
        if fresh == 0 {
            return 0;
        }
        let mut minutes = 0;
        let dirs: [(i32, i32); 4] = [(1, 0), (-1, 0), (0, 1), (0, -1)];
        while !q.is_empty() {
            let mut infected_this_layer = false;
            for _ in 0..q.len() {
                let (r, c) = q.pop_front().unwrap();
                for (dr, dc) in dirs {
                    let nr = r as i32 + dr;
                    let nc = c as i32 + dc;
                    if nr < 0 || nc < 0 || nr >= rows as i32 || nc >= cols as i32 {
                        continue;
                    }
                    let (nr, nc) = (nr as usize, nc as usize);
                    if grid[nr][nc] == 1 {
                        grid[nr][nc] = 2;
                        fresh -= 1;
                        q.push_back((nr, nc));
                        infected_this_layer = true;
                    }
                }
            }
            if infected_this_layer {
                minutes += 1;
            }
        }
        if fresh > 0 {
            -1
        } else {
            minutes
        }
    }
}

Rust · runnable

function orangesRotting(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const q: [number, number][] = [];
  let fresh = 0;
  for (let r = 0; r < rows; r++) {
    for (let 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;
  let minutes = 0;
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ] as const;
  let head = 0;
  while (head < q.length) {
    const tail = q.length;
    let infected = false;
    while (head < tail) {
      const [r, c] = q[head++];
      for (const [dr, dc] of dirs) {
        const nr = r + dr;
        const nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
        if (grid[nr][nc] === 1) {
          grid[nr][nc] = 2;
          fresh--;
          q.push([nr, nc]);
          infected = true;
        }
      }
    }
    if (infected) minutes++;
  }
  return fresh > 0 ? -1 : minutes;
}

TypeScript · runnable

Per-orange BFS (rejected baseline)

TimeO((m·n)²)

SpaceO(m·n)

A naive approach: for each fresh orange, BFS to the nearest rotten orange and take the max. Works correctly but is quadratic — each of the m · n fresh oranges can trigger an O(m · n) search.

Shown here only to contrast: multi-source BFS inverts the direction (start from sources, reach all targets once), dropping a factor of m · n.

use std::collections::VecDeque;

impl Solution {
    pub fn oranges_rotting(grid: Vec<Vec<i32>>) -> i32 {
        let rows = grid.len();
        let cols = grid[0].len();
        let dirs: [(i32, i32); 4] = [(1, 0), (-1, 0), (0, 1), (0, -1)];
        let mut max_dist = 0;
        for r in 0..rows {
            for c in 0..cols {
                if grid[r][c] != 1 {
                    continue;
                }
                // BFS outward from this fresh orange until we meet a rotten one.
                let mut dist = vec![vec![-1i32; cols]; rows];
                let mut q: VecDeque<(usize, usize)> = VecDeque::new();
                q.push_back((r, c));
                dist[r][c] = 0;
                let mut best = -1;
                while let Some((cr, cc)) = q.pop_front() {
                    if grid[cr][cc] == 2 {
                        best = dist[cr][cc];
                        break;
                    }
                    for (dr, dc) in dirs {
                        let nr = cr as i32 + dr;
                        let nc = cc as i32 + dc;
                        if nr < 0 || nc < 0 || nr >= rows as i32 || nc >= cols as i32 {
                            continue;
                        }
                        let (nr, nc) = (nr as usize, nc as usize);
                        if grid[nr][nc] == 0 || dist[nr][nc] != -1 {
                            continue;
                        }
                        dist[nr][nc] = dist[cr][cc] + 1;
                        q.push_back((nr, nc));
                    }
                }
                if best == -1 {
                    return -1;
                }
                max_dist = max_dist.max(best);
            }
        }
        max_dist
    }
}

Rust · runnable

function orangesRotting(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ] as const;
  let maxDist = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== 1) continue;
      const dist: number[][] = Array.from({ length: rows }, () =>
        new Array(cols).fill(-1)
      );
      const q: [number, number][] = [[r, c]];
      dist[r][c] = 0;
      let best = -1;
      let head = 0;
      while (head < q.length) {
        const [cr, cc] = q[head++];
        if (grid[cr][cc] === 2) {
          best = dist[cr][cc];
          break;
        }
        for (const [dr, dc] of dirs) {
          const nr = cr + dr;
          const nc = cc + dc;
          if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
          if (grid[nr][nc] === 0 || dist[nr][nc] !== -1) continue;
          dist[nr][nc] = dist[cr][cc] + 1;
          q.push([nr, nc]);
        }
      }
      if (best === -1) return -1;
      maxDist = Math.max(maxDist, best);
    }
  }
  return maxDist;
}

TypeScript · runnable

Trace

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

minute 0:   minute 1:   minute 2:   minute 3:   minute 4:
2 1 1       2 2 1       2 2 2       2 2 2       2 2 2
1 1 0       2 1 0       2 2 0       2 2 0       2 2 0
0 1 1       0 1 1       0 1 1       0 2 1       0 2 2

minute	queue size at start	infected this layer	fresh remaining
0	1	2	4
1	2	2	2
2	2	1	1
3	1	1	0
4	1	0	0 (done)

Answer: 4 minutes.

Edge cases

No fresh oranges — return 0 immediately.
No rotten oranges but fresh ones exist — BFS never runs; fresh > 0 triggers -1.
Unreachable fresh orange (walled off by zeros) — BFS completes but fresh > 0; return -1.
Grid is 1x1 — handled by the upfront checks.

Takeaway

Multi-source BFS is "shortest distance from any source". Whenever you see a problem with several starting points that propagate in parallel (rotting, fires, gates, radio signals), seed every source at level 0. The asymptotic win is the problem's m · n reduction over running BFS per source.

Medium#200

Number of Islands

Flood fill with DFS. The grid IS the graph — each cell is a node.

Hard#127

Word Ladder

BFS on an implicit graph. Each word is a node, edges connect words differing by one letter.

Medium#207

Course Schedule

Cycle detection in directed graph. Both DFS (3-color) and Kahn’s BFS work.