5 ms Java solution (beat 100%)


  • 1
    T

    It's flood-fill approach. The key is to stop flooding when you reach the room with less than or equal to the current value (except 0). This is because its neighbors are already filled with a smaller value.

        public void wallsAndGates(int[][] rooms) {
            for(int i = 0, n = rooms.length; i < n; i++) {
                for(int j = 0, m = rooms[i].length; j < m; j++) {
                    if(rooms[i][j] == 0) {
                        flood(rooms, i, j, 0);
                    }
                }
            }
        }
        
        public void flood(int[][] rooms, int i, int j, int val) {
            if(i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length) return;
            if(rooms[i][j] > val || val == 0) {
                rooms[i][j] = val;
                flood(rooms, i - 1, j, val + 1);
                flood(rooms, i + 1, j, val + 1);
                flood(rooms, i, j - 1, val + 1);
                flood(rooms, i, j + 1, val + 1);
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.