Pacific Atlantic Water Flow: the idea to remember.

The core insight

Search uphill from each ocean border. Return the intersection of the two visited sets.

Why it works

A downhill path from a cell to an ocean becomes an uphill path when reversed. Two independent reachability searches identify exactly the desired cells.

The mistake to avoid

Reverse the height comparison when traversing from the ocean. Equal height moves remain valid.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

List<List<Integer>> pacificAtlantic(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
    for (int r = 0; r < m; r++) { flood(heights, r, 0, pac); flood(heights, r, n - 1, atl); }
    for (int c = 0; c < n; c++) { flood(heights, 0, c, pac); flood(heights, m - 1, c, atl); }
    List<List<Integer>> out = new ArrayList<>();
    for (int r = 0; r < m; r++) for (int c = 0; c < n; c++)
        if (pac[r][c] && atl[r][c]) out.add(Arrays.asList(r, c));
    return out;
}
void flood(int[][] h, int r, int c, boolean[][] seen) {
    if (seen[r][c]) return;
    Deque<int[]> queue = new ArrayDeque<>(); queue.add(new int[]{r,c}); seen[r][c] = true;
    int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!queue.isEmpty()) {
        int[] cell = queue.remove();
        for (int[] d : directions) {
            int nr = cell[0] + d[0], nc = cell[1] + d[1];
            if (nr >= 0 && nr < h.length && nc >= 0 && nc < h[0].length
                && !seen[nr][nc] && h[nr][nc] >= h[cell[0]][cell[1]]) {
                seen[nr][nc] = true; queue.add(new int[]{nr,nc});
            }
        }
    }
}

Make the next connection