DSA problem
Walls and Gates
You are given an m x n grid rooms initialised with these three possible values: -1 represents a wall or obstacle, 0 represents a gate, and 2147483647 (INT_MAX) 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 INT_MAX. The distance is the minimum number of 4-directional moves through empty rooms.
The naive approach — running a separate BFS from every empty room — costs O((m * n)^2) and is far too slow for large grids. The standard improvement is the multi-source BFS pattern: rather than searching outward from each room toward gates, search outward from every gate simultaneously through empty rooms.
We enqueue every gate at distance 0 and run BFS. When we pop a cell with distance d, we visit each 4-neighbour: if the neighbour is an empty room (still INT_MAX), we set its value to d + 1 and enqueue it. We never enter walls and we never overwrite an already-shorter distance, because BFS visits cells in non-decreasing order of distance.
This in-place algorithm modifies the grid as the answer and runs in O(m * n) time with O(m * n) extra space for the queue. Every cell is enqueued at most once because as soon as it receives a finite distance it is no longer INT_MAX and is skipped on later visits.
Examples
rooms = [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]] where INF = 2147483647[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]rooms = [[-1]][[-1]]rooms = [[2147483647,2147483647],[2147483647,2147483647]][[2147483647,2147483647],[2147483647,2147483647]]Constraints
- m == rooms.length
- n == rooms[i].length
- 1 <= m, n <= 250
- rooms[i][j] is either -1, 0, or 2147483647.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.