Pacific Atlantic Water Flow

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.

Q: 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.

Medium DFS

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

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. The insight is to reverse the flow direction: start DFS from the ocean edges and move inward only to cells that can flow into the ocean (i.e., neighbors with height >= current cell). This approach efficiently marks all cells reachable from each ocean in O(m*n) time.

Optimal Approach

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. The final result is the intersection of these two sets. This approach guarantees O(m*n) time complexity and O(m*n) space complexity for visited sets.

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.

Pattern Spotlight

DFS (Reverse Reachability in Grid)

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.

Solution

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

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.

Initiate DFS from Ocean Borders to Populate Reachability Sets

18for c in range(COLS):
19    dfs(0, c, pacific, heights[0][c])
20    dfs(ROWS - 1, c, atlantic, heights[ROWS - 1][c])
22for r in range(ROWS):
23    dfs(r, 0, pacific, heights[r][0])
24    dfs(r, COLS - 1, atlantic, heights[r][COLS - 1])

Objective

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

Key Insight

The Pacific ocean touches the top row and left column, while the Atlantic touches the bottom row and right column. By iterating over these edges and launching DFS from each cell, the algorithm systematically marks all cells that can flow into each ocean. This approach leverages the problem's geometric constraints to reduce the search space and avoid redundant computations.

Interview Quick-Check

Core Logic

Launching DFS from all ocean-bordering cells ensures complete coverage of reachable cells for each ocean.

State & Boundaries

Iterating over columns for top and bottom rows and rows for left and right columns covers all ocean-adjacent cells.

Common Pitfalls & Bugs

Neglecting to start DFS from all border cells can miss reachable cells, leading to incorrect results.

Collect Cells Reachable by Both Oceans

26for r in range(ROWS):
  for c in range(COLS):
      if (r, c) in pacific and (r, c) in atlantic:
          res.append([r, c])

Objective

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

Key Insight

After marking reachable cells for each ocean, the problem reduces to finding the intersection of these two sets. Iterating over all cells and checking membership in both sets efficiently produces the final list of coordinates where water can flow to both oceans. This step leverages set membership for O(1) average-time checks, ensuring overall efficiency.

Interview Quick-Check

Core Logic

The intersection of the two visited sets represents cells that can flow to both oceans.

Complexity

Checking membership in sets is O(1) on average, making the intersection step O(m*n).

Common Pitfalls & Bugs

Failing to check both sets or incorrectly appending results can lead to incomplete or incorrect output.

Return the Final List of Coordinates

31	`return res`

Objective

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

Key Insight

Returning the accumulated result list completes the algorithm. This list contains all cells satisfying the problem's flow conditions, computed efficiently via reverse DFS and set intersection.

Interview Quick-Check

Core Logic

Returning the result list provides the final answer as required by the problem.

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.

Line 4 Core

pacific, atlantic = set(), set()

Initialize sets to track cells reachable from the Pacific and Atlantic oceans.

Using sets allows O(1) average-time membership checks and prevents revisiting cells during DFS, ensuring efficient traversal.

Line 12 Core

visit.add((r, c))

Mark the current cell as visited for the current ocean.

Recording visited cells prevents revisiting and infinite recursion, ensuring each cell is processed once per ocean.

Line 19 Core

dfs(0, c, pacific, heights[0][c])

Launch DFS from the top row cell for Pacific reachability.

This call initiates reverse flow exploration from the Pacific ocean's top edge.

Line 20 Core

dfs(ROWS - 1, c, atlantic, heights[ROWS - 1][c])

Launch DFS from the bottom row cell for Atlantic reachability.

This call initiates reverse flow exploration from the Atlantic ocean's bottom edge.

Line 23 Core

dfs(r, 0, pacific, heights[r][0])

Launch DFS from the left column cell for Pacific reachability.

This call initiates reverse flow exploration from the Pacific ocean's left edge.

Line 24 Core

dfs(r, COLS - 1, atlantic, heights[r][COLS - 1])

Launch DFS from the right column cell for Atlantic reachability.

This call initiates reverse flow exploration from the Atlantic ocean's right edge.

Line 9 Core

heights[r][c] < prev_height):

Return early from DFS if any pruning condition is met.

Early termination avoids unnecessary recursion and infinite loops, ensuring efficient traversal.

Line 13 Core

dfs(r + 1, c, visit, heights[r][c])

Recursively explore the cell below if valid.

DFS moves downward only if the neighbor's height is >= current cell, preserving the reverse flow condition.

Line 14 Core

dfs(r - 1, c, visit, heights[r][c])

Recursively explore the cell above if valid.

DFS moves upward with the same monotonic height constraint, ensuring correct reachability marking.

Line 15 Core

dfs(r, c + 1, visit, heights[r][c])

Recursively explore the cell to the right if valid.

DFS moves rightward under the height constraint, maintaining the reverse flow logic.

Line 16 Core

dfs(r, c - 1, visit, heights[r][c])

Recursively explore the cell to the left if valid.

DFS moves leftward with the height condition, completing exploration of all four directions.

Line 29 Core

res.append([r, c])

Append the current cell's coordinates to the result list.

Collecting valid cells into the result list prepares the final output.

Line 7 Standard

def dfs(r, c, visit, prev_height):

Define the DFS helper function to explore reachable cells.

Encapsulating DFS logic in a helper function enables recursive exploration with state parameters for visited sets and height constraints.

Line 18 Standard

for c in range(COLS):

Iterate over all columns to start DFS from the top row (Pacific ocean).

Starting DFS from the top edge ensures all cells reachable from the Pacific ocean's top border are explored.

Line 22 Standard

for r in range(ROWS):

Iterate over all rows to start DFS from the left column (Pacific ocean).

Starting DFS from the left edge ensures all cells reachable from the Pacific ocean's left border are explored.

Line 26 Standard

for r in range(ROWS):

Iterate over all rows for final intersection check.

This loop prepares to check each cell for reachability from both oceans.

Line 27 Standard

for c in range(COLS):

Iterate over all columns for final intersection check.

Nested loop completes traversal of all cells for intersection testing.

Line 31 Standard

return res

Return the list of coordinates reachable by both oceans.

Returning the result completes the algorithm, providing the required output to the caller.

Line 3 Basic

ROWS, COLS = len(heights), len(heights[0])

Cache the number of rows and columns in the heights matrix.

Storing dimensions upfront avoids repeated calls to len() and simplifies boundary checks throughout the algorithm.

Line 5 Basic

res = []

Initialize the result list to store coordinates reachable by both oceans.

This list accumulates the final output after intersecting reachable cells from both oceans.

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?

Because water can only flow from higher or equal height cells to lower or equal height neighbors, reversing the flow direction means starting from the ocean edges and moving only to neighbors with height >= current cell simulates all cells from which water can reach the ocean by flowing downhill or flat. This reverse traversal marks all cells that can flow to the ocean.

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

Problem

Example

Approach

Solution

Step-by-Step Solution

Mark Cells Reachable from Pacific and Atlantic via DFS

Initiate DFS from Ocean Borders to Populate Reachability Sets

Collect Cells Reachable by Both Oceans

Return the Final List of Coordinates

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.