Java DFS solution


  • 2
    • Start with top and left edges as immediately reachable from Pacific
    • DFS from these points, water falls into any higher ground from around a point
    • Do the same for Atlantic
    • Take the set intersection
    public class Solutions{
        private static class Coord {
            int x;
            int y;
    
            public Coord(int x, int y) {
                this.x = x;
                this.y = y;
            }
    
            int[] toint() {
                return new int[]{x, y};
            }
    
            @Override
            public String toString() {
                return x + "," + y;
            }
        }
    
        public List<int[]> pacificAtlantic(int[][] matrix) {
            List<int[]> list = new ArrayList<>();
            if (matrix.length < 1) return list;
            Queue<Coord> pacificOrigins = new LinkedList<>();
            Queue<Coord> atlanticOrigins = new LinkedList<>();
            for (int i = 0; i < matrix.length; i++) {
                pacificOrigins.add(new Coord(i, 0));
                atlanticOrigins.add(new Coord(i, matrix[0].length - 1));
            }
            for (int i = 0; i < matrix[0].length; i++) {
                pacificOrigins.add(new Coord(0, i));
                atlanticOrigins.add(new Coord(matrix.length - 1, i));
            }
            Map<String, Coord> pacific = reachables(matrix, pacificOrigins);
            Map<String, Coord> atlantic = reachables(matrix, atlanticOrigins);
            pacific.keySet().forEach(str -> {
                if (atlantic.containsKey(str)) {
                    list.add(atlantic.get(str).toint());
                    System.out.println(str);
                }
            });
            return list;
        }
    
        private Map<String, Coord> reachables(int[][] matrix, Queue<Coord> q) {
            Map<String, Coord> visited = new HashMap<>();
            q.forEach(origin -> visited.put(origin.toString(), origin));
            while (!q.isEmpty()) {
                Coord curr = q.poll();
                List<Coord> nexts = next(curr, matrix);
                for (Coord coord : nexts) {
                    if (!visited.containsKey(coord.toString())) {
                        q.add(coord);
                    }
                    visited.put(coord.toString(), coord);
                }
            }
            return visited;
        }
    
        private List<Coord> next(Coord coord, int[][] matrix) {
            List<Coord> list = new ArrayList<>();
            int x = (coord.x);
            int y = (coord.y);
            int h = matrix[x][y];
            if (x > 0 && x < matrix.length && matrix[x - 1][y] >= h) {
                list.add(new Coord(x - 1, y));
            }
            if (x >= 0 && x + 1 < matrix.length && matrix[x + 1][y] >= h) {
                list.add(new Coord(x + 1, y));
            }
            if (y > 0 && y < matrix[0].length && matrix[x][y - 1] >= h) {
                list.add(new Coord(x, y - 1));
            }
            if (y >= 0 && y + 1 < matrix[0].length && matrix[x][y + 1] >= h) {
                list.add(new Coord(x, y + 1));
            }
            return list;
        }
    }
    

Log in to reply
 

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