Pacific Atlantic Water Flow

Medium Problem 105 of 151 Java and Python

Problem

An m × n island has heights heights[r][c]. The Pacific touches the top and left edges; the Atlantic touches the bottom and right edges.

Rain flows from a cell to a neighbour (up, down, left, right) if the neighbour's height is less than or equal to the current height, and from edge cells into the adjacent ocean. Return all cells from which water can reach both oceans.

Example 1

Input: heights = [[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]]
Output: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]

Example 2

Input: heights = [[1]]
Output: [[0, 0]]

Constraints

1 ≤ m, n ≤ 200
0 ≤ heights[r][c] ≤ 10⁵

Explanation

Simulating water from every cell repeats work. Reverse the flow: start at each ocean's edge and walk uphill (to neighbours with height ≥ the current). Every cell reached can drain into that ocean.

Do it once for each ocean; the answer is the cells reached by both searches.

Approach 1 · Naive

Search downhill from every cell

Time O((m · n)²)
Space O(m · n)

From each cell, DFS downhill and check whether you can reach a Pacific edge and an Atlantic edge.

For each cell, run a DFS following non-increasing heights, with its own visited set.
Track whether the search reaches the top/left edge and the bottom/right edge.

Java

import java.util.*;

class Solution {
    private int m;
    private int n;
    private boolean pacific;
    private boolean atlantic;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m = heights.length;
        n = heights[0].length;
        List<List<Integer>> result = new ArrayList<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                pacific = false;
                atlantic = false;
                flow(heights, r, c, new boolean[m][n]);
                if (pacific && atlantic) {
                    result.add(List.of(r, c));
                }
            }
        }
        return result;
    }

    private void flow(int[][] h, int r, int c, boolean[][] seen) {
        seen[r][c] = true;
        pacific |= r == 0 || c == 0;
        atlantic |= r == m - 1 || c == n - 1;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int[] d : dirs) {
            int nr = r + d[0];
            int nc = c + d[1];
            if (nr >= 0 && nc >= 0 && nr < m && nc < n && !seen[nr][nc] && h[nr][nc] <= h[r][c]) {
                flow(h, nr, nc, seen);
            }
        }
    }
}

Python

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        m, n = len(heights), len(heights[0])
        result = []
        for r0 in range(m):
            for c0 in range(n):
                seen, stack = {(r0, c0)}, [(r0, c0)]
                pacific = atlantic = False
                while stack:
                    r, c = stack.pop()
                    pacific |= r == 0 or c == 0
                    atlantic |= r == m - 1 or c == n - 1
                    for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                        if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in seen and heights[nr][nc] <= heights[r][c]:
                            seen.add((nr, nc))
                            stack.append((nr, nc))
                if pacific and atlantic:
                    result.append([r0, c0])
        return result

Approach 2 · Optimal

Climb uphill from each ocean

Time O(m · n)
Space O(m · n)

DFS from all Pacific edge cells and from all Atlantic edge cells, moving to neighbours at least as high. Return cells reached by both.

Start climb from every top-row and left-column cell into pacific, and every bottom-row and right-column cell into atlantic.
climb(r, c): mark it; recurse into unvisited neighbours with height ≥ the current one.
Collect cells marked in both grids.

Java

import java.util.*;

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        for (int r = 0; r < m; r++) {
            climb(heights, r, 0, pacific);
            climb(heights, r, n - 1, atlantic);
        }
        for (int c = 0; c < n; c++) {
            climb(heights, 0, c, pacific);
            climb(heights, m - 1, c, atlantic);
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (pacific[r][c] && atlantic[r][c]) {
                    result.add(List.of(r, c));
                }
            }
        }
        return result;
    }

    private void climb(int[][] h, int r, int c, boolean[][] reached) {
        if (reached[r][c]) {
            return;
        }
        reached[r][c] = true;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int[] d : dirs) {
            int nr = r + d[0];
            int nc = c + d[1];
            if (nr >= 0 && nc >= 0 && nr < h.length && nc < h[0].length && h[nr][nc] >= h[r][c]) {
                climb(h, nr, nc, reached);
            }
        }
    }
}

Python

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        m, n = len(heights), len(heights[0])

        def climb(starts):
            reached, stack = set(starts), list(starts)
            while stack:
                r, c = stack.pop()
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if (0 <= nr < m and 0 <= nc < n and (nr, nc) not in reached
                            and heights[nr][nc] >= heights[r][c]):
                        reached.add((nr, nc))
                        stack.append((nr, nc))
            return reached

        pacific = climb([(r, 0) for r in range(m)] + [(0, c) for c in range(n)])
        atlantic = climb([(r, n - 1) for r in range(m)] + [(m - 1, c) for c in range(n)])
        return [[r, c] for r in range(m) for c in range(n) if (r, c) in pacific and (r, c) in atlantic]

Complexity compared

Approach	Time	Space
Naive Search downhill from every cell	O((m · n)²)	O(m · n)
Optimal Climb uphill from each ocean	O(m · n)	O(m · n)

Key takeaways

Reversing the direction of a search (from targets instead of sources) often turns many searches into one.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem