java dfs version. simple idea


  • 0
    Y

    Based on the idea that DFS could find reachability of node in graph, we do DFS from the nodes on the 4 borders of the graph.
    In the end, the nodes both reachable from Pacific and Atlantic could be found.
    BTW, because the size is not exceed 150, we could use a boolean[] to mark.

        private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        private boolean[] mark = new boolean[150 * 150 + 150];
        private Set<Integer> touchPacific = new HashSet<>();
        private List<int[]> res = new ArrayList<>();
    
        /*
            pacific: true --> find the reachability of Pacific  false: Atlantic    
        */
        private void reachOcean(int r, int c, int[][] matrix, boolean pacific) {
            int key = r * 150 + c;
            mark[key] = true;
    
            if (pacific) touchPacific.add(key);
            else if (touchPacific.contains(key)) res.add(new int[]{r, c});
    
            for (int[] d: dirs) {
                int r0 = r + d[0];
                int c0 = c + d[1];
                if (r0 < 0 || r0 >= m || c0 < 0 || c0 >= n || mark[r0 * 150 + c0] || matrix[r0][c0] < matrix[r][c]) {
                    continue;
                }
                reachOcean(r0, c0, matrix, pacific);
            }
        }
    
        public List<int[]> pacificAtlantic(int[][] matrix) {
            m = matrix.length;
            if (0 == m) return res;
            
            n = matrix[0].length;
            if (0 == n) return res;
    
            // top:
            for (int c = 0; c < n; ++c) {
                if(!mark[c]) reachOcean(0, c, matrix, true);
            }
    
            // left:
            for (int r = 0; r < m; ++r) {
                if(!mark[r*150]) reachOcean(r, 0, matrix, true);
            }
    
            mark = new boolean[150 * 150 + 150];
            // right:
            for (int r = 0; r < m; ++r) {
                if(!mark[r*150 + n - 1]) reachOcean(r, n - 1, matrix, false);
            }
    
            // bottom
            for (int c = 0; c < n; ++c) {
                if(!mark[(m - 1) * 150 + c]) reachOcean(m - 1, c, matrix, false);
            }
            return  res;
        }
    
    

Log in to reply
 

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