All problems

Pacific Atlantic Water Flow

Medium · graph traversal

You are given a rectangular grid of integers, heights, where heights[r][c] is the height of the land at row r, column c. The Pacific ocean touches the top and left edges of the grid. The Atlantic ocean touches the bottom and right edges.

Rain falls on a cell and then flows. Water moves from a cell to a neighbour above, below, left or right, but only if that neighbour is at the same height or lower. Water on an edge cell can also flow straight into the ocean that touches that edge. A corner cell therefore touches two edges, and a cell in a one-row or one-column grid touches several.

Return every cell from which water can reach both oceans, as a list of [row, col] pairs. The pairs may be returned in any order.

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

Water from [2, 2] (height 5) runs up through the 3 above it to the top edge, and right through a 3 and a 1 to the right edge.

Example 2

Input: heights = [[1]]

Output: [[0, 0]]

The only cell touches all four edges, so it reaches both oceans.

Example 3

Input: heights = [[2, 1], [1, 2]]

Output: [[0, 0], [0, 1], [1, 0], [1, 1]]

Every cell sits on the border. The cell [0, 0] touches the Pacific and flows down to [1, 0], which touches the Atlantic.

Constraints