The O(n) Club: Pacific Atlantic Water Flow’s Reverse-DFS Party Trick

The O(n) Club: Pacific Atlantic Water Flow’s Reverse-DFS Party Trick

⚡ TL;DR

Which cells in a height matrix can get their water to both the Pacific (top/left) and Atlantic (bottom/right) oceans, just by sliding downhill or flat? Naive approach: Run DFS from every cell—and fry your CPU. Smart approach: Go reverse. Start from the ocean edges, let the water “climb” inwards (only where possible), and find overlap.

// Java: Find cells flowing to both oceans
List<List<Integer>> pacificAtlantic(int[][] heights) {
    // See below for details; it's a reverse edge-in search!
}

🧠 How Devs Usually Mess This Up

Classic blunder: flood the grid from every land cell trying to reach the oceans. Next, accidentally simulate waves pushing inland (wrong direction—not even Poseidon does that). Or, if you’re feeling fancy, try going diagonal because clearly Pacific water is better at cornering. These approaches will help you find performance bottlenecks at record speed—if that’s your thing.

🔍 What’s Actually Going On

This is not a vacation slideshow for your virtual rain drop. Instead, it’s a battle between two party-crashing oceans invading the land—moving only where it’s not strictly uphill. Imagine each ocean’s scouts climbing the grid from their borders, marking everywhere they can reach (without breaking any legs—water won’t climb). The mutual invasion zone is our solution: where both blue armies meet, water can flow to both seas and everyone sings “It’s a Small World After All.”

Think flood insurance but for matrix cells: who’s double-insured by the Atlantic and Pacific, as checked by two clipboard-wielding BFS/DFS bots starting from opposing coastlines?

🛠️ PseudoCode

• Mark borders: Top/Left borders = Pacific, Bottom/Right = Atlantic.
• For each ocean:
  • Run DFS/BFS from border cells inwards—water “climbs”, moving to neighbor cells of height ≥ current cell.
  • Track where each ocean can reach (visited grids).
• Result is intersection: Cells touched by both searches.

// For each ocean:
for each border cell:
    traverse(cell, visited)
 // Traverse only into neighbors >= height
function traverse(cell, visited):
    mark visited
    for each neighbor in {up, down, left, right}:
        if in grid, not visited, neighbor.height >= cell.height:
            traverse(neighbor, visited)
 // After both oceans, collect all (i,j) where pacificVisited[i][j] && atlanticVisited[i][j]

💻 The Code

public List<List<Integer>> pacificAtlantic(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    boolean[][] pacific = new boolean[m][n];
    boolean[][] atlantic = new boolean[m][n];
    for (int i = 0; i < m; i++) {
        dfs(heights, i, 0, pacific);
        dfs(heights, i, n - 1, atlantic);
    }
    for (int j = 0; j < n; j++) {
        dfs(heights, 0, j, pacific);
        dfs(heights, m - 1, j, atlantic);
    }
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (pacific[i][j] && atlantic[i][j]) {
                result.add(Arrays.asList(i, j));
            }
        }
    }
    return result;
}
 private void dfs(int[][] h, int i, int j, boolean[][] visited) {
    visited[i][j] = true;
    int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    for (int d = 0; d < 4; d++) {
        int ni = i + dx[d], nj = j + dy[d];
        if (ni >= 0 && ni < h.length && nj >= 0 && nj < h[0].length) {
            if (!visited[ni][nj] && h[ni][nj] >= h[i][j]) {
                dfs(h, ni, nj, visited);
            }
        }
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Diagonal temptation? Resist. Water stays in its lane: up, down, left, right.
• Backwards logic trip: You move from edges inwards, but only to same-or-higher cells (reverse of the usual pour).
• Edge vigilance: Don’t forget grid boundaries. City block or skinny river—you need all the borders.
• Time & space sanity: Two O(mn) visited matrices; each cell at most twice. If you try all-cells DFS/BFS, enjoy exponential existential dread.

🧠 Interviewer Brain-Tattoo

“Don’t check if your rain drop can escape—you literally start at the escape. Let the oceans climb in. Party intersection is your answer, and the only flood you want is your ego racing to the whiteboard.”