Java beat 90% solution


  • 2
    O

    My ides is sample, let water flow from four directions to the entire matrix, maintain a visited map for Pacific Ocean (left direction or top direction) and refresh it for Atlantic Ocean (from bottom direction or right direction). Then maintain a counter map, for each unvisited cell the flow reaches, increment its value by 1. Then we just need to find the cell with a value of 2, that's the cell that can both flow to Pacific Ocean and Atlantic Ocean.

    public class Solution {
        static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        public List<int[]> pacificAtlantic(int[][] matrix) {
            List<int[]> result = new ArrayList<int[]>();
            if(matrix.length == 0) return result;
            boolean[][] visited = new boolean[matrix.length][matrix[0].length];
            int[][] waterFlowCount = new int[matrix.length][matrix[0].length];
            for(int i = 0; i < matrix[0].length; i++){ // from top row
                dfs(matrix,0,i,visited, waterFlowCount);
            }
            for(int i = 0; i < matrix.length; i++){ // from left
                dfs(matrix,i,0,visited, waterFlowCount);
            }
    
            visited = new boolean[matrix.length][matrix[0].length];
            for(int i = 0; i < matrix[0].length; i++){ // from bottom
                dfs(matrix,matrix.length-1,i,visited, waterFlowCount);
            }
            for(int i = 0; i < matrix.length; i++){ // from right
                dfs(matrix,i,matrix[0].length-1,visited, waterFlowCount);
            }
    
            for(int i = 0; i < waterFlowCount.length; i++){
                for(int j = 0; j < waterFlowCount[0].length; j++){
                    if(waterFlowCount[i][j] == 2)
                        result.add(new int[]{i,j});
                }
            }
    
            return result;
        }
    
        public void dfs(int[][] matrix, int i, int j, boolean[][] visited, int[][] waterFlowCount){
            if(i >= matrix.length || i < 0 || j >= matrix[0].length || j < 0 || visited[i][j]) {
                return;
            }
            visited[i][j] = true;
            waterFlowCount[i][j]++;
            for(int[] dir : dirs){
                int nexti = i + dir[0];
                int nextj = j + dir[1];
                if(nexti >= 0 && nexti < matrix.length && nextj >= 0 && nextj < matrix[0].length && !visited[nexti][nextj] ) {
                   if(matrix[nexti][nextj] >= matrix[i][j]) dfs(matrix,nexti,nextj,visited,waterFlowCount); // has to be higher than the height of itself so when water poured on this cell can reach the ocean
                }
            }
        }
    }
    

  • 0

    good idea, I made a bit improvement:)

    static final int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> result = new ArrayList<int[]>();
        if(matrix.length == 0) return result;
        int n = matrix.length, m = matrix[0].length;
        int[][] waterFlowCount = new int[n][m];
        for(int i = 0; i < m; i++) dfs(matrix,0,i,waterFlowCount,Integer.MIN_VALUE, true, result);
        for(int i = 0; i < n; i++) dfs(matrix,i,0,waterFlowCount,Integer.MIN_VALUE, true, result);
        for(int i = 0; i < m; i++) dfs(matrix,n-1,i,waterFlowCount,Integer.MIN_VALUE, false, result);
        for(int i = 0; i < n; i++) dfs(matrix,i,m-1,waterFlowCount,Integer.MIN_VALUE, false, result);
        return result;
    }
    public void dfs(int[][] matrix, int x, int y, int[][] waterFlowCount, int prevheight, boolean pacific, List<int[]> result){
        int n = matrix.length, m = matrix[0].length;
        if(x<0||x>=n||y<0||y>=m||prevheight>matrix[x][y]) return;
        if(pacific){// from top/left
            if(waterFlowCount[x][y]==1) return;//already visited by 1
            waterFlowCount[x][y]=1;//mark it as visited by 1
        }
        else {// from bottom/right
            if(waterFlowCount[x][y]>=2) return;//already visited by 2
            waterFlowCount[x][y]=waterFlowCount[x][y]==0?2:3;//mark it as visited by 2; if it is already visited by 1, mark it as 3 (visited by both 1 and 2)
            if(waterFlowCount[x][y]==3) result.add(new int[]{x,y});//check if visited by both 1 and 2
        }
        for(int[]d:dir) dfs(matrix, x+d[0], y+d[1], waterFlowCount, matrix[x][y], pacific, result);
    }

Log in to reply
 

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