Walls and Gates

NeetCode: Walls and Gates · LeetCode: 286. Walls and Gates · Difficulty: Medium

A grid has three kinds of cells: -1 is a wall, 0 is a gate, and INF (2147483647, Integer.MAX_VALUE) is an empty room. Fill each empty room with the number of steps to its nearest gate (moving up, down, left, right). If a room cannot reach any gate, leave it as INF.

Example

Text

INF  -1   0  INF        3 -1  0  1
INF INF INF  -1         2  2  1 -1
INF  -1 INF  -1   -->   1 -1  2 -1
  0  -1 INF INF         0 -1  3  4

A Java int[][] is an array of row arrays, and a method can change its cells in place. The solution below follows LeetCode's signature void wallsAndGates(int[][] rooms) and edits the grid it receives. ArrayDeque is Java's queue, and int[] pairs hold a cell's row and column.

Brute force: BFS from every empty room

For each empty room, run a BFS outward until the first gate is found; the BFS level at that moment is the distance. Every room runs its own search. The distances are collected first and written after all searches finish, so one search never sees another's result.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

class Solution {
    private static final int INF = Integer.MAX_VALUE;
    private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // Steps from (sr, sc) to the nearest gate, or -1 when no gate is reachable.
    private int nearestGate(int[][] grid, int sr, int sc) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        visited[sr][sc] = true;
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{sr, sc, 0});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (grid[cur[0]][cur[1]] == 0) {
                return cur[2];
            }
            for (int[] d : DIRS) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n
                        && grid[nr][nc] != -1 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    queue.add(new int[]{nr, nc, cur[2] + 1});
                }
            }
        }
        return -1;
    }

    public void wallsAndGates(int[][] rooms) {
        List<int[]> answers = new ArrayList<>();
        for (int r = 0; r < rooms.length; r++) {
            for (int c = 0; c < rooms[0].length; c++) {
                if (rooms[r][c] == INF) {
                    int d = nearestGate(rooms, r, c);
                    if (d != -1) {
                        answers.add(new int[]{r, c, d});
                    }
                }
            }
        }
        for (int[] a : answers) {
            rooms[a[0]][a[1]] = a[2];
        }
    }
}

public class Main {
    static final int INF = Integer.MAX_VALUE;

    static void show(int[][] grid) {
        for (int[] row : grid) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < row.length; c++) {
                if (c > 0) {
                    sb.append(' ');
                }
                sb.append(row[c] == INF ? "INF" : String.valueOf(row[c]));
            }
            System.out.println(sb);
        }
    }

    public static void main(String[] args) {
        int[][] grid = {
            {INF, -1, 0, INF},
            {INF, INF, INF, -1},
            {INF, -1, INF, -1},
            {0, -1, INF, INF},
        };
        new Solution().wallsAndGates(grid);
        show(grid);
        int[][] lonely = {{INF, -1, 0}};
        new Solution().wallsAndGates(lonely);
        show(lonely);
    }
}

Output

Time: O((m * n)^2) worst case. Space: O(m * n) for the visited matrix and queue of one search.

Optimal: multi-source BFS from the gates

Search from the gates instead of from the rooms. Push all gates into the queue with distance 0. BFS then reaches each room first via its nearest gate, so the first time a room is filled, that value is final. Only rooms still equal to INF are unvisited, so the grid itself doubles as the visited set. Rooms cut off from every gate are never touched and stay INF.

Java

import java.util.ArrayDeque;

class Solution {
    private static final int INF = Integer.MAX_VALUE;
    private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public void wallsAndGates(int[][] rooms) {
        if (rooms.length == 0) {
            return;
        }
        int m = rooms.length, n = rooms[0].length;
        ArrayDeque<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});
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int d = rooms[cur[0]][cur[1]];
            for (int[] dir : DIRS) {
                int nr = cur[0] + dir[0], nc = cur[1] + dir[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] == INF) {
                    rooms[nr][nc] = d + 1;
                    queue.add(new int[]{nr, nc});
                }
            }
        }
    }
}

public class Main {
    static final int INF = Integer.MAX_VALUE;

    static void show(int[][] grid) {
        for (int[] row : grid) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < row.length; c++) {
                if (c > 0) {
                    sb.append(' ');
                }
                sb.append(row[c] == INF ? "INF" : String.valueOf(row[c]));
            }
            System.out.println(sb);
        }
    }

    public static void main(String[] args) {
        int[][] grid = {
            {INF, -1, 0, INF},
            {INF, INF, INF, -1},
            {INF, -1, INF, -1},
            {0, -1, INF, INF},
        };
        new Solution().wallsAndGates(grid);
        show(grid);
        int[][] lonely = {{INF, -1, 0}};
        new Solution().wallsAndGates(lonely);
        show(lonely);
    }
}

Output

d + 1 never overflows: d is the value of a cell that was already filled (a gate or a finished room), never INF, so it stays far below Integer.MAX_VALUE. Time: O(m * n). Space: O(m * n) for the queue.