Java solution with PriorityQueue


  • 0
    Y

    The idea:

    Step 1, calculate all the cells that could flow to the pacific.
    First, we add the cells on the first column and first row, which can flow to the ocean obviously, to a priority queue in the order of the height of the cells.
    Second, poll a cell from the queue, check its neighbors, and mark the neighbors that with higher or equal height.
    Step 2, calculate all the cells that could flow to the atlantic with the same approach, but start from the last column and last row.
    Step 3, based on the results from Steps 1 and 2, generate the cells that could flow to both oceans.

    public class Solution {
        public class Node {
            int x;
            int y;
            int val;
            public Node(int x, int y, int val){
                this.x = x;
                this.y = y;
                this.val = val;
            }
        }
        
        public List<int[]> pacificAtlantic(int[][] matrix) {
            List<int[]> res = new ArrayList<int[]>();
            
            if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0)
                return res;
                
            int m = matrix.length;
            int n = matrix[0].length;
            
            boolean[][] pacific = new boolean[m][n];
            boolean[][] atlantic = new boolean[m][n];
            boolean[][] visited = new boolean[m][n];
            
            PriorityQueue<Node> pq = new PriorityQueue<>(1, new Comparator<Node>(){
                public int compare(Node a, Node b) {
                    return a.val - b.val;
                }
            });
            
            for (int i = 0; i < n; i++) {
                pacific[0][i] = true;
                visited[0][i] = true;
                pq.offer(new Node(0, i, matrix[0][i]));
            }
    
            for (int i = 0; i < m; i++) {
                pacific[i][0] = true;
                visited[i][0] = true;
                pq.offer(new Node(i, 0, matrix[i][0]));
            } 
            
            while (!pq.isEmpty())
                helper(matrix, pacific, visited, pq, m, n);
            
            for (boolean[] v : visited)
                Arrays.fill(v, false);
                
            for (int i = 0; i < n; i++) {
                atlantic[m - 1][i] = true;
                visited[m - 1][i] = true;
                pq.offer(new Node(m - 1, i, matrix[m - 1][i]));
            }
    
            for (int i = 0; i < m; i++) {
                atlantic[i][n - 1] = true;
                visited[i][n - 1] = true;
                pq.offer(new Node(i, n - 1, matrix[i][n - 1]));
            }
            
            while (!pq.isEmpty())
                helper(matrix, atlantic, visited, pq, m, n);
    
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (pacific[i][j] && atlantic[i][j])
                        res.add(new int[]{i, j});
    
            return res;
        }
        
        private void helper (int[][] matrix, boolean[][] ocean, boolean[][] visited, PriorityQueue<Node> pq, int m, int n) {
            Node tmp = pq.poll();
            
            int row = tmp.x;
            int col = tmp.y;
            
            int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            
            for (int[] dir : dirs) {
                int x = row + dir[0];
                int y = col + dir[1];
                
                if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y]) {
                    visited[x][y] = true;
                    if (matrix[x][y] >= matrix[row][col]) {
                        ocean[x][y] = true;
                        pq.offer(new Node (x, y, matrix[x][y]));
                    }
                }
            }
        }
    }
    

Log in to reply
 

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