417. Pacific Atlantic Water Flow

At a Glance

Topic: graphs
Pattern: DFS / Backtracking (multi-source)
Difficulty: Medium
Companies: Google, Amazon, Microsoft, Apple, Meta
Frequency: High
LeetCode: 417

Problem (one-liner)

Heights matrix: water flows to equal-or-lower neighbors. Pacific touches top and left; Atlantic touches bottom and right. Return cells that can reach both oceans.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Reverse thinking — from ocean climb up >= instead of simulating all paths down
Two boolean grids or bitmasks for reachability

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Forward per cell BFS/DFS — O(n^2 m^2) — too slow.
Optimal — DFS from both borders — O(nm).

Optimal Solution

Go

func pacificAtlantic(heights [][]int) [][]int {
	rows := len(heights)
	cols := len(heights[0])
	pacific := make([][]bool, rows)
	atlantic := make([][]bool, rows)
	for row := range pacific {
		pacific[row] = make([]bool, cols)
		atlantic[row] = make([]bool, cols)
	}

	var dfs func(row int, col int, seen [][]bool)
	dfs = func(row int, col int, seen [][]bool) {
		if seen[row][col] {
			return
		}
		seen[row][col] = true
		current := heights[row][col]
		directions := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
		for _, delta := range directions {
			nextRow := row + delta[0]
			nextCol := col + delta[1]
			if nextRow < 0 || nextCol < 0 || nextRow >= rows || nextCol >= cols {
				continue
			}
			if heights[nextRow][nextCol] < current {
				continue
			}
			dfs(nextRow, nextCol, seen)
		}
	}

	for col := 0; col < cols; col++ {
		dfs(0, col, pacific)
		dfs(rows-1, col, atlantic)
	}
	for row := 0; row < rows; row++ {
		dfs(row, 0, pacific)
		dfs(row, cols-1, atlantic)
	}

	result := [][]int{}
	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if pacific[row][col] && atlantic[row][col] {
				result = append(result, []int{row, col})
			}
		}
	}
	return result
}

JavaScript

function pacificAtlantic(heights) {
  const rows = heights.length;
  const cols = heights[0].length;
  const pacific = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const atlantic = Array.from({ length: rows }, () => new Array(cols).fill(false));

  function dfs(row, col, seen) {
    if (seen[row][col]) {
      return;
    }
    seen[row][col] = true;
    const current = heights[row][col];
    const directions = [
      [1, 0],
      [-1, 0],
      [0, 1],
      [0, -1],
    ];
    for (const [deltaRow, deltaCol] of directions) {
      const nextRow = row + deltaRow;
      const nextCol = col + deltaCol;
      if (nextRow < 0 || nextCol < 0 || nextRow >= rows || nextCol >= cols) {
        continue;
      }
      if (heights[nextRow][nextCol] < current) {
        continue;
      }
      dfs(nextRow, nextCol, seen);
    }
  }

  for (let col = 0; col < cols; col += 1) {
    dfs(0, col, pacific);
    dfs(rows - 1, col, atlantic);
  }
  for (let row = 0; row < rows; row += 1) {
    dfs(row, 0, pacific);
    dfs(row, cols - 1, atlantic);
  }

  const result = [];
  for (let row = 0; row < rows; row += 1) {
    for (let col = 0; col < cols; col += 1) {
      if (pacific[row][col] && atlantic[row][col]) {
        result.push([row, col]);
      }
    }
  }
  return result;
}

Walkthrough

Start every Pacific-border cell and DFS uphill: move to a neighbor only if neighborHeight >= currentHeight. Same from Atlantic borders. Any cell marked by both floods drains to both oceans.

Invariant: Reverse simulation moves water “from ocean inward” along allowed uphill climbs; forward view is downhill flow from cells to oceans.

Edge Cases

Plateaus — equal heights propagate across flats
Single row / column matrix

Pitfalls

Walking downhill in reverse search — wrong direction; must expand to higher-or-equal neighbors only

Variants

Return counts per ocean instead of intersection

Mind-Map Tags

#grid #dfs #multi-source #reverse-flow #matrix