Multi-Source BFS in Coding Interviews: Rotting Oranges, Walls and Gates, and Nearest Distance Grids
3 views
Many grid problems in coding interviews look like they need a breadth-first search from every cell, which would be far too slow. The trick interviewers want to see is multi-source BFS: put every starting point into the queue at once and let the search expand outward in layers. Once you recognize the pattern, a whole family of questions becomes routine.
The core idea
Ordinary BFS starts from one node and finds the shortest distance to everything else in an unweighted graph. Multi-source BFS starts from a set of nodes simultaneously. Conceptually, you add a virtual super-source connected to all of them with zero-cost edges. In code you simply push all sources into the queue with distance 0 before the loop starts. Each cell is still visited at most once, so the total cost stays O(rows x cols).
Rotting Oranges
Each minute, fresh oranges next to a rotten one become rotten. Return the minutes until none are fresh, or -1 if impossible. Count the fresh oranges and enqueue every rotten orange first. Process the queue level by level; each level is one minute. When you rot a neighbor, decrement the fresh count. At the end, if fresh is still above zero, some orange was unreachable, so return -1. A common bug is counting one extra minute after the last level; only increment the clock when the level actually rotted something.
Walls and Gates / 01 Matrix
Fill each empty room with its distance to the nearest gate, or each cell of a binary matrix with its distance to the nearest zero. The naive approach runs BFS from every empty room. The better approach reverses the direction: start from all gates (or all zeros) together. The first time BFS reaches a cell is guaranteed to be through the nearest source, so you can write the distance and never revisit it.
Variants worth practicing
- As Far From Land As Possible: start from all land cells and return the largest distance reached in water.
- Shortest Bridge: find one island with DFS, push all its cells, then BFS until you touch the second island.
- Pacific Atlantic Water Flow: run two multi-source searches from each ocean's border and intersect the results.
How to talk through it
Interviewers care about the reasoning as much as the code. Say out loud why single-source BFS from every cell is O((rc)^2) and why reversing the search fixes it. Mention that BFS gives shortest paths only because every edge has equal weight; if weights differ, you would need Dijkstra or 0-1 BFS with a deque. Call out edge cases before coding: an empty grid, no sources at all, and no targets at all.
Practicing under real conditions
Grid BFS is easy to understand on paper and surprisingly easy to fumble live, mostly in the level-counting and boundary checks. Timed practice with a friend or a mock interviewer helps. Some candidates also use Linkjob AI (https://linkjob.ai), which gives real-time help during live job interviews and technical interviews, to keep their explanation structured when nerves kick in. Whatever tools you use, the goal is the same: recognize the multi-source pattern in the first minute and spend the rest of the time writing clean, bug-free code.