Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Multi-Source BFS
DSA

Multi-Source BFS

Learn how to run BFS simultaneously from multiple starting points to solve grid distance and propagation problems.

Multi-Source BFS starts the queue with multiple sources at once — the wave spreads from all of them simultaneously.

Its core advantage:

Distance from a cell to its nearest source — not any specific one.

Focus on recognizing:

“Simultaneously” / “nearest of many” / “minutes until all…” → seed the queue with every source

Core Template

public int multiSourceBFS(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();

    // Add ALL sources first
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (grid[r][c] == SOURCE)
                queue.offer(new int[]{r, c});

    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    int distance = -1;

    while (!queue.isEmpty()) {
        int size = queue.size();
        distance++;                     // one level = one step

        for (int s = 0; s < size; s++) {
            int[] cell = queue.poll();

            for (int[] d : dirs) {
                int nr = cell[0] + d[0];
                int nc = cell[1] + d[1];

                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && isUnvisited(grid, nr, nc)) {
                    markVisited(grid, nr, nc);
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
    }

    return distance;
}
from collections import deque

def multi_source_bfs(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()

    # Add ALL sources first
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == SOURCE:
                queue.append((r, c))

    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    distance = -1

    while queue:
        distance += 1               # one level = one step

        for _ in range(len(queue)):
            r, c = queue.popleft()

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc

                if 0 <= nr < rows and 0 <= nc < cols \
                        and is_unvisited(grid, nr, nc):
                    mark_visited(grid, nr, nc)
                    queue.append((nr, nc))

    return distance
int multiSourceBFS(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    queue<pair<int, int>> q;

    // Add ALL sources first
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (grid[r][c] == SOURCE)
                q.push({r, c});

    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int distance = -1;

    while (!q.empty()) {
        int size = q.size();
        distance++;                 // one level = one step

        while (size--) {
            auto [r, c] = q.front();
            q.pop();

            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];

                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && isUnvisited(grid, nr, nc)) {
                    markVisited(grid, nr, nc);
                    q.push({nr, nc});
                }
            }
        }
    }

    return distance;
}
function multiSourceBFS(grid) {
  const rows = grid.length,
    cols = grid[0].length;
  const queue = [];

  // Add ALL sources first
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === SOURCE) queue.push([r, c]);

  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  let distance = -1;

  while (queue.length) {
    const size = queue.length;
    distance++; // one level = one step

    for (let s = 0; s < size; s++) {
      const [r, c] = queue.shift();

      for (const [dr, dc] of dirs) {
        const nr = r + dr,
          nc = c + dc;

        if (
          nr >= 0 &&
          nr < rows &&
          nc >= 0 &&
          nc < cols &&
          isUnvisited(grid, nr, nc)
        ) {
          markVisited(grid, nr, nc);
          queue.push([nr, nc]);
        }
      }
    }
  }

  return distance;
}

The only difference from normal BFS: all sources enter the queue before the walk begins.

Level = time step. Seeding all sources up front makes every distance a “nearest source” distance.

Pattern 1: Rotting Oranges

Watch rot spread through an orange grid level by level — the whole frontier advances each minute. Press ▶ to animate.

Rotting Oranges (Multi-Source BFS)

Every rotten orange enters the queue at minute 0. Each minute, rot spreads to adjacent fresh oranges. The answer is the number of minutes until no fresh orange remains (or -1 if some can never rot).

Grid: 2 = rotten, 1 = fresh, 0 = empty. Seed ALL rotten cells at minute 0. Each wave spreads rot one cell outward — watch the 1s flip to 2s as the front advances. The last wave to rot a fresh cell is the answer.

GRID VISUALIZER
Steps –
2
1
1
1
1
0
0
1
1
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        enqueue ALL rotten oranges at minute 0
                      
                        2
                        while queue not empty:
                      
                        3
                          process the whole current level (one minute)
                      
                        4
                          each orange rots its fresh 4-neighbors
                      
                        5
                        answer = last minute a new orange rotted

Minutes until every fresh orange rots — -1 if some never do:

public int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int fresh = 0;

    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) queue.offer(new int[]{r, c});
            else if (grid[r][c] == 1) fresh++;
        }

    if (fresh == 0) return 0;

    int minutes = -1;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

    while (!queue.isEmpty()) {
        int size = queue.size();
        minutes++;

        for (int s = 0; s < size; s++) {
            int[] cell = queue.poll();

            for (int[] d : dirs) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];

                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
    }

    return fresh == 0 ? minutes : -1;
}
from collections import deque

