Java DFS beats 75%


  • 0
    G
    public class Solution {
        private int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        public List<int[]> pacificAtlantic(int[][] matrix) {
             int rows = matrix.length;
             if (rows == 0) return new ArrayList<int[]>();
             int cols = matrix[0].length;
             if (cols == 0) return new ArrayList<int[]>();
        
             List<int[]> result = new ArrayList<int[]>();
             int[][] states = new int[rows][cols];
             for(int r = 0; r < rows; r++){
                 Flood(matrix, states, rows, cols, r, 0, 1);
                 Flood(matrix, states, rows, cols, r, cols-1, 2);
             }
             for(int c = 0; c < cols; c++){
                 Flood(matrix, states, rows, cols, 0, c, 1);
                 Flood(matrix, states, rows, cols, rows-1, c, 2);
             }
        
             for(int r = 0; r < rows; r++)
             for(int c = 0; c < cols; c++){
                if (states[r][c] == 3) result.add(new int[]{r, c});
             }
             return result;
        }
        
          private void Flood(int[][] matrix, int[][] states, int rows, int cols, int r, int c, int v){
              if ((states[r][c] & v) != 0) return;
          
              states[r][c] |= v;
              for(int i = 0; i < dirs.length; i++){
                 int nr = r + dirs[i][0];
                 int nc = c + dirs[i][1];
        
                 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || matrix[nr][nc] < matrix[r][c]) continue;
                 Flood(matrix, states, rows, cols, nr, nc, v);
             }
          }
    }
    

Log in to reply
 

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