🚀 Phases 1–4 are live — Days 1–13 + Day 17 are fully written. See the roadmap →
Day 10 - Graph Traversal (DFS and BFS)Practice QuestionsWalls and Gates

Walls and Gates medium

Description

You are given an m x n grid rooms where:

  • -1 represents a wall or an obstacle.
  • 0 represents a gate.
  • INF (use 2^31 - 1 as a sentinel) represents an empty room.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, leave the value as INF.

Examples

> Case 1:
    Input:                            Output:
    INF -1   0  INF                     3 -1  0  1
    INF INF INF -1                      2  2  1 -1
    INF -1  INF -1                      1 -1  2 -1
     0  -1  INF INF                     0 -1  3  4

Constraints

  • m == rooms.length
  • n == rooms[i].length
  • 1 <= m, n <= 250

The naive approach (slow)

For every empty room, run BFS to find the nearest gate. With K empty rooms and G gates, that’s O(K · m · n) in the worst case — too slow for large grids.

The multi-source BFS trick

Flip the problem: start BFS from all gates simultaneously, expanding outward layer by layer. Every cell’s distance-to-nearest-gate equals the BFS layer it gets reached in.

Why this works: BFS from a single source assigns the minimum distance to each cell. With multiple sources, each cell still gets its minimum distance — to the nearest source.

Start: queue = all gates (distance 0)

Layer 1: every empty cell adjacent to a gate becomes 1
Layer 2: every unvisited empty cell adjacent to a Layer-1 cell becomes 2
...

Walls (-1) are never enqueued — they block expansion.
Unreachable cells stay at INF.

This collapses the O(K · m · n) naive bound to O(m · n) total.

Code

The rooms[nr][nc] == INF check serves double duty: it skips walls (which are -1), it skips already-visited cells (which now have a finite distance), and it skips gates (which have distance 0). One condition covers all three.

Why we don’t need a separate visited set

The grid is the visited set. Once a cell is filled with a distance, we never revisit it. This is a common space-saving trick in multi-source BFS on grids — mutate the grid in place.

The same template, three problems

ProblemWhat the “source” isWhat gets filled in
Walls and GatesGates (0s)Distance to nearest gate
Rotting OrangesInitially-rotten cells (2s)Time until each cell rots
01 MatrixAll 0 cellsDistance to nearest 0
As Far From Land as PossibleLand cellsDistance from each water cell to nearest land

Every one of these is literally the same code with different inputs and outputs. Multi-source BFS is one of the highest-leverage patterns in the graph chapter — recognize it once and you’ve unlocked a family.

Why not DFS?

DFS would assign whatever distance comes from the first path it explores — not the minimum. To get the minimum via DFS you’d need to revisit cells whenever you find a shorter path → potential blow-up to O(2^(m+n)) in pathological cases. BFS is the right tool because it visits cells in non-decreasing distance order.

Analysis

  • Time: O(m · n) — every cell enqueued at most once.
  • Space: O(m · n) for the queue in the worst case.
Pacific Atlantic Water FlowShortest Path in Binary Matrix