Pacific Atlantic Water Flow

medium

There is an m x n rectangular island that borders both the Pacific Ocean and the Atlantic Ocean. The Pacific touches the island's left and top edges, and the Atlantic touches its right and bottom edges.

You are given an m x n integer matrix heights. Water can flow from a cell to a neighbouring cell 4-directionally if the neighbour's height is less than or equal to the current cell's height.

Return a list of grid coordinates from which rain water can flow to both oceans.

Test Cases

Copy an input into the main harness and Run to verify

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

Expected Output

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

Input

heights = [[1]]

Expected Output

[[0,0]]

Explanation: A single cell touches both oceans.

Constraints

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

Hints

Hint 1 — click to reveal

Searching downhill from every cell repeats enormous amounts of work.

Hint 2 — click to reveal

Reverse the flow: start at each ocean's edge and walk *uphill* to find everything that drains into it.

Java Compiler