PATTERN 14B: Multi-Source BFS / Level Expansion

D

Qubits of DPK

April 11, 2026

Core DSA

Core Idea (lock this)

“All sources expand
You are not choosing paths.
You are measuring distance / time / layers.
If DFS explores depth,
BFS measures minimum steps.
And if multiple starting points exist,
push them all at once.

How to Recognize This Pattern (CRITICAL)

You should instantly think Multi-Source BFS when:
  • The question asks for:
  • You see:
  • Multiple cells / nodes start in the same initial state
Trigger words:
  • “nearest”
  • “shortest”
  • “minimum moves”
  • “distance from all”
  • “time to spread”

30 MUST-DO INTERVIEW PROBLEMS

(10 Easy → 10 Medium → 10 Hard)

EASY (Distance = Level Intuition)

Goal: connect BFS levels to time.
  1. #
    Rotting Oranges – LC 994
  2. #
    01 Matrix – LC 542
  3. #
    Walls and Gates – LC 286
  4. #
    As Far from Land as Possible – LC 1162
  5. #
    Nearest Exit from Entrance in Maze – LC 1926
  6. #
    Shortest Path in Binary Matrix – LC 1091
  7. #
    Distance of Nearest Cell Having 1 – GFG
  8. #
    Steps by Knight – GFG
  9. #
    Open the Lock – LC 752
  10. #
    Minimum Genetic Mutation – LC 433
Now EASY builds:
  • Grid BFS
  • Multi-source initialization
  • Distance arrays
  • Level counting
No tree noise.

️ MEDIUM (State + Multi-Source)

Now state modeling becomes important.
  1. #
    Shortest Bridge – LC 934
  2. #
    Word Ladder – LC 127
  3. #
    Pacific Atlantic Water Flow – LC 417
  4. #
    Bus Routes – LC 815
  5. #
    Snakes and Ladders – LC 909
  6. #
    Parallel Courses – LC 1136
  7. #
    Minimum Time to Collect All Apples – LC 1443
  8. #
    Find All Groups of Farmland – LC 1992
  9. #
    Minimum Number of Vertices to Reach All Nodes – LC 1557
  10. #
    Shortest Path with Alternating Colors – LC 1129
This section locks:
  • Graph BFS
  • Reverse BFS
  • Layer-by-layer propagation
  • Modified state transitions

HARD (State Explosion & Hybrid BFS)

Now the real challenge begins.
  1. #
    Shortest Path to Get All Keys – LC 864
  2. #
    Word Ladder II – LC 126
  3. #
    Shortest Path in Grid with Obstacles Elimination – LC 1293
  4. #
    Minimum Cost to Make at Least One Valid Path – LC 1368
  5. #
    Escape the Spreading Fire – LC 2258
  6. #
    The Maze III – LC 499
  7. #
    Smallest Sufficient Team (BFS state view) – LC 1125
  8. #
    Jump Game IV – LC 1345
  9. #
    Minimum Moves to Move a Box to Target – LC 1263
  10. #
    Path with Minimum Effort (Binary Search + BFS view) – LC 1631
Now HARD tests:
  • State compression
  • Bitmask BFS
  • Multi-dimensional visited
  • 0-1 BFS variants
  • Hybrid BFS + other pattern

The ONE Rule That Wins Interviews

Always be able to answer:
“What does
If the answer is:
  • one minute
  • one move
  • one distance unit
BFS is correct.

Common Interview Mistakes

  • Running BFS from one source instead of many
  • Mixing DFS where minimum distance is required
  • Forgetting to mark visited when enqueuing
  • Counting steps incorrectly (off-by-one levels)

INTERVIEW REVISION CARD — Pattern 14B

1️⃣ Pattern in One Line

"Push all sources at once and expand level by level — BFS measures minimum distance/time."

2️⃣ Recognize It When...

  • Minimum steps/time/distance from multiple starting points
  • Trigger words: "spreading", "nearest", "minimum moves", "time to reach all", "infection"
  • Multiple cells/nodes start in same initial state
  • Grid problems with simultaneous expansion

3️⃣ Don't Confuse With...

  • Graph DFS (P14A) → DFS for reachability; BFS for minimum distance
  • Dijkstra (P14A Hard) → weighted shortest path; BFS for unweighted
  • Single-source BFS → one starting point vs multi-source (all pushed at once)

4️⃣ Approach in 3 Steps

  1. #
    Push ALL source nodes into queue simultaneously at level 0
  2. #
    Process level by level — increment distance after each level
  3. #
    Mark visited when ENQUEUING (not dequeuing) to avoid duplicates

5️⃣ Invariant to Maintain

"Every node in the queue at level L is exactly L steps away from the nearest source."

6️⃣ Complexity to Justify

  • Time: O(V + E) — each node/cell visited once
  • Space: O(V) — queue holds at most all nodes
  • Why: BFS guarantees shortest path in unweighted graphs

7️⃣ Edge Cases to Always Check

  • No valid path exists — return -1
  • Source = destination
  • All cells already visited/blocked
  • Grid boundaries — check before enqueuing
  • Mark visited when enqueuing, NOT dequeuing

8️⃣ One Line to Say in Interview

"I'll initialize BFS with all sources simultaneously — each level represents one unit of distance, guaranteeing minimum steps in O(V+E)."