What pattern does Pacific Atlantic Water Flow use?

The Pattern: DFS (Reverse Reachability in Grid) The Heuristic: When a problem involves flow or reachability constrained by monotonic conditions on grid cells, reverse the direction of flow and use DFS/BFS from the targets (oceans) inward to efficiently mark reachable cells.

Pacific Atlantic Water Flow — DFS

Q: What is the time complexity of Pacific Atlantic Water Flow?

O(m * n). Each DFS traversal visits each cell at most once, and there are two traversals (Pacific and Atlantic), resulting in O(2 * m * n) = O(m * n) time.

Problem

Given an m x n matrix of heights representing an island's elevation map, return the list of grid coordinates where water can flow to both the Pacific and Atlantic oceans, assuming water can flow from a cell to neighboring cells with equal or lower height.

m == heights.length
n == heights[i].length
1 ≤ m, n ≤ 200
0 ≤ heights[i][j] ≤ 10⁵

Example

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

Starting from the Pacific edges (top row and left column), DFS explores cells that can flow into the Pacific by moving only to neighbors with height >= current cell. Similarly, starting from the Atlantic edges (bottom row and right column), DFS explores cells that can flow into the Atlantic. The intersection of these two reachable sets gives the cells where water can flow to both oceans. For example, cell (3,0) with height 6 can flow to both oceans because it is reachable from both DFS traversals.

Approach

Straightforward Solution

A naive approach would simulate water flow from every cell to check if it can reach both oceans, resulting in O(m*n*(m+n)) time complexity, which is inefficient for large grids.

Core Observation

Water flows from higher or equal height cells to lower or equal height neighbors. Instead of simulating water flow from every cell to the oceans, reverse the problem: start DFS from the ocean edges and move inward only to neighbors with height >= current cell, marking cells reachable by each ocean.

Path to Optimal

Preview

The key recognition signals are 'flow to ocean edges' and 'neighboring cells with height constraints'. These indicate a graph traversal pattern, specifically DFS or BFS…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Perform two separate DFS traversals: one starting from all Pacific-bordering cells (top row and left column), and one from all Atlantic-bordering cells (bottom row and right column). Each DFS marks cells reachable by that ocean…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

Each DFS traversal visits each cell at most once, and there are two traversals (Pacific and Atlantic), resulting in O(2 * m * n) = O(m * n) time.

Space

O(m * n)

Two sets store visited cells for Pacific and Atlantic traversals, each potentially containing all cells. The recursion stack in DFS can also reach O(m * n) in the worst case.

Solution

Python

1class Solution:
  def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
      ROWS, COLS = len(heights), len(heights[0])
      pacific, atlantic = set(), set()
      res = []
6
      def dfs(r, c, visit, prev_height):
          if ((r, c) in visit or r < 0 or c < 0 or r == ROWS or c == COLS or
                  heights[r][c] < prev_height):
              return
          
          visit.add((r, c))
          dfs(r + 1, c, visit, heights[r][c])
          dfs(r - 1, c, visit, heights[r][c])
          dfs(r, c + 1, visit, heights[r][c])
          dfs(r, c - 1, visit, heights[r][c])
17
      for c in range(COLS):
          dfs(0, c, pacific, heights[0][c])
          dfs(ROWS - 1, c, atlantic, heights[ROWS - 1][c])
      
      for r in range(ROWS):
          dfs(r, 0, pacific, heights[r][0])
          dfs(r, COLS - 1, atlantic, heights[r][COLS - 1])
25
      for r in range(ROWS):
          for c in range(COLS):
              if (r, c) in pacific and (r, c) in atlantic:
                  res.append([r, c])
      
      return res

Step-by-Step Solution

1

Mark Cells Reachable from Pacific and Atlantic via DFS

7def dfs(r, c, visit, prev_height):
  if ((r, c) in visit or r < 0 or c < 0 or r == ROWS or c == COLS or
          heights[r][c] < prev_height):
      return
  visit.add((r, c))
  dfs(r + 1, c, visit, heights[r][c])
  dfs(r - 1, c, visit, heights[r][c])
  dfs(r, c + 1, visit, heights[r][c])
  dfs(r, c - 1, visit, heights[r][c])

