Skip to main content
BFS Queue

Multi-Source BFS

Start BFS from multiple sources simultaneously by enqueuing all of them at the beginning. The BFS then expands outward from ALL sources at once, finding the nearest source for every cell. Used in 'rotting oranges', distance-to-nearest problems.

O(V + E)
·
O(V)

How It Works

Some problems ask for the distance from every cell to its nearest source — nearest rotten orange, nearest gate, nearest zero. Running one BFS per source costs O(sources × cells). Multi-source BFS instead seeds the queue with all sources at distance 0 before the loop starts. The wave then expands from every source simultaneously, and the first wave to reach a cell is guaranteed to come from its closest source.

Conceptually this is ordinary BFS from a virtual super-node connected to all sources by zero-cost edges. One pass over the grid suffices: O(cells) time and space regardless of how many sources exist, which is why it is the standard tool for spreading or infection-style simulations.

Step-by-Step Visualization

Distance of each cell to nearest 0
0
0
0
1
0
2
0
3
1
4
0
5
1
6
1
7
1
8
SourcesAll 0-cells
1/3

Code

Java
static int[][] updateMatrix(int[][] mat) {
  int m = mat.length, n = mat[0].length;
  Queue<int[]> queue = new LinkedList<>();
  int[][] dist = new int[m][n];
  for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);

  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      if (mat[i][j] == 0) { dist[i][j] = 0; queue.add(new int[]{i, j}); }

  int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
  while (!queue.isEmpty()) {
    int[] cell = queue.poll();
    int r = cell[0], c = cell[1];
    for (int[] d : dirs) {
      int nr = r+d[0], nc = c+d[1];
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] > dist[r][c]+1) {
        dist[nr][nc] = dist[r][c] + 1;
        queue.add(new int[]{nr, nc});
      }
    }
  }
  return dist;
}

Tips & Gotchas

1Same as gb-multi: enqueue all sources at the start
2All sources start at distance 0
3Useful for nearest distance from any source problems

Practice Problems

  • 1Rotting Oranges
  • 201 Matrix
  • 3Walls and Gates
  • 4Map of Highest Peak

About the BFS Queue Pattern

BFS explores nodes level by level using a queue. Enqueue the starting node, then repeatedly: dequeue a node, process it, and enqueue all its unvisited neighbors. This guarantees you visit nodes in order of their distance from the start.

Key insight

BFS = queue. If you need shortest path in an unweighted graph or level-order traversal, reach for a queue. Monotonic deques solve sliding window extremes in O(n).

Common Queue / Deque Interview Problems

  • Binary Tree Level Order Traversal
  • Sliding Window Maximum
  • Rotting Oranges
  • Shortest Path in Binary Matrix
  • Implement Queue using Stacks

Frequently Asked Questions

How do I know which minute or round the process finished on?

Either track levels explicitly by snapshotting the queue size per round, or store each cell's distance when you enqueue it and take the maximum at the end. For Rotting Oranges, also verify afterward that no fresh orange remains unreached, in which case the answer is −1.

What distinguishes a multi-source problem from a plain BFS problem?

Look for phrasing like 'nearest', 'for every cell', or simultaneous spreading from many starting points. If the answer for each location depends on its closest of many origins, seed them all at once; if there is a single start and a single goal, ordinary BFS applies.