Run it in your head. What does this return?

[[0, 0], [0, 1], [1, 0], [1, 1]]

[[1, 0], [0, 1], [1, 0], [1, 1]]

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]

Pacific Atlantic Water Flow

Medium

Search inland from both oceans

Problem

Given a grid of heights, return cells from which water can flow to both the Pacific (top/left) and Atlantic (bottom/right) oceans.

In simple words

Flow inward from each ocean's border to higher-or-equal cells; the overlap can reach both oceans.

The idea

Rather than testing every cell's outflow, start from the ocean edges and walk inland to cells of equal or greater height — those are the cells that can reach that ocean. The answer is the intersection of the two reachable sets.

The trick

Reverse the flow: search uphill from the borders.
Two visited grids, one per ocean; the answer is where both are true.
O(rows × cols) instead of a search per cell.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(m*n)spaceO(m*n)

1DFS/BFS inward from Pacific edges and from Atlantic edges (uphill)2return cells reached by both

Input

array: [5, 5]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

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]]
Explanation:: Cells that can drain to both oceans.

Example 2

Input:: heights = [[1]]
Output:: [[0, 0]]
Explanation:: The single cell touches both oceans.

Example 3

Input:: heights = [[2,1],[1,2]]
Output:: [[0, 0], [0, 1], [1, 0], [1, 1]]
Explanation:: Corners reach both sides.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.