Pacific Atlantic Water Flow

Rain falls on an island of heights. Water flows to neighbours of equal or lower height. The Pacific touches the top and left edges; the Atlantic touches the bottom and right. Return every cell whose water can reach both oceans.

A way to picture it

Pouring water from every single cell and watching where it goes is slow. Flip it around: let each ocean climb uphill from its own coast. Any cell both oceans can climb to can drain into both.

How to approach it

Run one search from all Pacific border cells and one from all Atlantic border cells, moving only to neighbours at least as high. Answer = cells reached by both.

Example

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

Complexity: O(m · n) time and O(m · n) space. Each search visits each cell at most once.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.