243. Pacific Atlantic Water Flow

Instead of asking whether each cell can reach an ocean, flip it: start at the ocean borders and climb inward to cells of equal or greater height. Cells reached from both oceans are the answer.

Reverse the flow

Checking every cell's downhill path to an ocean is expensive and repetitive. Instead, run DFS from the ocean edges inward, moving to a neighbour only when its height is ≥ the current cell (water could have flowed down the other way). Do this from the Pacific borders (top row, left column) and the Atlantic borders (bottom row, right column) separately.

A cell reachable in both traversals can send water to both oceans.

Walk-through

dfs(r, c, visited, prevHeight):
    if oob or visited or heights[r][c] < prevHeight: return
    visited.add((r,c))
    for each neighbour: dfs(neighbour, visited, heights[r][c])
run from Pacific edges -> pacific set
run from Atlantic edges -> atlantic set
answer = cells in pacific ∩ atlantic

Complexity

• Time: O(m·n) — each cell visited at most twice.
• Space: O(m·n) for the two visited sets and recursion.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private int rows, cols;
    private int[][] heights;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        rows = heights.length;
        cols = heights[0].length;
        boolean[][] pacific = new boolean[rows][cols];
        boolean[][] atlantic = new boolean[rows][cols];

        for (int c = 0; c < cols; c++) {
            dfs(0, c, pacific, Integer.MIN_VALUE);
            dfs(rows - 1, c, atlantic, Integer.MIN_VALUE);
        }
        for (int r = 0; r < rows; r++) {
            dfs(r, 0, pacific, Integer.MIN_VALUE);
            dfs(r, cols - 1, atlantic, Integer.MIN_VALUE);
        }

        List<List<Integer>> res = new ArrayList<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (pacific[r][c] && atlantic[r][c]) {
                    res.add(Arrays.asList(r, c));
                }
            }
        }
        return res;
    }

    private void dfs(int r, int c, boolean[][] ocean, int prevHeight) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || ocean[r][c] || heights[r][c] < prevHeight) {
            return;
        }
        ocean[r][c] = true;
        dfs(r + 1, c, ocean, heights[r][c]);
        dfs(r - 1, c, ocean, heights[r][c]);
        dfs(r, c + 1, ocean, heights[r][c]);
        dfs(r, c - 1, ocean, heights[r][c]);
    }
}