Skip to main content
CodePeetCodePeet
BLIND 75

Pacific Atlantic Water Flow

MEDIUMProblemSolveExternal Links

Description

You are given an m x n rectangular island represented as a grid of integer heights, where heights[r][c] is the elevation above sea level at row r, column c.

The island is surrounded by two oceans:

  • The Pacific Ocean touches the island's top and left edges.
  • The Atlantic Ocean touches the island's right and bottom edges.

When it rains, water can flow from a cell to any of its four adjacent neighbors (north, south, east, west) if the neighboring cell's height is less than or equal to the current cell's height. Any cell adjacent to an ocean boundary can flow water directly into that ocean.

Your task is to find all cells from which rainwater can reach both the Pacific Ocean and the Atlantic Ocean. Return these coordinates as a list of [row, col] pairs in any order.

5x5 grid showing Pacific Ocean on top and left edges, Atlantic Ocean on right and bottom edges
5x5 grid showing Pacific Ocean on top and left edges, Atlantic Ocean on right and bottom edges

Examples

Example 1

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

Explanation: Consider cell [2,2] with height 5. Water can flow to the Pacific by going up: [2,2] (5) → [1,2] (3) → [0,2] (2) → Pacific (top edge). Water can also flow to the Atlantic by going right: [2,2] (5) → [2,3] (3) → [2,4] (1) → Atlantic (right edge). Since both paths exist, [2,2] is included in the answer. Similarly, corner cells like [0,4] and [4,0] touch both oceans' boundaries, so they are automatically included. Cell [3,0] with height 6 reaches Pacific directly (left edge) and reaches Atlantic via [3,0] → [4,0] (5) → Atlantic (bottom edge).

Example 2

Input: heights = [[1]]

Output: [[0,0]]

Explanation: With only a single cell, it borders all four edges of the island. It is adjacent to both the Pacific (top and left) and Atlantic (right and bottom) oceans, so water from this cell can reach both oceans trivially.

Example 3

Input: heights = [[1,1],[1,1]]

Output: [[0,0],[0,1],[1,0],[1,1]]

Explanation: All cells have the same height, so water can flow freely in any direction (equal heights are allowed). Every cell can reach both ocean boundaries, so all four cells are in the answer.

Constraints

  • m == heights.length
  • n == heights[r].length
  • 1 ≤ m, n ≤ 200
  • 0 ≤ heights[r][c] ≤ 10^5

Editorial

Brute Force

Intuition

The most straightforward approach is to check each cell individually: can water from this cell reach the Pacific Ocean? Can it also reach the Atlantic Ocean? If both answers are yes, add it to the result.

Think of standing on a hilltop and pouring a bucket of water. The water flows downhill (or stays level) until it reaches the edge of the island. For each cell, we simulate this process by exploring all possible downhill or level paths. If any path leads to the top or left edge, the Pacific is reachable. If any path leads to the right or bottom edge, the Atlantic is reachable.

We can use DFS (or BFS) from each cell, following paths where the next cell's height is less than or equal to the current cell's height. We run this search twice for each cell — once checking if we can reach any Pacific border, and once checking if we can reach any Atlantic border.

Step-by-Step Explanation

Let's trace through a small portion using 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]]:

Step 1: Start with cell [0,0] (height 1). Check Pacific: it's on the top and left edge, so it directly touches Pacific. Check Atlantic: try flowing right to [0,1] (height 2) — but 2 > 1, water cannot flow uphill. Try flowing down to [1,0] (height 3) — but 3 > 1, also cannot flow uphill. Cell [0,0] is stuck; it cannot reach Atlantic. NOT in result.

Step 2: Check cell [0,1] (height 2). Pacific: it's on the top edge, so yes. Atlantic: from [0,1] we can go right to [0,2] (2, equal, ok), then right to [0,3] (3, higher — no). From [0,2] go down to [1,2] (3, higher — no). We cannot reach the right or bottom edge via downhill paths. NOT in result.

Step 3: Check cell [0,4] (height 5). Pacific: it's on the top edge, so yes. Atlantic: it's on the right edge, so yes. Both oceans reachable. IN result.

Step 4: Check cell [2,2] (height 5). Pacific: go up to [1,2] (3 ≤ 5, ok), then up to [0,2] (2 ≤ 3, ok), which is on the top edge — Pacific reached. Atlantic: go right to [2,3] (3 ≤ 5, ok), then right to [2,4] (1 ≤ 3, ok), which is on the right edge — Atlantic reached. IN result.

Step 5: Continue this process for all m × n cells. Each cell requires a DFS/BFS that in the worst case visits all m × n cells.

Step 6: Collect all cells where both Pacific and Atlantic are reachable. Result: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]].

