AceYourInterviews
Checking sign-in…

100. Pacific Atlantic Water Flow

AdvancedReverse downhill edges from each ocean, then intersect two independent reachability sets

Water can move orthogonally from a cell to a neighbor of equal or lower height. Find cells from which some route reaches the Pacific boundary and some route reaches the Atlantic boundary.

The two routes need not be the same route. A cell must satisfy both reachability conditions, and equal heights permit flow.

Example 1

Input

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

Output

[[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]

Explanation: A cell must have a valid downhill route to each ocean, possibly along different paths.

Example 2

Input

[[MIN,MAX],[MAX,MIN]]

Output

[[0,1],[1,0]]

Explanation: Each MAX cell touches both oceans; the low opposite-corner cells cannot climb to reach the other ocean.

Example 3

Input

[[5,5],[5,5]]

Output

[[0,0],[0,1],[1,0],[1,1]]

Explanation: Equal-height edges permit flow across the plateau.

Constraints

  • 0 <= heights.length <= 105
  • 0 <= total heights cells <= 105
  • -231 <= heights[r][c] <= 231 - 1
  • All rows have equal length and are non-null.
Hints
Hint 1

Can you search from each ocean rather than from every cell?

Hint 2

Reverse every legal downhill edge into an uphill/equal edge.

Hint 3

Run two independent boundary searches and intersect their masks.

Practice on LeetCode ↗
Code
Saved on this deviceLn 1, Col 1

Two independent reverse-flow searches

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