Skip to content
AI360Xpert
Beta
Back to Graphs
Difficulty: MediumGraphs

Pacific Atlantic Water Flow

Problem in Plain English

Rain falls on an island grid where water only flows downhill into neighbours that are at most as tall. The Pacific touches the top and left edges and the Atlantic touches the bottom and right edges, and every cell whose water can reach both oceans must be returned.

Problem Statement

You are given an m x n integer matrix heights where heights[r][c] is the height above sea level of one island cell. Rain falling on a cell flows into a directly neighbouring cell to the north, south, east, or west whenever that neighbour is at most as tall as the current cell, and keeps flowing while the rule holds.

The Pacific Ocean touches the top and left borders of the island, and the Atlantic Ocean touches the bottom and right borders. Return every coordinate [r, c] whose rain can reach both oceans.

Constraints

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

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

Seven cells drain to both oceans. Cell (2,2) reaches the Pacific through (1,2) and (0,2), and reaches the Atlantic through (2,3) and (2,4).

Example 2

Input
heights = [[2,1]]
Output
[[0,0],[0,1]]

In a one-row island every cell touches both the top Pacific border and the bottom Atlantic border directly. Both coordinates qualify regardless of their heights; no downhill movement is required.

Example 3

Input
heights = [[1,2,1],[2,0,2],[1,2,1]]
Output
[[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]]

The center 0 cannot climb to any neighbour, so it reaches neither ocean. Top-left 1 and bottom-right 1 cannot leave their own ocean side. The other two corners touch both oceans directly; each border 2 can descend toward corners on both sides.

Example 4

Input
heights = [[7]]
Output
[[0,0]]

The single cell touches all four borders, so it reaches both oceans directly.

Intuition

Water may split into several routes; one route reaching each ocean is enough. In Example 1, height 5 at (2,2) can descend toward the top through (1,2), and toward the right through (2,3). Instead of repeating these downhill paths for every source, reverse their arrows: start at each ocean border and climb into equal or higher neighbours. A reverse path certifies a downhill path back to that ocean. Intersect the two independent reachable sets.

Approaches

Downhill DFS Per Cell

Solution Details

Reveal Downhill DFS Per Cell: intuition, complexity, and code

Hints

Hint 1
Running a search from every cell repeats the same downhill paths many times, so look for a way to share the work between cells.
Hint 2
Flip the direction: rain flows downhill into an ocean, so starting at an ocean border and walking only uphill visits exactly the cells that can drain there.
Hint 3
Run one uphill search from the Pacific borders and one from the Atlantic borders, then return the cells marked by both searches.

Edge Cases

  • A 1 by 1 grid qualifies immediately. In any one-row or one-column grid every cell touches both oceans directly.
  • Equal heights allow travel in both directions; a flat grid returns every cell. Visited marking prevents infinite plateau cycles.
  • A strictly low interior basin surrounded by higher cells may reach neither ocean, even though those higher cells qualify.
  • The top-right and bottom-left corners always touch both oceans directly. A cell needs separate valid routes to both oceans, not one route that visits both.

Common Mistakes and Interview Tips

  • Using <= in the border search follows forward flow instead of reversed flow; reverse neighbours must be >=.
  • Using strict inequalities loses equal-height paths. Only four orthogonal directions are legal; diagonals are not.
  • Sharing markers between oceans changes intersection into mixed reachability. Resetting markers for each border seed instead repeats work.
  • Mutating heights to mark visits destroys the height comparisons needed by later sources or the other ocean.
  • Recursive DFS may exceed ordinary Python or JavaScript call stacks on a 200 by 200 plateau. Use an explicit stack and mark at push time.
  • Interview tip: prove the path-reversal equivalence and count each cell once per ocean before claiming linear time.

Key Takeaway

When many sources must reach one destination, reverse the search and grow outward from the destination once instead of once per source.