37ms Java Solution using BFS


  • 0
    public class Solution {
        public List<int[]> pacificAtlantic(int[][] matrix) {
            if(matrix == null || matrix.length == 0) return new ArrayList<>();
    
            Set<Position> pacific = findFloodArea(matrix, 0, 0, true);
            Set<Position> atlantic = findFloodArea(matrix, matrix.length - 1, matrix[0].length - 1, false);
    
            List<int[]> res = new ArrayList<>();
            pacific.retainAll(atlantic);
            for(Position pos: pacific) res.add(new int[]{pos.row, pos.col});
            return res;
        }
    
        private Set<Position> findFloodArea(int[][] matrix, int row, int col, boolean direction) {
            Set<Position> res = new HashSet<>();
            Queue<Position> queue = new LinkedList<>();
            int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
            boolean[][] visited = new boolean[matrix.length][matrix[0].length];
    
            for(int j = 0; j < matrix[0].length; j++) {
                Position tmp = new Position(row, j);
                queue.add(tmp);
                res.add(tmp);
                visited[tmp.row][tmp.col] = true;
            }
    
            int start = direction ? 1 : 0, end = direction ? matrix.length : matrix.length - 1;
            for(int i = start; i < end; i++) {
                Position tmp = new Position(i, col);
                queue.add(tmp);
                res.add(tmp);
                visited[tmp.row][tmp.col] = true;
            }
    
            while(!queue.isEmpty()) {
                Position curr = queue.poll();
                for(int[] dir: dirs) {
                    int newRow = curr.row + dir[0], newCol = curr.col + dir[1];
                    if(newRow >= 0 && newCol >= 0 && newRow < matrix.length
                            && newCol < matrix[0].length && !visited[newRow][newCol]) {
                        Position newPos = new Position(newRow, newCol);
                        if(matrix[newRow][newCol] >= matrix[curr.row][curr.col]) {
                            queue.add(newPos);
                            res.add(newPos);
                            visited[newPos.row][newPos.col] = true;
                        }
                    }
                }
            }
            return res;
        }
    
        class Position {
            int row, col;
            public Position(int row, int col) {
                this.row = row;
                this.col = col;
            }
    
            public boolean equals(Object other) {
                Position o = (Position)other;
                return this.row == o.row && this.col == o.col;
            }
    
            public int hashCode() {
                return 31 * row + col;
            }
    
            public String toString() {
                return "(" + row + "," + col + ")";
            }
        }
    }
    

Log in to reply
 

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