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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Walls and Gates and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →