LeetCode : 286. Walls and Gates

[congr]

https://leetcode.com/problems/walls-and-gates/

[congr]

O(MN) - 2D GRID MN

class Solution {
    class Point {
        int y, x, n;
        Point(int y, int x, int n) {
            this.y = y;
            this.x = x;
            this.n = n;
        }
    }

    public void wallsAndGates(int[][] rooms) {
        if (rooms.length == 0) return;

        int M = rooms.length, N = rooms[0].length;
        Queue<Point> q = new LinkedList();

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (rooms[i][j] == 0) q.add(new Point(i, j, 0));
            }
        }

        while(!q.isEmpty()) {
            Point p = q.remove();

            for (int d = 0; d < 4; d++) {
                int ny = p.y + dy[d], nx = p.x + dx[d];
                if (inside(ny, nx, M, N) && rooms[ny][nx] > p.n) {
                    q.add(new Point(ny, nx, p.n+1));
                    rooms[ny][nx] = p.n+1; // or rooms[ny][nx] = rooms[y][x]+1
                }
            }
        }
    }

    int[] dy = {-1,0,1,0};
    int[] dx = {0,-1,0,1};

    boolean inside(int y, int x, int M, int N) {
        if (y >= 0 && x >= 0 && y < M && x < N) return true;
        return false;
    }
}

[congr]

Without Point class, a bit shorter

class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms.length == 0) return;

        int M = rooms.length, N = rooms[0].length;
        Queue<int[]> q = new LinkedList();

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (rooms[i][j] == 0) q.add(new int[]{i, j});
            }
        }

        while(!q.isEmpty()) {
            int[] p = q.remove();

            for (int d = 0; d < 4; d++) {
                int ny = p[0] + dy[d], nx = p[1] + dx[d];
                if (inside(ny, nx, M, N) && rooms[ny][nx] == Integer.MAX_VALUE) {
                    q.add(new int[] {ny, nx});
                    rooms[ny][nx] = rooms[p[0]][p[1]] + 1;
                }
            }
        }
    }

    int[] dy = {-1,0,1,0};
    int[] dx = {0,-1,0,1};

    boolean inside(int y, int x, int M, int N) {
        if (y >= 0 && x >= 0 && y < M && x < N) return true;
        return false;
    }
}