Pacific Atlantic Water Flow

Depth-First Search·Medium

There is an m x n rectangular island that borders both the Pacific Ocean (top and left edges) and the Atlantic Ocean (bottom and right edges). The island is partitioned into a grid of square cells. heights[r][c] is the height above sea level of the cell at (r, c).

The island receives heavy rain, and rainwater flows from a cell to a neighboring cell (north, south, east, or west) if the neighbor's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into that ocean.

Return a 2D list of grid coordinates [r, c] such that water can flow from (r, c) to both the Pacific and Atlantic oceans.

For determinism, the result must be sorted lexicographically (ascending by r, ties by c).

Examples

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]]

Input: heights = [[1]]

Output: [[0,0]]

Constraints

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 10^5

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Sign up free Sign in

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Depth-First Search
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.

Sign up to solve this problem