Algorithm

  1. For each cell (r, c) in the grid:
    a. Run a DFS/BFS from (r, c), following cells with height ≤ current height
    b. If any path reaches the top edge or left edge, mark pacific_reachable = true
    c. Run another DFS/BFS from (r, c) with the same rules
    d. If any path reaches the bottom edge or right edge, mark atlantic_reachable = true
    e. If both are true, add [r, c] to the result
  2. Return the result list

Code

class Solution {
public:
    int m, n;
    vector<vector<int>> dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    
    bool canReach(vector<vector<int>>& heights, int r, int c,
                  function<bool(int,int)> isBorder) {
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        queue<pair<int,int>> q;
        q.push({r, c});
        visited[r][c] = true;
        while (!q.empty()) {
            auto [cr, cc] = q.front(); q.pop();
            if (isBorder(cr, cc)) return true;
            for (auto& d : dirs) {
                int nr = cr + d[0], nc = cc + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
                    !visited[nr][nc] &&
                    heights[nr][nc] <= heights[cr][cc]) {
                    visited[nr][nc] = true;
                    q.push({nr, nc});
                }
            }
        }
        return false;
    }
    
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size(); n = heights[0].size();
        vector<vector<int>> result;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                bool pacific = canReach(heights, r, c,
                    [](int r, int c) { return r == 0 || c == 0; });
                bool atlantic = canReach(heights, r, c,
                    [this](int r, int c) { return r == m-1 || c == n-1; });
                if (pacific && atlantic)
                    result.push_back({r, c});
            }
        }
        return result;
    }
};
from collections import deque
from typing import List, Callable

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        m, n = len(heights), len(heights[0])
        dirs = [(0,1),(0,-1),(1,0),(-1,0)]
        
        def can_reach(r: int, c: int, is_border: Callable) -> bool:
            visited = set()
            queue = deque([(r, c)])
            visited.add((r, c))
            while queue:
                cr, cc = queue.popleft()
                if is_border(cr, cc):
                    return True
                for dr, dc in dirs:
                    nr, nc = cr + dr, cc + dc
                    if (0 <= nr < m and 0 <= nc < n and
                        (nr, nc) not in visited and
                        heights[nr][nc] <= heights[cr][cc]):
                        visited.add((nr, nc))
                        queue.append((nr, nc))
            return False
        
        result = []
        for r in range(m):
            for c in range(n):
                pacific = can_reach(r, c, lambda r, c: r == 0 or c == 0)
                atlantic = can_reach(r, c, lambda r, c: r == m-1 or c == n-1)
                if pacific and atlantic:
                    result.append([r, c])
        return result
class Solution {
    int m, n;
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    
    private boolean canReach(int[][] heights, int r, int c, boolean checkPacific) {
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int cr = cell[0], cc = cell[1];
            if (checkPacific && (cr == 0 || cc == 0)) return true;
            if (!checkPacific && (cr == m-1 || cc == n-1)) return true;
            for (int[] d : dirs) {
                int nr = cr + d[0], nc = cc + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
                    !visited[nr][nc] &&
                    heights[nr][nc] <= heights[cr][cc]) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        return false;
    }
    
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m = heights.length; n = heights[0].length;
        List<List<Integer>> result = new ArrayList<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (canReach(heights, r, c, true) && canReach(heights, r, c, false)) {
                    result.add(Arrays.asList(r, c));
                }
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O((m × n)²)

We iterate over all m × n cells. For each cell, we run up to two BFS/DFS traversals, each of which can visit up to m × n cells in the worst case. Therefore, the total time is O(m × n) cells × O(m × n) per BFS = O((m × n)²). With m, n up to 200, that is up to (200 × 200)² = 1.6 × 10⁹ operations — far too slow.

Space Complexity: O(m × n)

Each BFS/DFS uses a visited array of size m × n, plus the queue which can hold up to m × n elements in the worst case.

Why This Approach Is Not Efficient

The brute force approach is extremely wasteful because it treats each cell independently. When we run BFS from cell [2,2], we might explore cells [1,2], [0,2], and discover they can reach the Pacific. But when we later check cell [1,2] directly, we start a brand-new BFS that re-discovers the same paths. There is massive redundant computation — the same cells are explored over and over.

With m, n ≤ 200, we have up to 40,000 cells. Running a full BFS (up to 40,000 cells) for each one gives roughly 1.6 billion operations — this will time out.

The key insight is to reverse the direction of flow. Instead of asking "from cell X, can I flow downhill to the ocean?", we ask "from the ocean, which cells can I flow uphill to?" This reversal lets us start BFS from all ocean border cells simultaneously (multi-source BFS), visiting each cell at most once per ocean. This eliminates the redundant per-cell explorations entirely.

Optimal Approach - Reverse BFS/DFS from Ocean Borders

Intuition

Instead of pouring water from every cell and checking where it ends up, imagine the oceans rising and "creeping" inland. The Pacific starts at the top and left edges and can flow inward to any neighbor that is at least as tall (reversing the flow direction — water flows downhill, so going backward means going uphill or level). Similarly, the Atlantic starts at the bottom and right edges.

We run two separate multi-source BFS (or DFS) traversals:

