Graphs Grids as graphs

438. Pacific Atlantic Water Flow

You are given a map of an island as a grid of integers, heights, with m rows and n columns. heights[i][j] is the height of the land in row i, column j. The Pacific Ocean touches the top and left edges of the island, and the Atlantic Ocean touches the bottom and right edges.

Rain falls on every cell. Water flows from a cell to a neighbour up, down, left or right whose height is less than or equal to its own. Water on a cell at the edge of the grid also flows into the ocean on that side.

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

Example 1

Input: heights = [[1, 2, 2, 3], [3, 2, 3, 4], [2, 4, 5, 3], [6, 1, 1, 4]]

Output: [[0,3],[1,3],[2,1],[2,2],[3,0]]

Explanation: Water from the 4 at row 2, column 1 runs left to the Pacific and down to the Atlantic, and the 5 beside it runs through that 4. The top-right and bottom-left corners touch both oceans, and the 4 at row 1, column 3 flows into the 3 in the top-right corner.

Example 2

Input: heights = [[3, 1, 4]]

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

Explanation: With one row, every cell is on both the top edge and the bottom edge.

Example 3

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

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

Explanation: Water flows between equal heights, so every 5 can run along the border to both oceans. The 1 in the middle is lower than all its neighbours, so its water stays there.

Check your understanding

Work out the answer for this input before you write any code.

heights = [[3, 3, 1], [2, 4, 3], [5, 1, 2]]

Constraints

m == heights.length, n == heights[i].length
1 ≤ m, n ≤ 300
0 ≤ heights[i][j] ≤ 10⁹

Clarifying questions

What you would ask an interviewer before writing any code.