Objective

To perform DFS from ocean-bordering cells, marking all cells that can flow into each ocean by moving only to neighbors with height >= current cell.

Key Insight

Reversing the flow direction simplifies the problem: instead of simulating water flow from every cell, start from the oceans and move inward only to cells that satisfy the height condition. This ensures each cell is visited once per ocean, efficiently capturing reachability. The DFS uses a visited set to avoid revisiting cells and a height comparison to enforce monotonic flow constraints.

Interview Quick-Check

Core Logic

DFS explores neighbors only if they are within bounds, not visited, and have height >= the previous cell, ensuring monotonic non-decreasing traversal that models reverse water flow.

State & Boundaries

Visited sets prevent infinite loops and redundant work by tracking cells already reachable from each ocean.

Common Pitfalls & Bugs

Forgetting to check height constraints or visited status before DFS calls can cause incorrect reachability or infinite recursion.

Complexity

Each cell is visited at most twice (once per ocean), ensuring O(m*n) time complexity.

2

Initiate DFS from Ocean Borders to Populate Reachability Sets

To start DFS traversals from all cells adjacent to the Pacific and Atlantic oceans, ensuring all reachable cells are marked.

3

Collect Cells Reachable by Both Oceans

To identify and collect all cells that are reachable from both the Pacific and Atlantic oceans by intersecting the two visited sets.

4

Return the Final List of Coordinates

To return the list of coordinates where water can flow to both oceans after completing DFS traversals and intersection.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 8 Critical

if ((r, c) in visit or r < 0 or c < 0 or r == ROWS or c == COLS or

Check boundary conditions and pruning criteria for DFS.

This line is critical because it enforces all constraints that guarantee correctness and termination of DFS: it prevents revisiting cells, bounds checking, and ensures the height condition that models water flow direction.

Line 28 Critical

if (r, c) in pacific and (r, c) in atlantic:

Check if the current cell is reachable from both oceans.

This line is critical because it performs the intersection test that defines the problem's solution: only cells reachable from both oceans are valid answers.

Full line-by-line criticality + rationale for all 22 lines available on Pro.

Test Your Understanding

Why does starting DFS from the ocean edges and moving inward to higher or equal height neighbors correctly identify cells that can flow to the oceans?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Pacific Atlantic Water Flow from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Pacific Atlantic Water Flow drill

or drill a free problem

1	`class Solution:`
2	`def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:`
3	`ROWS, COLS = len(heights), len(heights[0])`
4	`pacific, atlantic = set(), set()`
5	`res = []`
6
7	`def dfs(r, c, visit, prev_height):`
8	`if ((r, c) in visit or r < 0 or c < 0 or r == ROWS or c == COLS or`
9	`heights[r][c] < prev_height):`
10	`return`
11
12	`visit.add((r, c))`
13	`dfs(r + 1, c, visit, heights[r][c])`
14	`dfs(r - 1, c, visit, heights[r][c])`
15	`dfs(r, c + 1, visit, heights[r][c])`
16	`dfs(r, c - 1, visit, heights[r][c])`
17
18	`for c in range(COLS):`
19	`dfs(0, c, pacific, heights[0][c])`
20	`dfs(ROWS - 1, c, atlantic, heights[ROWS - 1][c])`
21
22	`for r in range(ROWS):`
23	`dfs(r, 0, pacific, heights[r][0])`
24	`dfs(r, COLS - 1, atlantic, heights[r][COLS - 1])`
25
26	`for r in range(ROWS):`
27	`for c in range(COLS):`
28	`if (r, c) in pacific and (r, c) in atlantic:`
29	`res.append([r, c])`
30
31	`return res`

7	`def dfs(r, c, visit, prev_height):`
8	`if ((r, c) in visit or r < 0 or c < 0 or r == ROWS or c == COLS or`
9	`heights[r][c] < prev_height):`
10	`return`
12	`visit.add((r, c))`
13	`dfs(r + 1, c, visit, heights[r][c])`
14	`dfs(r - 1, c, visit, heights[r][c])`
15	`dfs(r, c + 1, visit, heights[r][c])`
16	`dfs(r, c - 1, visit, heights[r][c])`