417. Pacific Atlantic Water Flow (Medium)

Problem

Given an m × n matrix of heights representing an island, water can flow from a cell to an adjacent cell with height ≤ the current cell. The Pacific Ocean touches the top and left edges; the Atlantic touches the bottom and right. Return all cells from which water can flow to both oceans.

Example

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]]
→ [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

LeetCode 417 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, DFS from every cell, test reachability

Swift

final class Solution {
    func pacificAtlantic(_ heights: [[Int]]) -> [[Int]] {
        let rows = heights.count, cols = heights[0].count
        func reachesBoth(_ startRow: Int, _ startCol: Int) -> Bool {
            var stack = [(startRow, startCol)], seen = Set([startRow * cols + startCol])
            var pacific = false, atlantic = false
            while let (row, col) = stack.popLast() {
                if row == 0 || col == 0 { pacific = true }
                if row == rows - 1 || col == cols - 1 { atlantic = true }
                for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
                    let nr = row + dr, nc = col + dc, key = nr * cols + nc
                    if nr >= 0 && nr < rows && nc >= 0 && nc < cols && heights[nr][nc] <= heights[row][col] && seen.insert(key).inserted {
                        stack.append((nr, nc))
                    }
                }
            }
            return pacific && atlantic
        }
        var result: [[Int]] = []
        for row in 0..<rows { for col in 0..<cols where reachesBoth(row, col) { result.append([row, col]) } }
        return result
    }
}

For each cell, run two DFSes (“can I reach Pacific?”, “can I reach Atlantic?”). Keep cells that answer yes to both.

Complexity

Time: $O((m · n)$ ²). For each of m·n cells, a full $O(m·n)$ DFS.
Space: $O(m · n)$ .

Approach 2: DFS from the oceans inward (optimal)

Reverse the problem: for each ocean, walk upward (to higher or equal heights) from the border. Mark every reachable cell. The intersection of the two sets is the answer.

def pacific_atlantic(heights):
    if not heights:                                            # L1: guard empty input
        return []
    rows, cols = len(heights), len(heights[0])                # L2: O(1)
    pac = set()                                               # L3: Pacific reachability set
    atl = set()                                               # L4: Atlantic reachability set

    def dfs(r, c, visited):                                   # L5: recursive DFS
        if (r, c) in visited:                                 # L6: O(1) set lookup
            return
        visited.add((r, c))                                   # L7: O(1) set insert
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):    # L8: 4 neighbors
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and heights[nr][nc] >= heights[r][c]:
                dfs(nr, nc, visited)                          # L9: recurse uphill

    for c in range(cols):
        dfs(0, c, pac)             # L10: top row seeds Pacific
        dfs(rows - 1, c, atl)     # L11: bottom row seeds Atlantic
    for r in range(rows):
        dfs(r, 0, pac)             # L12: left column seeds Pacific
        dfs(r, cols - 1, atl)     # L13: right column seeds Atlantic

    return [[r, c] for (r, c) in pac & atl]                  # L14: set intersection

function pacificAtlantic(heights: number[][]): number[][] {
    if (!heights.length) return [];                            // L1: guard empty input
    const rows = heights.length, cols = heights[0].length;    // L2: O(1)
    const pac = new Set<number>();                             // L3: Pacific reachability
    const atl = new Set<number>();                             // L4: Atlantic reachability

    function dfs(r: number, c: number, visited: Set<number>): void {  // L5: recursive DFS
        const key = r * cols + c;
        if (visited.has(key)) return;                          // L6: O(1) set lookup
        visited.add(key);                                      // L7: O(1) set insert
        for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) { // L8: 4 neighbors
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && heights[nr][nc] >= heights[r][c]) {
                dfs(nr, nc, visited);                          // L9: recurse uphill
            }
        }
    }

    for (let c = 0; c < cols; c++) {
        dfs(0, c, pac);             // L10: top row seeds Pacific
        dfs(rows - 1, c, atl);     // L11: bottom row seeds Atlantic
    }
    for (let r = 0; r < rows; r++) {
        dfs(r, 0, pac);             // L12: left column seeds Pacific
        dfs(r, cols - 1, atl);     // L13: right column seeds Atlantic
    }

    const result: number[][] = [];
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            const key = r * cols + c;
            if (pac.has(key) && atl.has(key)) result.push([r, c]);  // L14: intersection
        }
    }
    return result;
}

