Walls And Gates
Medium · Graphs
You are given a 2D grid representing a floor plan, where each cell is one of three values: -1 for a wall, 0 for a gate, or a very large number representing an empty room. Update the grid in place so that every empty room cell holds the length of the shortest path to the nearest gate, moving only up, down, left or right through non-wall cells. Cells that stay unreachable from any gate keep the large placeholder value. Return nothing, the grid itself is checked after the call.
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]]
Why: Each empty room is filled with the shortest distance to its nearest gate, walls stay -1 and gates stay 0.Input: rooms = [[-1]]
Output: [[-1]]
Why: The only cell is a wall, so nothing changes.Input: rooms = [[0]]
Output: [[0]]
Why: The only cell is already a gate.Constraints
1 <= rows, cols <= 100, grid values are only INF (2147483647), -1 (wall), or 0 (gate)
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Walls And Gates. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.