Pacific Atlantic Water Flow

Problem

Given an m × n matrix of land heights, water can flow from any cell to neighbors with height ≤ current. The Pacific touches the top + left edges, Atlantic touches the bottom + right. Return coordinates that can drain to BOTH oceans.

Constraints

• 1 ≤ m, n ≤ 200
• 0 ≤ heights[i][j] ≤ 10⁵

Approach — Graphs

This is a Graphs problem. The idea: explore the graph with BFS or DFS, marking nodes visited so you never process one twice. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(V + E) time.

Solution code

Python

class Solution:
    def pacificAtlantic(self, heights):
        if not heights:
            return []
        m, n = len(heights), len(heights[0])
        pac, atl = set(), set()
        def dfs(r, c, seen, prev):
            if (r < 0 or c < 0 or r >= m or c >= n or (r, c) in seen
                    or heights[r][c] < prev):
                return
            seen.add((r, c))
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                dfs(r+dr, c+dc, seen, heights[r][c])
        for i in range(m):
            dfs(i, 0, pac, heights[i][0]); dfs(i, n-1, atl, heights[i][n-1])
        for j in range(n):
            dfs(0, j, pac, heights[0][j]); dfs(m-1, j, atl, heights[m-1][j])
        return [[r, c] for r in range(m) for c in range(n) if (r, c) in pac and (r, c) in atl]

Java

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

        // Pacific touches the top and left edges; Atlantic the bottom and right.
        for (int r = 0; r < rows; r++) {
            dfs(heights, pacific, r, 0);
            dfs(heights, atlantic, r, cols - 1);
        }
        for (int c = 0; c < cols; c++) {
            dfs(heights, pacific, 0, c);
            dfs(heights, atlantic, rows - 1, c);
        }

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

    private void dfs(int[][] heights, boolean[][] visited, int r, int c) {
        visited[r][c] = true;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] d : directions) {
            int nr = r + d[0];
            int nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= heights.length || nc >= heights[0].length) {
                continue;
            }
            if (visited[nr][nc]) {
                continue;
            }
            if (heights[nr][nc] < heights[r][c]) {
                continue;
            }
            dfs(heights, visited, nr, nc);
        }
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.