Pacific Atlantic Water Flow

Medium · Graphs

You are given a grid of integers representing terrain heights, with the Pacific ocean touching the top and left edges and the Atlantic ocean touching the bottom and right edges. Water at a cell can flow to any of the four orthogonally adjacent cells only if that neighbor's height is less than or equal to the current cell's height. Return the coordinates [row, col] of every cell from which water can eventually reach both oceans. The order of the returned coordinates does not matter.

Examples

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]]
Why:    Each listed cell has a downhill (non-increasing) path to both the top/left edge and the bottom/right edge.

Input:  heights = [[1]]
Output: [[0,0]]
Why:    The single cell touches both oceans simultaneously since it sits on every edge.

Input:  heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]
Why:    Every cell can reach both oceans through some non-increasing path in this small grid.

Constraints

1 <= number of rows, columns <= 200, 0 <= heights[r][c] <= 10^5

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Pacific Atlantic Water Flow

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Pacific Atlantic Water Flow. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.