AAlgoLoopSpaced repetition for LeetCode
MEDIUMBFS / DFSLeetCode ↗

Walls and Gates

The key idea

Run one breadth-first search from ALL gates at once. Seed the queue with every gate (distance 0) before expanding. Because BFS spreads in rings of equal distance, the first time a wave reaches an empty room it arrives by the shortest path, so the first value written is final and rooms are never revisited.

Problem

You are given an m x n grid rooms initialized with three possible values: -1 marks a wall or obstacle, 0 marks a gate, and 2147483647 (treated as infinity, INF) marks an empty room. Fill each empty room with the distance to its nearest gate, where distance is the number of steps moving up, down, left, or right. If it is impossible for an empty room to reach any gate, leave it as INF. You must modify the grid in place.

Constraints

Examples

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

Complexity

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

See the full solution

410310
Step-by-step visualization
Start free →

More BFS / DFS problems