final class Solution {
    func pacificAtlantic(_ heights: [[Int]]) -> [[Int]] {
        let rows = heights.count, cols = heights[0].count
        func reachable(_ starts: [(Int, Int)]) -> Set<Int> {
            var seen = Set(starts.map { $0.0 * cols + $0.1 })
            var work = starts
            while let (row, col) = work.popLast() {
                for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
                    let nr = row + dr, nc = col + dc, key = nr * cols + nc
                    if nr >= 0 && nr < rows && nc >= 0 && nc < cols && heights[nr][nc] >= heights[row][col] && seen.insert(key).inserted {
                        work.append((nr, nc))
                    }
                }
            }
            return seen
        }
        let pacific = reachable((0..<rows).map { ($0, 0) } + (0..<cols).map { (0, $0) })
        let atlantic = reachable((0..<rows).map { ($0, cols - 1) } + (0..<cols).map { (rows - 1, $0) })
        var result: [[Int]] = []
        for row in 0..<rows { for col in 0..<cols where pacific.contains(row * cols + col) && atlantic.contains(row * cols + col) { result.append([row, col]) } }
        return result
    }
}

Where the time goes, line by line

Variables: m = grid rows, n = grid cols.

Line	Per-call cost	Times executed	Contribution
L10-L13 (border seeds)	$O(1)$	2(m + n)	$O(m + n)$
L6 (visited lookup)	$O(1)$	at most m·n per ocean	$O(m·n)$
L7 (visited insert)	$O(1)$	at most m·n per ocean	$O(m·n)$
L8-L9 (neighbor recurse)	$O(1)$ per neighbor	4 × m·n total	$O(m·n)$
L5-L9 (full DFS, both oceans)	$O(1)$ per cell	2 × m·n	$O(m·n)$ ← dominates
L14 (set intersection)	$O(m·n)$	1	$O(m·n)$

Complexity

Time: $O(m · n)$ , driven by L5-L9 (each cell visited at most twice, once per ocean).
Space: $O(m · n)$ for the visited sets and the recursion stack.

Approach 3: BFS from the oceans inward

Same reverse-walk idea with a queue.

from collections import deque

def pacific_atlantic(heights):
    if not heights:                                                      # L1: guard
        return []
    rows, cols = len(heights), len(heights[0])                           # L2: O(1)

    def bfs(starts):                                                     # L3: BFS kernel
        visited = set(starts)                                            # L4: seed visited
        q = deque(starts)                                                # L5: seed queue
        while q:                                                         # L6: loop until empty
            r, c = q.popleft()                                           # L7: O(1) dequeue
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):           # L8: 4 neighbors
                nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols and
                        (nr, nc) not in visited and
                        heights[nr][nc] >= heights[r][c]):
                    visited.add((nr, nc))                                # L9: O(1) insert
                    q.append((nr, nc))                                   # L10: O(1) enqueue
        return visited

    pac = bfs([(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)])           # L11
    atl = bfs([(rows - 1, c) for c in range(cols)] + [(r, cols - 1) for r in range(rows)])  # L12
    return [[r, c] for (r, c) in pac & atl]                             # L13: intersection

function pacificAtlantic(heights: number[][]): number[][] {
    if (!heights.length) return [];
    const rows = heights.length, cols = heights[0].length;

    function bfs(starts: [number, number][]): Set<number> {
        const visited = new Set<number>(starts.map(([r, c]) => r * cols + c));
        const q: [number, number][] = [...starts];
        let head = 0;
        while (head < q.length) {
            const [r, c] = q[head++];
            for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
                const nr = r + dr, nc = c + dc;
                const key = nr * cols + nc;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                        !visited.has(key) && heights[nr][nc] >= heights[r][c]) {
                    visited.add(key);
                    q.push([nr, nc]);
                }
            }
        }
        return visited;
    }

    const pacStarts: [number, number][] = [];
    const atlStarts: [number, number][] = [];
    for (let c = 0; c < cols; c++) { pacStarts.push([0, c]); atlStarts.push([rows - 1, c]); }
    for (let r = 0; r < rows; r++) { pacStarts.push([r, 0]); atlStarts.push([r, cols - 1]); }

    const pac = bfs(pacStarts);
    const atl = bfs(atlStarts);
    const result: number[][] = [];
    for (let r = 0; r < rows; r++)
        for (let c = 0; c < cols; c++)
            if (pac.has(r * cols + c) && atl.has(r * cols + c)) result.push([r, c]);
    return result;
}

