Micro-questions over the BFS pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.

This bank is about recognising the problem shape. The mechanics are in the BFS bank.


A. The shape

1. What phrasing almost always means BFS?

Answer

“Minimum steps / levels / time to reach X” in an unweighted setting.

2. Give the physical metaphor.

Answer

Ripples expanding outward from a pebble dropped in water.

3. Give the social-network illustration.

Answer

Finding the shortest connection path between two people — check all paths of length 1, then length 2, and so on.


B. Level-order

4. What is the key trick that turns plain BFS into level-order BFS?

Answer

level_size = len(queue) — a snapshot of exactly how many nodes are in this level, taken before processing any of them.

5. What happens without it?

Answer

You process the nodes but lose track of which level each one belonged to.

6. Why is len(queue) exactly the level width at that moment?

Answer

Because at the top of the iteration the queue holds every node of the current level and nothing else — the previous level has all been popped and the next level has not been enqueued yet.


C. Multi-source BFS

7. What is multi-source BFS?

Answer

Starting BFS from all initial sources simultaneously — putting all of them in the queue at distance 0 before the loop begins.

8. What does it compute?

Answer

For every cell, the distance to the nearest source — in one pass, at the same cost as a single-source run.

9. Give the canonical problem.

Answer

Rotting Oranges — every rotten orange starts in the queue at once, and they spread simultaneously.

10. Why would running single-source BFS from each source be wrong as well as slow?

Answer

Slow because it is passes — and you would then have to take the minimum across all of them per cell, which multi-source gives you for free by construction.

11. What must you check at the end of Rotting Oranges?

Answer

Whether any fresh oranges remain — if so, they were unreachable and the answer is , not the elapsed minutes.


D. Trade-offs

12. What does BFS guarantee that DFS does not?

Answer

Shortest paths in unweighted graphs.

13. Why does BFS guarantee that?

Answer

It exhausts distance entirely before touching , so the first time it reaches a node it has done so by the fewest possible edges.

14. What is BFS’s memory cost, and on what shape is it worst?

Answer

The queue can grow to — worst on wide graphs, where DFS would use far less.

15. Summarise the pattern in one sentence.

Answer

If the question is “how few steps”, expand in rings with a queue — snapshot the level size when levels matter, and seed every source at once when the answer is a distance to the nearest of many.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to LeetCode Patterns — University-Style Teaching Notes