Multi-Source BFS: The Pattern Behind Rotting Oranges, Walls and Gates, and Word Ladder

Most developers know single-source BFS — start from one node, find the shortest path to everything else. Multi-source BFS is the same thing, but with multiple starting nodes pushed into the queue simultaneously. It sounds like a minor tweak. It unlocks a whole class of problems.

The key insight: if you need the minimum distance from any of several sources to every other node, you don't run BFS separately from each source (that would be O(k × m × n) for k sources). You push all sources into the queue at once and run one BFS pass. Each cell gets updated the first time BFS reaches it, which by definition is the minimum distance from any source. That's the BFS guarantee: first reach equals shortest path.

The Pattern

Single-source BFS: one item in the initial queue. Multi-source BFS: multiple items. The rest of the algorithm is identical. That's it. That's the pattern.

Problem 1: Walls and Gates (LeetCode 286)

The problem: You have an m × n grid with three types of cells: -1 (walls), 0 (gates), and 2^31 - 1 (empty rooms, represented as INF). Fill each empty room with the distance to its nearest gate. Walls and gates stay unchanged. If a room can't reach a gate, leave it as INF.

Brute Force: BFS from Each Room

For every empty room, run BFS to find the nearest gate. That's one BFS per room, each taking O(m × n) time. Total: O((m × n)²). On a 300 × 300 grid, that's roughly 8 billion operations. Not going to work.

Optimal: Multi-Source BFS from All Gates

// Time: O(m * n), Space: O(m * n)
const wallsAndGates = (rooms) => {
  const rows = rooms.length;
  const cols = rooms[0].length;
  const INF = 2 ** 31 - 1;
  const queue = [];
 
  // Seed the queue with every gate simultaneously
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (rooms[r][c] === 0) queue.push([r, c]);
    }
  }
 
  const dirs = [[1,0], [-1,0], [0,1], [0,-1]];
 
  // An index cursor, not queue.shift() — see the note under this listing
  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
 
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
 
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (rooms[nr][nc] !== INF) continue; // wall, gate, or already updated room
 
      rooms[nr][nc] = rooms[r][c] + 1; // distance from nearest gate
      queue.push([nr, nc]);
    }
  }
  // modifies rooms in-place, no return value needed
};

The rooms[nr][nc] !== INF guard handles everything at once: walls have -1, gates have 0, and already-updated rooms have a finite distance — none of these equal INF. Once a room gets a distance, BFS won't overwrite it, so the first-reach equals minimum distance guarantee holds.

Problem 2: Rotting Oranges (LeetCode 994)

The problem: A grid where 0 is empty, 1 is a fresh orange, and 2 is a rotten orange. Every minute, each rotten orange infects all adjacent fresh oranges. Return the minimum minutes until no fresh oranges remain, or -1 if it's impossible.

This is Walls and Gates with a clock attached. The "minutes elapsed" is just the BFS level number — you're counting how many rounds of spreading happen before all fresh oranges are converted.

Brute Force: Simulate Minute by Minute

Scan the entire grid each minute, update rotten oranges, repeat. Time: O((m × n)²) in the worst case. Same problem as before.

Optimal: Multi-Source BFS with Level Tracking

// Time: O(m * n), Space: O(m * n)
const orangesRotting = (grid) => {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let freshCount = 0;
  let minutes = 0;
 
  // Seed all rotten oranges, count fresh ones
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      if (grid[r][c] === 1) freshCount++;
    }
  }
 
  if (freshCount === 0) return 0; // already done
 
  const dirs = [[1,0], [-1,0], [0,1], [0,-1]];
 
  let head = 0; // queue cursor, same reason as above
  while (head < queue.length && freshCount > 0) {
    const levelSize = queue.length - head; // how many oranges are rotten THIS minute
    minutes++;
 
    for (let i = 0; i < levelSize; i++) {
      const [r, c] = queue[head++];
 
      for (const [dr, dc] of dirs) {
        const nr = r + dr;
        const nc = c + dc;
 
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (grid[nr][nc] !== 1) continue; // not a fresh orange
 
        grid[nr][nc] = 2; // now rotten
        freshCount--;
        queue.push([nr, nc]);
      }
    }
  }
 
  return freshCount === 0 ? minutes : -1;
};

