Pacific Atlantic Water Flow (LC 417)

Pattern: Grid as graph — multi-source reverse flood fill (DFS/BFS)
Difficulty: Medium
Key Concept: Water flows downhill to lower or equal heights; instead of simulating from every cell outward, start from ocean borders and mark everywhere water can flow back uphill to that ocean.

Problem Statement

Given an m x n matrix of non-negative heights, water can flow to a neighbor north/south/east/west if that neighbor’s height is ≤ current height.

• Pacific touches the left and top edges.
• Atlantic touches the right and bottom edges.

Return the list of grid coordinates [r, c] that can reach both oceans.

Input: int[][] heights
Output: List<List<Integer>> — order does not matter on LeetCode.

---

1. Algorithm & Pseudocode

Brute force

For each cell, run DFS/BFS to see if it can reach Pacific and Atlantic.

for each cell (r,c):
  if dfsPacific(r,c) && dfsAtlantic(r,c): add to answer

Optimal

Reverse reachability

pacificReachable = empty set
atlanticReachable = empty set

// Multi-source DFS/BFS from Pacific-adjacent borders
for each cell on top row OR left column:
  dfs(r, c, pacificReachable)

// Multi-source from Atlantic-adjacent borders  
for each cell on bottom row OR right column:
  dfs(r, c, atlanticReachable)

answer = cells in intersection of both sets

DFS helper (from ocean inward):

dfs(r, c, visited):
  mark (r,c) visited
  for each neighbor (nr,nc) in 4 directions:
    if in bounds AND not visited AND heights[nr][nc] >= heights[r][c]:
      dfs(nr, nc, visited)

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Forward simulation from every cell repeats work: overlapping paths explode to roughly O((mn)²) in the naive approach.
• Reversing the arrow: “Can ocean water climb up to here?” uses the same rule (only move to equal or higher neighbors) but starts only from border seeds — O(mn) total visits with marking.
• Two boolean grids (or bitmasks) record Pacific vs Atlantic reach; intersection is the answer.

---

3. The Dry Run

Heights:

      c0   c1
r0    1    2
r1    1    1

Pacific borders: top row (r0), left col (c0). Atlantic: bottom (r1), right (c1).

Pacific DFS (only key expansions):

Visit order (conceptual)	Stack rationale	Pacific set
(0,0) border seed	height 1	{(0,0)}
(1,0)	1≥1 OK from (0,0)	+ (1,0)
(0,1)	from (0,0)? 2≥1 OK; from top	+ (0,1)
(1,1)	from (0,1) 1≥2 fail; from (1,0) 1≥1 OK	+ (1,1)

Atlantic from (0,1), (1,1), (1,0), (0,0) similarly marks all four. Intersection = all cells [[0,0],[0,1],[1,0],[1,1]].

---

4. Java Solution

Brute Force

import java.util.*;

class SolutionBrute {
    private static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        List<List<Integer>> res = new ArrayList<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                boolean[][] visP = new boolean[m][n];
                boolean[][] visA = new boolean[m][n];
                if (dfs(r, c, heights, visP, true) && dfs(r, c, heights, visA, false)) {
                    res.add(Arrays.asList(r, c));
                }
            }
        }
        return res;
    }

    // true if can reach Pacific (isPacific) or Atlantic from (r,c) going downhill to ocean
    private boolean dfs(int r, int c, int[][] h, boolean[][] vis, boolean pacific) {
        int m = h.length, n = h[0].length;
        if (vis[r][c]) return false;
        vis[r][c] = true;
        if (pacific && (r == 0 || c == 0)) {
            vis[r][c] = false;
            return true;
        }
        if (!pacific && (r == m - 1 || c == n - 1)) {
            vis[r][c] = false;
            return true;
        }

        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (h[nr][nc] <= h[r][c]) {
                if (dfs(nr, nc, h, vis, pacific)) {
                    vis[r][c] = false;
                    return true;
                }
            }
        }
        vis[r][c] = false;
        return false;
    }
}

Time: O((mn)²) in worst case — each cell starts a full DFS.
Space: O(mn) per DFS visit matrix.

Optimal

import java.util.*;

class Solution {
    private static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        boolean[][] pac = new boolean[m][n];
        boolean[][] atl = new boolean[m][n];

        for (int c = 0; c < n; c++) {
            dfs(0, c, heights, pac);
            dfs(m - 1, c, heights, atl);
        }
        for (int r = 0; r < m; r++) {
            dfs(r, 0, heights, pac);
            dfs(r, n - 1, heights, atl);
        }

        List<List<Integer>> res = new ArrayList<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (pac[r][c] && atl[r][c]) {
                    res.add(Arrays.asList(r, c));
                }
            }
        }
        return res;
    }

    private void dfs(int r, int c, int[][] h, boolean[][] vis) {
        vis[r][c] = true;
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nr >= h.length || nc < 0 || nc >= h[0].length) continue;
            if (vis[nr][nc]) continue;
            if (h[nr][nc] < h[r][c]) continue; // can only climb to >= height
            dfs(nr, nc, h, vis);
        }
    }
}

BFS variant: enqueue all border seeds, same climb rule.

Time: O(mn) — each cell constant work.
Space: O(mn) for vis grids + recursion stack O(mn) worst case (use BFS for O(mn) auxiliary only).

---

5. The “Java vs. Others” Edge

• boolean[][] is clear; for tight memory, a single byte[][] with bit flags works.
• Stack overflow on huge grids: prefer ArrayDeque<int[]> BFS or iterative stack.
• List<List<Integer>> with Arrays.asList(r,c) matches LeetCode I/O.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute DFS per cell × 2 oceans	O((mn)²)	O(mn)	Revisits many paths
Optimal multi-source DFS/BFS	O(mn)	O(mn)	Standard interview answer

---

ASCII: Oceans and borders

P = Pacific border cells (top + left)
A = Atlantic border cells (bottom + right)

P P P P P P
P . . . . A
P . . . . A
P . . . . A
A A A A A A

Flow simulation reversed: flood from P inward, flood from A inward; overlap wins.