final class Solution {
    func pacificAtlantic(_ heights: [[Int]]) -> [[Int]] {
        let rows = heights.count, cols = heights[0].count
        func reachable(_ starts: [(Int, Int)]) -> Set<Int> {
            var seen = Set(starts.map { $0.0 * cols + $0.1 })
            var work = starts, index = 0
            while index < work.count {
                let (row, col) = work[index]; index += 1
                for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
                    let nr = row + dr, nc = col + dc, key = nr * cols + nc
                    if nr >= 0 && nr < rows && nc >= 0 && nc < cols && heights[nr][nc] >= heights[row][col] && seen.insert(key).inserted {
                        work.append((nr, nc))
                    }
                }
            }
            return seen
        }
        let pacific = reachable((0..<rows).map { ($0, 0) } + (0..<cols).map { (0, $0) })
        let atlantic = reachable((0..<rows).map { ($0, cols - 1) } + (0..<cols).map { (rows - 1, $0) })
        var result: [[Int]] = []
        for row in 0..<rows { for col in 0..<cols where pacific.contains(row * cols + col) && atlantic.contains(row * cols + col) { result.append([row, col]) } }
        return result
    }
}

Complexity

Time: $O(m · n)$ , driven by each cell dequeued at most once per ocean.
Space: $O(m · n)$ for the visited sets and the queue.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
DFS from every cell to each ocean	$O((m · n)$ ²)	$O(m · n)$
DFS from ocean borders inward	$O(m · n)$	$O(m · n)$
BFS from ocean borders	$O(m · n)$	$O(m · n)$

The “reverse the direction” trick is the key insight, it avoids redundant work by computing both reachability sets once. Same pattern solves problem 130 (Surrounded Regions).

# Quick smoke tests, paste into a REPL or save as test_417.py and run.
# Uses the canonical implementation (Approach 2, DFS from borders).

def pacific_atlantic(heights):
    if not heights:
        return []
    rows, cols = len(heights), len(heights[0])
    pac = set()
    atl = set()

    def dfs(r, c, visited):
        if (r, c) in visited:
            return
        visited.add((r, c))
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and heights[nr][nc] >= heights[r][c]:
                dfs(nr, nc, visited)

    for c in range(cols):
        dfs(0, c, pac)
        dfs(rows - 1, c, atl)
    for r in range(rows):
        dfs(r, 0, pac)
        dfs(r, cols - 1, atl)

    return sorted([r, c] for (r, c) in pac & atl)

def _run_tests():
    # LeetCode example
    h1 = [[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]]
    assert pacific_atlantic(h1) == [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

    # Single cell: touches all borders, always flows to both
    assert pacific_atlantic([[5]]) == [[0, 0]]

    # Flat grid: every cell can flow to both oceans
    h2 = [[1, 1], [1, 1]]
    result2 = pacific_atlantic(h2)
    assert sorted(result2) == [[0,0],[0,1],[1,0],[1,1]]

    assert pacific_atlantic([]) == []

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function pacificAtlantic(heights: number[][]): number[][] {
    if (!heights.length) return [];
    const rows = heights.length, cols = heights[0].length;
    const pac = new Set<number>(), atl = new Set<number>();

    function dfs(r: number, c: number, visited: Set<number>): void {
        const key = r * cols + c;
        if (visited.has(key)) return;
        visited.add(key);
        for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && heights[nr][nc] >= heights[r][c])
                dfs(nr, nc, visited);
        }
    }

    for (let c = 0; c < cols; c++) { dfs(0, c, pac); dfs(rows - 1, c, atl); }
    for (let r = 0; r < rows; r++) { dfs(r, 0, pac); dfs(r, cols - 1, atl); }

    const result: number[][] = [];
    for (let r = 0; r < rows; r++)
        for (let c = 0; c < cols; c++)
            if (pac.has(r * cols + c) && atl.has(r * cols + c)) result.push([r, c]);
    return result;
}

const h1 = [[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]];
const r1 = pacificAtlantic(h1);
console.assert(JSON.stringify(r1) === JSON.stringify([[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]));
console.assert(JSON.stringify(pacificAtlantic([[5]])) === JSON.stringify([[0,0]]));
console.assert(JSON.stringify(pacificAtlantic([])) === JSON.stringify([]));
console.log("all tests pass");

Arrays, height grid
Hash Tables, two reachability sets intersected at the end

Flood Fill, grid traversal tactics for expanding through adjacent cells that share a condition.
Graph Traversal, visited-state tactics for exploring nodes, edges, components, and reachability relationships.
Grid DP, row-column DP tactics for paths, matrix states, and local moves with directional dependencies.

417. Pacific Atlantic Water Flow (Medium)

Problem

Try it yourself

Approach 1: Brute force, DFS from every cell, test reachability

Approach 2: DFS from the oceans inward (optimal)

Approach 3: BFS from the oceans inward

Summary

Test cases

Related data structures

Related concepts