{"title":"Multi-Source BFS","description":"","content":"Multi-source BFS is a variation of breadth-first search where you start from multiple sources at once instead of just one. All sources are added to the queue initially, and the search expands outward in layers, ensuring the shortest distance to each node or cell.\n\nMulti-source BFS is a small extension of standard single-source BFS. The algorithm is identical. The only change is the initialization.\n\n---\n\n## What Is Multi-Source BFS?\n\nIn standard BFS, you start from a single source node, add it to a queue, and explore its neighbors level by level. The FIFO queue guarantees that all nodes at distance d are processed before any node at distance d+1. This gives you shortest paths from that single source.\n\nMulti-source BFS is the same algorithm, but instead of putting one node into the queue at the start, you put all source nodes into the queue at level 0. From there, BFS expands outward from all sources simultaneously, level by level. The result is the shortest distance from each cell to its **nearest** source, not to a specific source.\n\n### Real-World Applications\n\n- **Forest fire simulation:** Multiple fires break out at different locations. Flames spread to adjacent areas every time step. Multi-source BFS models how quickly the entire forest burns.\n- **Network broadcast:** A message originates at several servers. Each server forwards it to its neighbors. Multi-source BFS computes how many hops it takes for every node in the network to receive the message.\n- **Nearest facility computation:** Given a map with several hospitals, find the distance from every location to the nearest hospital. This is a direct multi-source BFS problem.\n- **Social network influence:** Multiple influencers post content simultaneously. How many \"hops\" until a piece of information reaches every user?\n- **Game AI:** In strategy games, multiple units spread control over territory simultaneously. The game engine uses multi-source BFS to compute influence zones.\n\nThese all share the same structure: multiple origins, simultaneous expansion, and the need to know the shortest distance from each point to its nearest origin.\n\n---\n\n## The Core Idea\n\nA common setup is a grid where some cells are marked as \"sources\" and the goal is the shortest distance from every cell to its nearest source.\n\nThe naive approach is to run a BFS from each source independently, computing the distance from that source to every cell, and then take the minimum across all sources. If there are k sources and the grid has m*n cells, that costs O(k * m * n). For a 1000x1000 grid with 500 sources, that is 500 million operations.\n\n### The Key Insight\n\nAll sources are at distance 0. If you put them all into the queue at the start, BFS expands outward from all of them at the same time. Level 1 contains all cells that are adjacent to any source. Level 2 contains all cells that are two steps from their nearest source. And so on.\n\nBecause BFS is FIFO and processes nodes in the order they were enqueued, the first time any cell is visited, it has been reached by the nearest source via the shortest path. A single pass produces the answer for every cell.\n\nThis brings the time complexity down to O(m * n), the same as a single BFS. Every cell is visited exactly once, regardless of how many sources there are.\n\nA useful visual is multiple stones dropped into a pond at the same time. The ripples from each stone expand outward simultaneously. Where two sets of ripples meet, the boundary represents cells equidistant from two sources. Multi-source BFS computes that entire distance field in a single pass.\n\n### Visual Overview\n\nThe diagram below shows a grid with three sources (S). The colors represent the BFS level at which each cell is first reached.\n\n\n```mermaid\nflowchart TD\n subgraph Grid[\"Grid Expansion\"]\n direction TB\n L0[\"Level 0
Sources (S1, S2, S3)\"]:::primary\n L1[\"Level 1
Immediate neighbors of all sources\"]:::orange\n L2[\"Level 2
Neighbors of level-1 cells\"]:::green\n L3[\"Level 3
Remaining cells\"]:::teal\n end\n\n L0 --> L1\n L1 --> L2\n L2 --> L3\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nEach level expands outward from all sources simultaneously. A cell at level 2 means its nearest source is exactly 2 steps away.\n\n---\n\n## How It Works\n\nThe algorithm has three phases. The first is unique to multi-source BFS. The second and third are identical to standard BFS.\n\n### Algorithm Steps\n\n1. **Scan for sources:** Walk through the entire input (grid, graph, etc.) and identify all source nodes. Add each source to the queue and mark it as visited with distance 0.\n2. **BFS expansion:** While the queue is not empty, dequeue a node, look at its neighbors, and for each unvisited neighbor, mark it visited, record its distance (current distance + 1), and enqueue it.\n3. **Result extraction:** When the queue is empty, every reachable cell has been assigned its shortest distance to the nearest source. Read off whatever the problem asks for (maximum distance, specific cell's distance, count of reachable cells, etc.).\n\nThe only difference from single-source BFS is step 1: instead of enqueuing one node, you enqueue all sources.\n\n### Step-by-Step Flowchart\n\n\n```mermaid\nflowchart TD\n A[\"Scan input for all
source nodes\"]:::primary\n B[\"Enqueue all sources
Mark visited, distance = 0\"]:::primary\n C{\"Queue empty?\"}:::orange\n D[\"Dequeue front node\"]:::teal\n E[\"Explore 4-directional
neighbors\"]:::teal\n F{\"Neighbor valid
and unvisited?\"}:::orange\n G[\"Mark visited
Set distance = current + 1
Enqueue neighbor\"]:::green\n H[\"Done: all distances
computed\"]:::green\n\n A --> B\n B --> C\n C -->|No| D\n D --> E\n E --> F\n F -->|Yes| G\n G --> C\n F -->|No| C\n C -->|Yes| H\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n---\n\n## Example Walkthrough: Rotting Oranges (LeetCode 994)\n\nLet us trace through a concrete example.\n\n### Problem Setup\n\nWe have a 4x4 grid. The value 0 means empty, 1 means fresh orange, and 2 means rotten orange.\n\n\n```shell\nGrid:\n 2 1 1 0\n 1 1 0 0\n 0 1 1 1\n 0 0 1 2\n```\n\n\nThere are two rotten oranges: at (0,0) and (3,3). There are 8 fresh oranges. We need to find the minimum number of minutes until all fresh oranges are rotten.\n\n### Step-by-Step Trace\n\n\n```shell\nInitialization:\n Enqueue all rotten oranges: (0,0) and (3,3)\n Queue: [(0,0), (3,3)]\n Fresh count: 8\n Minutes: 0\n\n--- Minute 1 ---\nProcess all nodes currently in queue (size = 2):\n\n Dequeue (0,0): neighbors (0,1) and (1,0) are fresh\n -> Rot (0,1), enqueue. Rot (1,0), enqueue. Fresh count: 6\n Dequeue (3,3): neighbor (2,3) is fresh\n -> Rot (2,3), enqueue. Fresh count: 5\n\n Grid after minute 1:\n 2 2 1 0\n 2 1 0 0\n 0 1 1 2\n 0 0 1 2\n\n Queue: [(0,1), (1,0), (2,3)]\n Minutes: 1\n\n--- Minute 2 ---\nProcess all nodes currently in queue (size = 3):\n\n Dequeue (0,1): neighbor (0,2) is fresh\n -> Rot (0,2), enqueue. Fresh count: 4\n Dequeue (1,0): neighbor (1,1) is fresh\n -> Rot (1,1), enqueue. Fresh count: 3\n Dequeue (2,3): neighbor (2,2) is fresh\n -> Rot (2,2), enqueue. Fresh count: 2\n\n Grid after minute 2:\n 2 2 2 0\n 2 2 0 0\n 0 1 2 2\n 0 0 1 2\n\n Queue: [(0,2), (1,1), (2,2)]\n Minutes: 2\n\n--- Minute 3 ---\nProcess all nodes currently in queue (size = 3):\n\n Dequeue (0,2): no fresh neighbors\n Dequeue (1,1): neighbor (2,1) is fresh\n -> Rot (2,1), enqueue. Fresh count: 1\n Dequeue (2,2): neighbor (3,2) is fresh\n -> Rot (3,2), enqueue. Fresh count: 0\n\n Grid after minute 3:\n 2 2 2 0\n 2 2 0 0\n 0 2 2 2\n 0 0 2 2\n\n Queue: [(2,1), (3,2)]\n Minutes: 3\n\n--- Minute 4 ---\nProcess all nodes currently in queue (size = 2):\n\n Dequeue (2,1): no fresh neighbors\n Dequeue (3,2): no fresh neighbors\n\n Queue: []\n Fresh count: 0\n\nResult: 3 minutes\n```\n\n\nBoth rotten oranges spread simultaneously. By minute 2, the expanding rot zones from the two sources have almost met in the middle. By minute 3, every fresh orange has been reached. Running BFS from each source separately and taking the per-cell minimum would produce the same final answer, but it would cost O(k * m * n) instead of O(m * n). Multi-source BFS speeds up the computation without changing the result.\n\n---\n\n## Implementation\n\nHere is a generic multi-source BFS implementation for grid problems. The function takes a grid, identifies all sources, and computes the shortest distance from each cell to its nearest source.\n\n\n```java\nimport java.util.LinkedList;\nimport java.util.Queue;\n\n/**\n * Multi-source BFS on a grid.\n * Computes shortest distance from each cell to the nearest source.\n *\n * Time Complexity: O(m * n)\n * Space Complexity: O(m * n)\n */\npublic class MultiSourceBFS {\n\n public int[][] shortestDistanceFromSources(int[][] grid, int sourceValue) {\n int rows = grid.length, cols = grid[0].length;\n int[][] distance = new int[rows][cols];\n boolean[][] visited = new boolean[rows][cols];\n Queue queue = new LinkedList<>();\n\n // Initialize: fill distances with -1, enqueue all sources\n for (int r = 0; r < rows; r++) {\n for (int c = 0; c < cols; c++) {\n if (grid[r][c] == sourceValue) {\n queue.offer(new int[]{r, c});\n visited[r][c] = true;\n distance[r][c] = 0;\n } else {\n distance[r][c] = -1;\n }\n }\n }\n\n int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};\n\n // BFS expansion\n while (!queue.isEmpty()) {\n int[] cell = queue.poll();\n int row = cell[0], col = cell[1];\n\n for (int[] dir : directions) {\n int nr = row + dir[0];\n int nc = col + dir[1];\n\n if (nr >= 0 && nr < rows && nc >= 0 && nc < cols\n && !visited[nr][nc]) {\n visited[nr][nc] = true;\n distance[nr][nc] = distance[row][col] + 1;\n queue.offer(new int[]{nr, nc});\n }\n }\n }\n\n return distance;\n }\n}\n```\n\n```python\nfrom collections import deque\nfrom typing import List\n\ndef shortest_distance_from_sources(grid: List[List[int]], source_value: int) -> List[List[int]]:\n \"\"\"\n Multi-source BFS on a grid.\n Computes shortest distance from each cell to the nearest source.\n\n Time Complexity: O(m * n)\n Space Complexity: O(m * n)\n \"\"\"\n rows, cols = len(grid), len(grid[0])\n distance = [[-1] * cols for _ in range(rows)]\n visited = [[False] * cols for _ in range(rows)]\n queue = deque()\n\n # Initialize: enqueue all sources\n for r in range(rows):\n for c in range(cols):\n if grid[r][c] == source_value:\n queue.append((r, c))\n visited[r][c] = True\n distance[r][c] = 0\n\n directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n\n # BFS expansion\n while queue:\n row, col = queue.popleft()\n\n for dr, dc in directions:\n nr, nc = row + dr, col + dc\n\n if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:\n visited[nr][nc] = True\n distance[nr][nc] = distance[row][col] + 1\n queue.append((nr, nc))\n\n return distance\n```\n\n```cpp\n#include \n#include \nusing namespace std;\n\n/**\n * Multi-source BFS on a grid.\n * Computes shortest distance from each cell to the nearest source.\n *\n * Time Complexity: O(m * n)\n * Space Complexity: O(m * n)\n */\nvector> shortestDistanceFromSources(vector>& grid,\n int sourceValue) {\n int rows = grid.size(), cols = grid[0].size();\n vector> distance(rows, vector(cols, -1));\n vector> visited(rows, vector(cols, false));\n queue> q;\n\n // Initialize: enqueue all sources\n for (int r = 0; r < rows; r++) {\n for (int c = 0; c < cols; c++) {\n if (grid[r][c] == sourceValue) {\n q.push({r, c});\n visited[r][c] = true;\n distance[r][c] = 0;\n }\n }\n }\n\n int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};\n\n // BFS expansion\n while (!q.empty()) {\n auto [row, col] = q.front();\n q.pop();\n\n for (auto& dir : directions) {\n int nr = row + dir[0];\n int nc = col + dir[1];\n\n if (nr >= 0 && nr < rows && nc >= 0 && nc < cols\n && !visited[nr][nc]) {\n visited[nr][nc] = true;\n distance[nr][nc] = distance[row][col] + 1;\n q.push({nr, nc});\n }\n }\n }\n\n return distance;\n}\n```\n\n```csharp\nusing System.Collections.Generic;\n\n///

\n/// Multi-source BFS on a grid.\n/// Computes shortest distance from each cell to the nearest source.\n///\n/// Time Complexity: O(m * n)\n/// Space Complexity: O(m * n)\n///

\npublic class MultiSourceBFS\n{\n public int[,] ShortestDistanceFromSources(int[,] grid, int sourceValue)\n {\n int rows = grid.GetLength(0), cols = grid.GetLength(1);\n int[,] distance = new int[rows, cols];\n bool[,] visited = new bool[rows, cols];\n Queue<(int row, int col)> queue = new Queue<(int, int)>();\n\n // Initialize: fill distances with -1, enqueue all sources\n for (int r = 0; r < rows; r++)\n {\n for (int c = 0; c < cols; c++)\n {\n if (grid[r, c] == sourceValue)\n {\n queue.Enqueue((r, c));\n visited[r, c] = true;\n distance[r, c] = 0;\n }\n else\n {\n distance[r, c] = -1;\n }\n }\n }\n\n int[][] directions = new int[][]\n {\n new int[] {0, 1}, new int[] {0, -1},\n new int[] {1, 0}, new int[] {-1, 0}\n };\n\n // BFS expansion\n while (queue.Count > 0)\n {\n var (row, col) = queue.Dequeue();\n\n foreach (var dir in directions)\n {\n int nr = row + dir[0];\n int nc = col + dir[1];\n\n if (nr >= 0 && nr < rows && nc >= 0 && nc < cols\n && !visited[nr, nc])\n {\n visited[nr, nc] = true;\n distance[nr, nc] = distance[row, col] + 1;\n queue.Enqueue((nr, nc));\n }\n }\n }\n\n return distance;\n }\n}\n```\n\n```go\npackage main\n\n// ShortestDistanceFromSources performs multi-source BFS on a grid.\n// Computes shortest distance from each cell to the nearest source.\n//\n// Time Complexity: O(m * n)\n// Space Complexity: O(m * n)\nfunc ShortestDistanceFromSources(grid [][]int, sourceValue int) [][]int {\n rows, cols := len(grid), len(grid[0])\n distance := make([][]int, rows)\n visited := make([][]bool, rows)\n for r := 0; r < rows; r++ {\n distance[r] = make([]int, cols)\n visited[r] = make([]bool, cols)\n for c := 0; c < cols; c++ {\n distance[r][c] = -1\n }\n }\n\n type cell struct{ row, col int }\n queue := []cell{}\n\n // Initialize: enqueue all sources\n for r := 0; r < rows; r++ {\n for c := 0; c < cols; c++ {\n if grid[r][c] == sourceValue {\n queue = append(queue, cell{r, c})\n visited[r][c] = true\n distance[r][c] = 0\n }\n }\n }\n\n directions := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}\n\n // BFS expansion\n for len(queue) > 0 {\n curr := queue[0]\n queue = queue[1:]\n\n for _, dir := range directions {\n nr, nc := curr.row+dir[0], curr.col+dir[1]\n\n if nr >= 0 && nr < rows && nc >= 0 && nc < cols &&\n !visited[nr][nc] {\n visited[nr][nc] = true\n distance[nr][nc] = distance[curr.row][curr.col] + 1\n queue = append(queue, cell{nr, nc})\n }\n }\n }\n\n return distance\n}\n```\n\n```rust\npub struct MultiSourceBFS;\n\nimpl MultiSourceBFS {\n /**\n * Multi-source BFS on a grid.\n * Computes shortest distance from each cell to the nearest source.\n *\n * Time Complexity: O(m * n)\n * Space Complexity: O(m * n)\n */\n pub fn shortest_distance_from_sources(grid: Vec>, source_value: i32) -> Vec> {\n let rows = grid.len();\n let cols = grid[0].len();\n let mut distance = vec![vec![-1; cols]; rows];\n let mut visited = vec![vec![false; cols]; rows];\n let mut queue: std::collections::VecDeque<(usize, usize)> = std::collections::VecDeque::new();\n\n // Initialize: fill distances with -1, enqueue all sources\n for r in 0..rows {\n for c in 0..cols {\n if grid[r][c] == source_value {\n queue.push_back((r, c));\n visited[r][c] = true;\n distance[r][c] = 0;\n }\n }\n }\n\n let directions: [(isize, isize); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)];\n\n // BFS expansion\n while let Some((row, col)) = queue.pop_front() {\n for &(dr, dc) in &directions {\n let nr = row as isize + dr;\n let nc = col as isize + dc;\n\n if nr >= 0\n && nr < rows as isize\n && nc >= 0\n && nc < cols as isize\n && !visited[nr as usize][nc as usize]\n {\n let nr = nr as usize;\n let nc = nc as usize;\n visited[nr][nc] = true;\n distance[nr][nc] = distance[row][col] + 1;\n queue.push_back((nr, nc));\n }\n }\n }\n\n distance\n }\n}\n```\n\n```javascript\n/**\n * Multi-source BFS on a grid.\n * Computes shortest distance from each cell to the nearest source.\n *\n * Time Complexity: O(m * n)\n * Space Complexity: O(m * n)\n *\n * @param {number[][]} grid\n * @param {number} sourceValue\n * @return {number[][]}\n */\nfunction shortestDistanceFromSources(grid, sourceValue) {\n const rows = grid.length, cols = grid[0].length;\n const distance = Array.from({length: rows}, () => Array(cols).fill(-1));\n const visited = Array.from({length: rows}, () => Array(cols).fill(false));\n const queue = [];\n let head = 0;\n\n // Initialize: enqueue all sources\n for (let r = 0; r < rows; r++) {\n for (let c = 0; c < cols; c++) {\n if (grid[r][c] === sourceValue) {\n queue.push([r, c]);\n visited[r][c] = true;\n distance[r][c] = 0;\n }\n }\n }\n\n const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];\n\n // BFS expansion\n while (head < queue.length) {\n const [row, col] = queue[head++];\n\n for (const [dr, dc] of directions) {\n const nr = row + dr;\n const nc = col + dc;\n\n if (nr >= 0 && nr < rows && nc >= 0 && nc < cols\n && !visited[nr][nc]) {\n visited[nr][nc] = true;\n distance[nr][nc] = distance[row][col] + 1;\n queue.push([nr, nc]);\n }\n }\n }\n\n return distance;\n}\n```\n\n```typescript\n/**\n * Multi-source BFS on a grid.\n * Computes shortest distance from each cell to the nearest source.\n *\n * Time Complexity: O(m * n)\n * Space Complexity: O(m * n)\n */\nfunction shortestDistanceFromSources(grid: number[][], sourceValue: number): number[][] {\n const rows: number = grid.length;\n const cols: number = grid[0].length;\n const distance: number[][] = Array.from({length: rows}, () => Array(cols).fill(-1));\n const visited: boolean[][] = Array.from({length: rows}, () => Array(cols).fill(false));\n const queue: [number, number][] = [];\n let head: number = 0;\n\n // Initialize: enqueue all sources\n for (let r = 0; r < rows; r++) {\n for (let c = 0; c < cols; c++) {\n if (grid[r][c] === sourceValue) {\n queue.push([r, c]);\n visited[r][c] = true;\n distance[r][c] = 0;\n }\n }\n }\n\n const directions: [number, number][] = [[0, 1], [0, -1], [1, 0], [-1, 0]];\n\n // BFS expansion\n while (head < queue.length) {\n const [row, col] = queue[head++];\n\n for (const [dr, dc] of directions) {\n const nr: number = row + dr;\n const nc: number = col + dc;\n\n if (nr >= 0 && nr < rows && nc >= 0 && nc < cols\n && !visited[nr][nc]) {\n visited[nr][nc] = true;\n distance[nr][nc] = distance[row][col] + 1;\n queue.push([nr, nc]);\n }\n }\n }\n\n return distance;\n}\n```\n\n\n### Code Explanation\n\nThe structure across all implementations is identical:\n\n1. **Initialization loop:** We scan the entire grid looking for source cells. Every source gets enqueued with distance 0 and marked as visited. Non-source cells start with distance -1 (unreachable until BFS reaches them).\n2. **Directions array:** The four-entry directions array encodes the four cardinal directions (right, left, down, up). This is a standard idiom for grid traversal.\n3. **BFS loop:** We dequeue a cell, check its four neighbors, and for each valid unvisited neighbor, compute its distance as the current cell's distance plus one. Then we mark it visited and enqueue it.\n4. **No level tracking needed here:** Unlike some BFS problems where you need to count levels explicitly, the distance array itself tracks the level for each cell. Each cell's distance is its parent's distance plus one.\n\n**Common Mistakes:**\n\n- Forgetting to mark sources as visited during initialization. This causes sources to be re-enqueued when a neighbor processes them, leading to incorrect distances.\n- Using a data structure with O(n) dequeue operations for the queue. For example, using a plain list with removal from the front in Python is O(n) per operation, which turns O(m*n) BFS into O((m*n)^2). Use a deque or a pointer-based approach instead.\n- Checking grid boundaries after accessing the array instead of before. Always validate indices before reading the grid cell.\n\n---\n\n## Complexity Analysis\n\n### Time Complexity\n\n**Overall:** O(m * n) for a grid, or O(V + E) for a general graph.\n\n- The initialization scan visits every cell once: O(m * n).\n- During BFS, each cell is enqueued and dequeued at most once, with constant work (4 neighbor checks) per cell.\n\nThe number of sources does not affect the time complexity. Whether you have 1 source or 10,000 sources, the BFS still visits each cell exactly once.\n\n### Space Complexity\n\n**Overall:** O(m * n)\n\n- The distance array: O(m * n).\n- The visited array: O(m * n). (Can be avoided if you modify the grid in place.)\n- The queue: O(m * n) in the worst case, when all cells are sources or when the BFS frontier spans the entire grid.\n\n---\n\n## Comparison with Related Approaches\n\nThe table below compares multi-source BFS against alternative approaches.\n\n\n| Approach | Time Complexity | Space Complexity | Correctness | When to Use |\n|---|---|---|---|---|\n| **Multi-source BFS** | O(V + E) | O(V) | Correct for unweighted graphs | Multiple sources, uniform edge weights, simultaneous expansion |\n| **Separate BFS from each source** | O(k * (V + E)) | O(V) | Correct but slow | Very few sources (k is small), or when you need per-source distances |\n| **Dijkstra from virtual super-source** | O((V + E) log V) | O(V) | Correct for weighted graphs | Sources at different \"starting costs,\" weighted edges |\n| **BFS from single source** | O(V + E) | O(V) | Wrong for multi-source problems | Only one source exists |\n\n\n### When to Choose Multi-Source BFS\n\n- All sources are equivalent (same starting distance of 0).\n- The graph is unweighted, or all edges have the same weight.\n- You need the shortest distance from each node to its nearest source.\n\n### When NOT to Use Multi-Source BFS\n\n- Sources have different starting costs (e.g., some fires started earlier than others). In this case, you need Dijkstra with a priority queue.\n- You need the shortest distance from each node to a specific source, not just the nearest one. In that case, run BFS from each source individually.\n- The graph has weighted edges with varying weights. Multi-source BFS assumes all edges have equal weight.\n\n---\n\n## Common Patterns and Applications\n\nMulti-source BFS appears in several recognizable patterns in interview problems. Once you can spot the pattern, the implementation follows the same template each time.\n\n### Pattern 1: Simultaneous Spread\n\n**Problem type:** Multiple entities spread to adjacent cells each time step. Find how long until everything is reached (or whether it is possible).\n\n**How multi-source BFS helps:** Enqueue all spreading entities at level 0. Each BFS level represents one time step. The answer is the maximum level reached (or -1 if some cells are unreachable).\n\n**Examples:** Rotting Oranges (LC 994), where rotten oranges spread rot. Shortest Bridge (LC 934), where you find all cells of one island, then BFS-expand toward the other island.\n\n### Pattern 2: Distance from Nearest Source\n\n**Problem type:** Given a grid with some special cells, compute the shortest distance from every cell to its nearest special cell.\n\n**How multi-source BFS helps:** Enqueue all special cells as sources. BFS computes the shortest distance from each cell to whichever source is closest.\n\n**Examples:** 01 Matrix (LC 542), where you find the distance from each cell to the nearest 0. Walls and Gates (LC 286), where you find the distance from each empty room to the nearest gate. Map of Highest Peak (LC 1765), where you assign heights based on distance from water cells.\n\n### Pattern 3: Boundary Expansion\n\n**Problem type:** Start from all boundary cells and expand inward.\n\n**How multi-source BFS helps:** Enqueue all boundary cells as sources. BFS expands inward, and you can use the distance values or the visited set for further processing.\n\n**Examples:** Surrounded Regions (LC 130), where you mark all O cells reachable from the boundary. Pacific Atlantic Water Flow (LC 417), where you expand from ocean boundaries inward.\n\n---\n\n## Key Takeaways\n\n- Multi-source BFS seeds the queue with every source at distance 0 and marks each one visited during initialization, then runs the same FIFO loop as standard single-source BFS. The only difference from single-source BFS is that step.\n- Because all sources start at level 0 and expand together, the first time BFS reaches a cell it has arrived from the nearest source along the shortest path. A single pass produces the minimum distance from each node to its nearest source.\n- The time complexity is O(V + E) for a graph or O(m * n) for a grid, and it does not depend on the number of sources. Visiting each cell once costs the same whether there is 1 source or 10,000.\n- Running a separate BFS from each of k sources and taking the per-cell minimum gives the same answer at O(k * (V + E)), so multi-source BFS is the faster choice when sources share a starting distance and edges are unweighted.\n- Use multi-source BFS for simultaneous spread problems like Rotting Oranges (LC 994) and for nearest-source distance problems like 01 Matrix (LC 542) and Walls and Gates (LC 286). Switch to Dijkstra from a virtual super-source when sources have different starting costs or edges carry varying weights.\n\n---\n\n# Quiz","pageType":"dsa"}

Get Premium