Skip to main content

286. Walls and Gates

medium

Fill each empty room in a grid with the distance to its nearest gate. Multi-source BFS starting from every gate at once — the first time you reach an empty cell is by definition the shortest distance.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given an m x n grid rooms initialized with these three possible values: -1 represents a wall or an obstacle, 0 represents a gate, and INF represents an empty room (the value 2^31 - 1 is used to represent INF since you may assume the distance to a gate is less than 2147483647). Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Constraints

  • m == rooms.length
  • n == rooms[i].length
  • 1 <= m, n <= 250
  • rooms[i][j] is -1, 0, or 2^31 - 1.

Examples

Example 1

Input
rooms = [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]]
Output
[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Example 2

Input
rooms = [[-1]]
Output
[[-1]]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Single-source BFS from every empty room is O((m*n)^2) — too slow. What if you started from the gates instead?

Hint 2

All gates are distance 0. Push them all into a BFS queue at once and expand outward, writing the current distance into each unvisited empty cell.

Hint 3

Multi-source BFS guarantees the first time you reach a cell is via the shortest path from any source — no need to revisit.

Solution approach

Reveal approach

Multi-source BFS. First pass: scan the grid and push every cell with value 0 (a gate) into a queue. Then run BFS — pop a cell at distance d, attempt to fill each of its 4 in-bounds neighbors that are still INF with d+1, and push those into the queue. Walls (-1) and already-filled cells (anything < INF) are skipped. Because all sources start at distance 0 simultaneously, the first time you touch a cell is via the shortest path from the closest gate. No revisits needed. Cells unreachable from any gate stay INF. O(m*n) time and space — each cell is enqueued and processed at most once.

Complexity

Time
O(m*n)
Space
O(m*n)

Related patterns

  • graph-bfs
  • multi-source-bfs
  • matrix

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

More Graphs practice problems

See all Graphs problems →