The levelSize pattern is the classic BFS level-order trick: capture how many items are waiting before the inner loop, then process exactly that many. With a cursor that is queue.length - head rather than queue.length. Each outer iteration is one "minute." All oranges that go rotten in minute N are in the queue together, and they collectively infect the next wave.

Visualizing the BFS Levels

Problem 3: Word Ladder (LeetCode 127)

The problem: Given a start word, end word, and a word list, find the length of the shortest transformation sequence from start to end where each step changes exactly one letter and every intermediate word exists in the word list.

This is BFS on a word graph. Each word is a node. Two words are connected if they differ by exactly one character. You're looking for the shortest path between two nodes.

Why Not DFS?

DFS finds a path — not the shortest path. For shortest path in an unweighted graph, BFS is the right tool. Always. This is non-negotiable.

Brute Force: Build the Full Adjacency List

Compare every pair of words to check if they're one edit apart. Time: O(n² × L) where n is the word list size and L is word length. For a list of 5000 words with 5-letter words, that's 125 million character comparisons just to build the graph. Then BFS on top of that.

Optimal: Implicit Graph BFS

Don't precompute edges. For each word being processed, generate all possible one-letter mutations and check if they're in the word set.

// Time: O(n * L^2), Space: O(n * L)
// n = word list size, L = word length
const ladderLength = (beginWord, endWord, wordList) => {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0; // impossible
 
  const queue = [[beginWord, 1]]; // [current word, steps taken]
  const visited = new Set([beginWord]);
 
  let head = 0; // queue cursor, not shift()
  while (head < queue.length) {
    const [word, steps] = queue[head++];
 
    // Try replacing each character with 'a'-'z'
    for (let i = 0; i < word.length; i++) {
      for (let charCode = 97; charCode <= 122; charCode++) {
        const newWord = word.slice(0, i) + String.fromCharCode(charCode) + word.slice(i + 1);
 
        if (newWord === endWord) return steps + 1;
 
        if (wordSet.has(newWord) && !visited.has(newWord)) {
          visited.add(newWord);
          queue.push([newWord, steps + 1]);
        }
      }
    }
  }
 
  return 0; // no transformation sequence found
};

The inner double loop generates all L × 26 possible one-letter variations for each word. It's the same graph traversal pattern as before — the graph is just implicit (generated on the fly) rather than stored explicitly.

Why L² in the Time Complexity?

For each word in the BFS queue, you generate L × 26 candidate words. Each candidate requires O(L) string operations (slice + concatenate). So per word, it's O(L × 26 × L) = O(L²). With n words total, that's O(n × L²). The 26 constant drops out in big-O notation.

That bound also assumes an O(1) dequeue, which is what the head cursor buys. Word Ladder is the mildest of the three cases in this post: each dequeue does L × 26 slice-and-concatenate operations, and that string work hides shift() until the queue is genuinely large. On a 7-letter word graph where the queue grows to the whole word list, shift() and the cursor are indistinguishable at 10,000 words (175ms vs 172ms), but at 83,522 words it's 4,351ms vs 1,739ms — 2.5–3.5× per doubling against 1.9–2.4×. Under LeetCode's 5,000-word limit you would never notice. The extra O(n²) term is real anyway, and the cursor costs one variable.

Comparing the Three Problems

All three use BFS for the same reason: you want the minimum cost (distance, time, steps) to reach a state. BFS guarantees that the first time you reach a state is the minimum cost.

Interview Tips

BFS vs DFS in one sentence: BFS for shortest path or minimum steps. DFS for existence checks, connected components, or when you don't care about optimality.

On multi-source BFS: When you explain it, say this explicitly: "I'll initialize the queue with all sources simultaneously. This gives us the minimum distance from any source to any cell in a single O(m×n) pass." That's the key insight — make sure the interviewer hears you say it.

Level tracking: The levelSize capture pattern (snapshot queue length before the inner loop) is cleaner than storing step count inside each queue element. Both work. The former is more idiomatic for time-based problems like Rotting Oranges.

Word Ladder pitfall: Not checking if endWord is in the word list before starting. If it's not there, return 0 immediately. Forgetting this causes the BFS to run to completion and return 0 anyway, but it wastes time and the interviewer notices.

Complexity for grids: O(m×n) time and space for all grid BFS problems — every cell is enqueued and processed at most once. For Word Ladder: O(n × L²) time where n is word list size, L is word length — the L² comes from generating and constructing candidate strings at each position.