def oranges_rotting(grid):
    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))
            elif grid[r][c] == 1:
                fresh += 1

    if fresh == 0:
        return 0

    minutes = -1

    while queue:
        minutes += 1

        for _ in range(len(queue)):
            r, c = queue.popleft()

            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc

                if 0 <= nr < rows and 0 <= nc < cols \
                        and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))

    return minutes if fresh == 0 else -1
int orangesRotting(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    queue<pair<int, int>> q;
    int fresh = 0;

    for (int r = 0; r < rows; r++)
        for (int 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;

    int minutes = -1;
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    while (!q.empty()) {
        int size = q.size();
        minutes++;

        while (size--) {
            auto [r, c] = q.front();
            q.pop();

            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];

                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    q.push({nr, nc});
                }
            }
        }
    }

    return fresh == 0 ? minutes : -1;
}
function orangesRotting(grid) {
  const rows = grid.length,
    cols = grid[0].length;
  const queue = [];
  let fresh = 0;

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }

  if (fresh === 0) return 0;

  let minutes = -1;
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  while (queue.length) {
    const size = queue.length;
    minutes++;

    for (let s = 0; s < size; s++) {
      const [r, c] = queue.shift();

      for (const [dr, dc] of dirs) {
        const nr = r + dr,
          nc = c + dc;

        if (
          nr >= 0 &&
          nr < rows &&
          nc >= 0 &&
          nc < cols &&
          grid[nr][nc] === 1
        ) {
          grid[nr][nc] = 2;
          fresh--;
          queue.push([nr, nc]);
        }
      }
    }
  }

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

Track fresh separately — the loop can end with unreachable oranges still standing.

Pattern 2: Distance from Nearest Source

Same skeleton, but write the distance INTO each cell instead of counting levels:

public int[][] nearestDistance(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();

    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (grid[r][c] == 0) {           // source
                queue.offer(new int[]{r, c});
            } else {
                grid[r][c] = -1;             // unvisited marker
            }

    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

    while (!queue.isEmpty()) {
        int[] cell = queue.poll();

        for (int[] d : dirs) {
            int nr = cell[0] + d[0], nc = cell[1] + d[1];

            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && grid[nr][nc] == -1) {
                grid[nr][nc] = grid[cell[0]][cell[1]] + 1;
                queue.offer(new int[]{nr, nc});
            }
        }
    }

    return grid;
}
from collections import deque

def nearest_distance(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0:      # source
                queue.append((r, c))
            else:
                grid[r][c] = -1      # unvisited marker

    while queue:
        r, c = queue.popleft()

        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc

            if 0 <= nr < rows and 0 <= nc < cols \
                    and grid[nr][nc] == -1:
                grid[nr][nc] = grid[r][c] + 1
                queue.append((nr, nc))

    return grid
vector<vector<int>> nearestDistance(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    queue<pair<int, int>> q;

    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 0) q.push({r, c});   // source
            else grid[r][c] = -1;                  // unvisited
        }

    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];

            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && grid[nr][nc] == -1) {
                grid[nr][nc] = grid[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }

    return grid;
}
function nearestDistance(grid) {
  const rows = grid.length,
    cols = grid[0].length;
  const queue = [];

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 0) queue.push([r, c]); // source
      else grid[r][c] = -1; // unvisited marker
    }

  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  while (queue.length) {
    const [r, c] = queue.shift();

    for (const [dr, dc] of dirs) {
      const nr = r + dr,
        nc = c + dc;

      if (
        nr >= 0 &&
        nr < rows &&
        nc >= 0 &&
        nc < cols &&
        grid[nr][nc] === -1
      ) {
        grid[nr][nc] = grid[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }

  return grid;
}

Storing distance + 1 per neighbor removes the level-size bookkeeping entirely.

Common Mistakes

Seeding sources one at a time.

Running BFS from each source separately answers “distance to THIS source”, not “nearest”. Seed everything first.

Forgetting the unreachable case.

Rotting oranges must report -1 when fresh > 0 after BFS ends.

Losing the level boundary.

When minutes matter, process exactly size cells per round — otherwise levels blur together.

Complexity

OperationTimeSpace
Multi-source BFSO(n·m)O(n·m)

My Private Notes

Notes are auto-saved locally to this device.