Sweaty Imposter

Walls and Gates

MediumGraph BFS/DFSNeetCode 150MidOpen on LeetCodeUpdated

You're given an m x n grid of rooms. Each cell is -1 for a wall, 0 for a gate, or INF (2^31 - 1 = 2147483647) for an empty room. Fill each empty room, in place, with the number of steps to its nearest gate, moving up, down, left, or right. A room that can't reach any gate keeps the value INF.

Examples

rooms = [[INF,-1,0],[INF,INF,INF],[0,-1,INF]] returns [[2,-1,0],[1,2,1],[0,-1,2]]

input
INF-10INFINFINF0-1INF
output
2-101210-12

Each room takes the distance to whichever gate is closer. The center room is two steps from both gates.

rooms = [[0,INF,INF,INF]] returns [[0,1,2,3]]

In a single row, each room's distance grows by one step from the gate.

rooms = [[INF,-1],[-1,0]] returns [[INF,-1],[-1,0]]

Walls cut the top-left room off from the only gate, so it stays INF.

Constraints

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

Hints

Hint 1

Searching outward from every empty room repeats a lot of work. Which cells should the search start from?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Run one breadth-first search (BFS) from all the gates at once. Put every gate in the queue, then pop cells in order, and for each neighbor that still holds INF, set it to the current cell's value plus 1 and enqueue it. BFS reaches cells in order of distance from the nearest source, so the first value written into a room is final. Walls and filled rooms never hold INF, so they're skipped without a visited set. O(m * n) time and O(m * n) space for the queue.

Time

O(m * n)

Space

O(m * n)

Pitfall

Running a separate search from each gate or from each room. Each search can cover the whole grid, so the cost grows to O(g * m * n) for g gates. Seed one queue with every gate instead.

Solutions

class Solution {
    private static final int INF = Integer.MAX_VALUE;

    public void wallsAndGates(int[][] rooms) {
        int m = rooms.length, n = rooms[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (rooms[r][c] == 0) queue.add(new int[]{r, c});
            }
        }
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int r = cell[0] + d[0], c = cell[1] + d[1];
                if (r < 0 || r >= m || c < 0 || c >= n || rooms[r][c] != INF) continue;
                rooms[r][c] = rooms[cell[0]][cell[1]] + 1;
                queue.add(new int[]{r, c});
            }
        }
    }
}
Drill This