  1. Pacific BFS: Start from all cells on the top row and left column. Mark every cell reachable by moving to neighbors with height ≥ current height.
  2. Atlantic BFS: Start from all cells on the bottom row and right column. Same traversal logic.

After both traversals complete, any cell marked as reachable by BOTH the Pacific and Atlantic BFS is a cell where water can flow to both oceans. We simply find the intersection of the two reachable sets.

This is like painting the grid with two colors: blue for Pacific-reachable, teal for Atlantic-reachable. Any cell painted with both colors is in the answer.

Step-by-Step Explanation

Let's trace using a smaller 3x3 portion from the top-left of our example: heights = [[1,2,2],[3,2,3],[2,4,5]].

Step 1: Initialize Pacific BFS queue with all top-row and left-column cells: {(0,0), (0,1), (0,2), (1,0), (2,0)}. Mark them all as Pacific-reachable.

Step 2: Process (0,0) height=1. Neighbors: (0,1) height=2 ≥ 1 — already marked. (1,0) height=3 ≥ 1 — already marked. No new discoveries.

Step 3: Process (0,1) height=2. Neighbors: (0,0) height=1 < 2 — cannot go uphill in reverse direction. (0,2) already marked. (1,1) height=2 ≥ 2 — mark (1,1) Pacific-reachable, add to queue.

Step 4: Process (0,2) height=2. Neighbors: (1,2) height=3 ≥ 2 — mark (1,2) Pacific-reachable. (0,1) already marked.

Step 5: Process (1,0) height=3. Neighbors: (2,0) already marked. (1,1) already marked. (0,0) height=1 < 3 — skip.

Step 6: Process (2,0) height=2. Neighbors: (1,0) height=3 ≥ 2 — already marked. (2,1) height=4 ≥ 2 — mark (2,1).

Step 7: Process remaining: (1,1) height=2 → (2,1) height=4 ≥ 2 — already marked. (1,2) height=3 → (2,2) height=5 ≥ 3 — mark (2,2). (2,1) height=4 → (2,2) already marked. Pacific-reachable: ALL cells.

Step 8: Initialize Atlantic BFS queue with bottom-row and right-column cells: {(2,0), (2,1), (2,2), (0,2), (1,2)}. Mark Atlantic-reachable.

Step 9: Process Atlantic BFS similarly. (2,2) height=5 → (1,2) height=3 < 5 — skip (reverse: need ≥). (2,1) height=4 → (1,1) height=2 < 4 — skip. (2,0) height=2 → (1,0) height=3 ≥ 2 — mark (1,0). Continue: (1,0) height=3 → (0,0) height=1 < 3 — skip. (0,2) height=2 → (0,1) height=2 ≥ 2 — mark (0,1). (0,1) → (0,0) height=1 < 2 — skip. Atlantic-reachable: {(2,0),(2,1),(2,2),(0,2),(1,2),(1,0),(0,1)}.

Step 10: Find intersection of Pacific and Atlantic sets. All cells except (0,0) are in both sets — but in the full grid with actual dimensions, only 7 cells qualify.

Result: Return cells in both sets.

Reverse BFS — Pacific and Atlantic Flooding — Watch two multi-source BFS traversals flood inward from ocean borders. Pacific (blue) starts from top and left edges. Atlantic (teal) starts from bottom and right edges. Cells reached by both are the answer.

Algorithm

