Skip to main content

417. Pacific Atlantic Water Flow

medium

Find cells in a grid from which water can flow to both the Pacific (top/left edges) and the Atlantic (bottom/right edges). Classic multi-source BFS/DFS — invert the problem and start from the edges, not the cells.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges. The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c). Water can flow from a cell to its neighboring cell directly north, south, east, or west if the neighboring cell's height is less than or equal to the current cell's height. Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic 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]]

Example 2

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

Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Forward simulation from each cell would be O((m*n)^2). Can you invert the flow?

Hint 2

Run two reverse BFS/DFS — one starting from every Pacific edge cell, one from every Atlantic edge cell. From an edge cell, traverse to neighbors whose height is >= current (because water can flow downhill to here, it can reach the ocean from here).

Hint 3

Take the intersection: cells reachable from BOTH simulations are the answer.

Solution approach

Reveal approach

Reverse the flow. Maintain two boolean grids pacific and atlantic. Seed pacific with every cell in the top row and left column; seed atlantic with every cell in the bottom row and right column. Run a DFS (or BFS) from each ocean's seeds: from cell (r, c), recurse into 4-directional neighbors whose height is >= heights[r][c] (because water flows from higher to lower, reverse-traversal goes from lower-or-equal to higher) and that aren't already marked in that ocean's grid. After both DFS sweeps, walk the grid and collect every (r, c) where pacific[r][c] && atlantic[r][c]. Each cell is visited at most once per ocean, so O(m*n) time and O(m*n) space.

Complexity

Time
O(m*n)
Space
O(m*n)

Related patterns

  • dfs
  • bfs
  • multi-source-bfs
  • matrix

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Pacific Atlantic Water Flow and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →