Leetcode 417) Pacific Atlantic Water Flow

21 Oct 2021 in Algorithms

My Answer

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        //visited array
        //PO array, AO array..
        int[][] ocean = new int[heights.length][heights[0].length];
        //Initialize array, boolean, every values would be false at first.
        boolean[][] visited = new boolean[heights.length][heights[0].length];
        int val=1;
        for(int i =0;i<visited.length;i++){
            dfs(heights,visited,ocean,val,i,0);
        }
        for(int j=0;j<visited[0].length;j++){
            dfs(heights,visited,ocean,val,0,j);
        }
        visited = new boolean[heights.length][heights[0].length];
        val=10;
        for(int i =0;i<visited.length;i++){
            dfs(heights,visited,ocean,val,i,visited[0].length-1);
        }
        for(int j=0;j<visited[0].length;j++){
            dfs(heights,visited,ocean,val,visited.length-1,j);
        }       
        List<List<Integer>>  pairs = new ArrayList<>();
        for(int i =0;i<visited.length;i++){
            for(int j=0;j<visited[0].length;j++){
                if(ocean[i][j]==11){
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(i);
                    tmp.add(j);
                    pairs.add(tmp);
                }
            }
        }
        return pairs;
    }
    public void dfs(int[][] heights,boolean[][] visited, int[][] ocean,int val ,int i , int j){
        if(visited[i][j]==true){
            return;
        }
        visited[i][j]=true;
        ocean[i][j]+=val;
        int[][] pos =  {{-1,0},{1,0},{0,-1},{0,1}}  ;
        for(int[] coords : pos){
            int x=i+ coords[0];
            int y=j+ coords[1];
            if(x>=0 && x<visited.length && y>=0 && y<visited[0].length){
                if(heights[x][y]>=heights[i][j]){
                    dfs(heights,visited,ocean,val,x,y);
                }
            }
        }   
    }
}

Other Answer