  1. Create two boolean matrices: pacific[m][n] and atlantic[m][n], initialized to false
  2. Pacific BFS:
    • Add all cells in row 0 and column 0 to a queue; mark them in pacific
    • While queue is not empty:
      • Dequeue cell (r, c)
      • For each neighbor (nr, nc) in 4 directions:
        • If in bounds, not yet marked, and heights[nr][nc] >= heights[r][c] → mark and enqueue
  3. Atlantic BFS:
    • Add all cells in row m-1 and column n-1 to a queue; mark them in atlantic
    • Same BFS logic as above
  4. Collect results:
    • For each cell (r, c), if pacific[r][c] AND atlantic[r][c], add [r, c] to result
  5. Return result

Code

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size();
        vector<vector<bool>> pacific(m, vector<bool>(n, false));
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));
        queue<pair<int,int>> pacQ, atlQ;
        
        // Seed Pacific (top row + left column)
        for (int c = 0; c < n; c++) {
            pacific[0][c] = true;
            pacQ.push({0, c});
        }
        for (int r = 1; r < m; r++) {
            pacific[r][0] = true;
            pacQ.push({r, 0});
        }
        
        // Seed Atlantic (bottom row + right column)
        for (int c = 0; c < n; c++) {
            atlantic[m-1][c] = true;
            atlQ.push({m-1, c});
        }
        for (int r = 0; r < m-1; r++) {
            atlantic[r][n-1] = true;
            atlQ.push({r, n-1});
        }
        
        int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
        
        // BFS helper
        auto bfs = [&](queue<pair<int,int>>& q, vector<vector<bool>>& reachable) {
            while (!q.empty()) {
                auto [r, c] = q.front(); q.pop();
                for (auto& d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
                        !reachable[nr][nc] &&
                        heights[nr][nc] >= heights[r][c]) {
                        reachable[nr][nc] = true;
                        q.push({nr, nc});
                    }
                }
            }
        };
        
        bfs(pacQ, pacific);
        bfs(atlQ, atlantic);
        
        vector<vector<int>> result;
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                if (pacific[r][c] && atlantic[r][c])
                    result.push_back({r, c});
        
        return result;
    }
};
from collections import deque
from typing import List

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        m, n = len(heights), len(heights[0])
        pacific = [[False] * n for _ in range(m)]
        atlantic = [[False] * n for _ in range(m)]
        pac_queue = deque()
        atl_queue = deque()
        
        # Seed Pacific border cells (top row + left column)
        for c in range(n):
            pacific[0][c] = True
            pac_queue.append((0, c))
        for r in range(1, m):
            pacific[r][0] = True
            pac_queue.append((r, 0))
        
        # Seed Atlantic border cells (bottom row + right column)
        for c in range(n):
            atlantic[m - 1][c] = True
            atl_queue.append((m - 1, c))
        for r in range(m - 1):
            atlantic[r][n - 1] = True
            atl_queue.append((r, n - 1))
        
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        def bfs(queue, reachable):
            while queue:
                r, c = queue.popleft()
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < m and 0 <= nc < n and
                        not reachable[nr][nc] and
                        heights[nr][nc] >= heights[r][c]):
                        reachable[nr][nc] = True
                        queue.append((nr, nc))
        
        bfs(pac_queue, pacific)
        bfs(atl_queue, atlantic)
        
        result = []
        for r in range(m):
            for c in range(n):
                if pacific[r][c] and atlantic[r][c]:
                    result.append([r, c])
        
        return result
class Solution {
    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];
        Queue<int[]> pacQ = new LinkedList<>();
        Queue<int[]> atlQ = new LinkedList<>();
        
        // Seed Pacific (top row + left column)
        for (int c = 0; c < n; c++) {
            pacific[0][c] = true;
            pacQ.offer(new int[]{0, c});
        }
        for (int r = 1; r < m; r++) {
            pacific[r][0] = true;
            pacQ.offer(new int[]{r, 0});
        }
        
        // Seed Atlantic (bottom row + right column)
        for (int c = 0; c < n; c++) {
            atlantic[m - 1][c] = true;
            atlQ.offer(new int[]{m - 1, c});
        }
        for (int r = 0; r < m - 1; r++) {
            atlantic[r][n - 1] = true;
            atlQ.offer(new int[]{r, n - 1});
        }
        
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        
        bfs(heights, pacQ, pacific, dirs, m, n);
        bfs(heights, atlQ, atlantic, dirs, m, n);
        
        List<List<Integer>> result = new ArrayList<>();
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                if (pacific[r][c] && atlantic[r][c])
                    result.add(Arrays.asList(r, c));
        
        return result;
    }
    
    private void bfs(int[][] heights, Queue<int[]> queue,
                     boolean[][] reachable, int[][] dirs, int m, int n) {
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int r = cell[0], c = cell[1];
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
                    !reachable[nr][nc] &&
                    heights[nr][nc] >= heights[r][c]) {
                    reachable[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(m × n)

We run two BFS traversals. In each BFS, every cell is enqueued and processed at most once (once marked as reachable, it is never revisited). Each cell has at most 4 neighbors to check. So each BFS does O(m × n) work. The final intersection scan is also O(m × n). Total: O(m × n) + O(m × n) + O(m × n) = O(m × n).

With m, n ≤ 200, this is at most 40,000 operations per BFS — extremely fast compared to the brute force's 1.6 billion.

Space Complexity: O(m × n)

We use two boolean matrices of size m × n (pacific and atlantic), plus two BFS queues that can hold up to m × n elements in the worst case. Total auxiliary space: O(m × n).