994. Pacific Atlantic Water Flow

EasyGraphsGridBFSDFS

Given an m x n grid of heights, water can flow from a cell to an orthogonally adjacent cell of equal or lower height. The Pacific ocean touches the top and left edges; the Atlantic touches the bottom and right edges. Return, sorted in row-major order, all cells [r, c] from which water can reach both oceans. The input is JSON {heights}.

Input: JSON {heights}.

Output: Nested array — the qualifying cells, sorted.

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]]
Explanation: Cells reaching both oceans.
Example 2
Input: {"heights":[[1]]}
Output: [[0,0]]
Explanation: Single cell touches both.
Example 3
Input: {"heights":[[2,1],[1,2]]}
Output: [[0,0],[0,1],[1,0],[1,1]]
Explanation: All reach both.

Constraints

Asked by

FlipkartAmazonAdobeGoogleMicrosoftMeta
Solve this problem in the editor →