Java BFS solution, 26ms


  • 0
    H

    The idea is searching the units with greater height starting from the four edges. Not yet optimized:

    public class Solution {
        public List<int[]> pacificAtlantic(int[][] matrix) {
            List<int[]> res=new ArrayList<>();
            if (matrix.length==0) return res;
            int m=matrix.length, n=matrix[0].length;
            int[][] pacific=new int[m][n];
            int[][] atlantic=new int[m][n];
            boolean[][] visited=new boolean[m][n];
            Queue<int[]> q=new LinkedList<>();
           //check the pacific part
            for (int i=0;i<m;i++) q.add(new int[]{i,0});
            for (int i=1;i<n;i++) q.add(new int[]{0,i});
            int[] dx={0,0,1,-1}, dy={1,-1,0,0};
            while (!q.isEmpty()){
                int[] pos=q.poll();
                pacific[pos[0]][pos[1]]=1;
                for (int k=0;k<4;k++){
                    int x=pos[0]+dx[k], y=pos[1]+dy[k];
                if (x<0 || y<0 || x==m || y==n || visited[x][y]==true || matrix[x][y]<matrix[pos[0]][pos[1]] || pacific[x][y]==1) continue;
                    visited[x][y]=true;
                    q.add(new int[]{x,y});
                }
            }
            //check the atlantic part
            visited=new boolean[m][n];
            for (int i=0;i<m;i++) q.add(new int[]{i,n-1});
            for (int i=0;i<n-1;i++) q.add(new int[]{m-1,i}); 
            while (!q.isEmpty()){
                int[] pos=q.poll();
                atlantic[pos[0]][pos[1]]=1;
                for (int k=0;k<4;k++){
                    int x=pos[0]+dx[k], y=pos[1]+dy[k];
                if (x<0 || y<0 || x==m || y==n || visited[x][y]==true || matrix[x][y]<matrix[pos[0]][pos[1]] || atlantic[x][y]==1) continue;
                    visited[x][y]=true;
                    q.add(new int[]{x,y});
                }
            }
            for (int i=0;i<m;i++){
                for (int j=0;j<n;j++){
                    if (pacific[i][j]==1 && atlantic[i][j]==1) res.add(new int[]{i,j});
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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