Pacific Atlantic Water Flow — Solution in C++, Java, Python, Go

Given an m x n rectangular island heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c), find all cells where water can flow to both the Pacific and Atlantic oceans.

The Pacific ocean touches the island's left and top edges. The Atlantic ocean touches the island's right and bottom edges. Water can flow from a cell to an adjacent cell (up, down, left, right) if the adjacent cell's height is less than or equal to the current cell's height. Water can also flow to the ocean if the cell is adjacent to the ocean boundary.

Return a 2D list of grid coordinates where each element [r, c] denotes that water can flow from cell (r, c) to both oceans.

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: Cells at these positions can reach both the Pacific (top/left) and Atlantic (bottom/right) oceans.

Example 2

Input: heights = [[1]]
Output: [[0,0]]
Explanation: The single cell borders both oceans.

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

DFS from Ocean Borders

Intuition

Instead of checking whether each cell can reach both oceans (which would be expensive), we reverse the problem: start from the ocean borders and flow uphill. We run DFS from every cell on the Pacific border (top row and left column) to find all cells reachable by the Pacific. Similarly, we run DFS from every cell on the Atlantic border (bottom row and right column). A cell where water can reach both oceans is one that appears in both reachable sets. This reversal dramatically reduces redundant work.

Algorithm

Create two boolean matrices: `pacific` and `atlantic`, both initialized to false.
Run DFS from every cell in the top row and left column, marking reachable cells in `pacific`. Water flows to cells with height greater than or equal to the current cell.
Run DFS from every cell in the bottom row and right column, marking reachable cells in `atlantic`.
Iterate through all cells. If a cell is marked true in both `pacific` and `atlantic`, add it to the result list.
Return the result list.

TimeO(m * n) where m and n are the dimensions of the gridSpaceO(m * n) for the two visited matrices and the recursion stack

Code (C++ · Java · Python · Go)

C++17

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));

        for (int i = 0; i < m; i++) {
            dfs(heights, pacific, i, 0);
            dfs(heights, atlantic, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(heights, pacific, 0, j);
            dfs(heights, atlantic, m - 1, j);
        }

        vector<vector<int>> result;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.push_back({i, j});
                }
            }
        }

        return result;
    }

private:
    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int r, int c) {
        int m = heights.size(), n = heights[0].size();
        visited[r][c] = true;

        int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                dfs(heights, visited, nr, nc);
            }
        }
    }
};

Java 21

class Solution {
    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    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, pacific, i, 0);
            dfs(heights, atlantic, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(heights, pacific, 0, j);
            dfs(heights, atlantic, m - 1, j);
        }

        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(List.of(i, j));
                }
            }
        }

        return result;
    }

    private void dfs(int[][] heights, boolean[][] visited, int r, int c) {
        int m = heights.length, n = heights[0].length;
        visited[r][c] = true;

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                dfs(heights, visited, nr, nc);
            }
        }
    }
}

Python 3.12

from typing import List


class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        m, n = len(heights), len(heights[0])
        pacific = set()
        atlantic = set()

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

        for i in range(m):
            dfs(i, 0, pacific)
            dfs(i, n - 1, atlantic)
        for j in range(n):
            dfs(0, j, pacific)
            dfs(m - 1, j, atlantic)

        return [[r, c] for r in range(m) for c in range(n) if (r, c) in pacific and (r, c) in atlantic]

Go 1.26

func pacificAtlantic(heights [][]int) [][]int {
    m, n := len(heights), len(heights[0])
    pacific := make([][]bool, m)
    atlantic := make([][]bool, m)
    for i := range pacific {
        pacific[i] = make([]bool, n)
        atlantic[i] = make([]bool, n)
    }

    dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

    var dfs func(visited [][]bool, r, c int)
    dfs = func(visited [][]bool, r, c int) {
        visited[r][c] = true
        for _, d := range dirs {
            nr, nc := r+d[0], c+d[1]
            if nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && heights[nr][nc] >= heights[r][c] {
                dfs(visited, nr, nc)
            }
        }
    }

    for i := 0; i < m; i++ {
        dfs(pacific, i, 0)
        dfs(atlantic, i, n-1)
    }
    for j := 0; j < n; j++ {
        dfs(pacific, 0, j)
        dfs(atlantic, m-1, j)
    }

    var result [][]int
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if pacific[i][j] && atlantic[i][j] {
                result = append(result, []int{i, j})
            }
        }
    }

    return result
}

Approach 2

BFS from Ocean Borders

Intuition

This approach uses the same reverse-flow idea but replaces DFS with BFS. We initialize two queues: one with all Pacific border cells and one with all Atlantic border cells. We perform BFS from each queue, expanding to neighbors with greater or equal height. Cells visited from both BFS runs can reach both oceans. BFS avoids deep recursion stacks and can be more cache-friendly for wide grids.

Algorithm

Create two boolean matrices and two queues. Add all Pacific border cells (top row, left column) to the Pacific queue. Add all Atlantic border cells (bottom row, right column) to the Atlantic queue.
Run BFS from the Pacific queue: dequeue a cell, and for each unvisited neighbor with height >= current cell height, mark it and enqueue it.
Run BFS from the Atlantic queue using the same logic.
Collect all cells that are marked in both matrices.
Return the result.

TimeO(m * n) where m and n are the dimensions of the gridSpaceO(m * n) for the two visited matrices and the queues

Code (C++ · Java · Python · Go)

C++17

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>> pacQueue, atlQueue;

        for (int i = 0; i < m; i++) {
            pacific[i][0] = true;
            pacQueue.push({i, 0});
            atlantic[i][n - 1] = true;
            atlQueue.push({i, n - 1});
        }
        for (int j = 0; j < n; j++) {
            pacific[0][j] = true;
            pacQueue.push({0, j});
            atlantic[m - 1][j] = true;
            atlQueue.push({m - 1, j});
        }

        int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        auto bfs = [&](queue<pair<int, int>>& q, vector<vector<bool>>& visited) {
            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 && !visited[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                        visited[nr][nc] = true;
                        q.push({nr, nc});
                    }
                }
            }
        };

        bfs(pacQueue, pacific);
        bfs(atlQueue, atlantic);

        vector<vector<int>> result;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.push_back({i, j});
                }
            }
        }
        return result;
    }
};

Java 21

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[]> pacQueue = new LinkedList<>();
        Queue<int[]> atlQueue = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            pacific[i][0] = true;
            pacQueue.add(new int[]{i, 0});
            atlantic[i][n - 1] = true;
            atlQueue.add(new int[]{i, n - 1});
        }
        for (int j = 0; j < n; j++) {
            pacific[0][j] = true;
            pacQueue.add(new int[]{0, j});
            atlantic[m - 1][j] = true;
            atlQueue.add(new int[]{m - 1, j});
        }

        bfs(heights, pacQueue, pacific, m, n);
        bfs(heights, atlQueue, atlantic, m, n);

        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(List.of(i, j));
                }
            }
        }
        return result;
    }

    private void bfs(int[][] heights, Queue<int[]> queue, boolean[][] visited, int m, int n) {
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && heights[nr][nc] >= heights[cell[0]][cell[1]]) {
                    visited[nr][nc] = true;
                    queue.add(new int[]{nr, nc});
                }
            }
        }
    }
}

Python 3.12

from typing import List
from collections import deque


class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        m, n = len(heights), len(heights[0])
        pacific = set()
        atlantic = set()

        pac_queue = deque()
        atl_queue = deque()

        for i in range(m):
            pacific.add((i, 0))
            pac_queue.append((i, 0))
            atlantic.add((i, n - 1))
            atl_queue.append((i, n - 1))
        for j in range(n):
            pacific.add((0, j))
            pac_queue.append((0, j))
            atlantic.add((m - 1, j))
            atl_queue.append((m - 1, j))

        def bfs(queue, visited):
            while queue:
                r, c = queue.popleft()
                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited and heights[nr][nc] >= heights[r][c]:
                        visited.add((nr, nc))
                        queue.append((nr, nc))

        bfs(pac_queue, pacific)
        bfs(atl_queue, atlantic)

        return [[r, c] for r in range(m) for c in range(n) if (r, c) in pacific and (r, c) in atlantic]

Go 1.26

func pacificAtlantic(heights [][]int) [][]int {
    m, n := len(heights), len(heights[0])
    pacific := make([][]bool, m)
    atlantic := make([][]bool, m)
    for i := range pacific {
        pacific[i] = make([]bool, n)
        atlantic[i] = make([]bool, n)
    }

    type cell struct{ r, c int }
    dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

    pacQueue := []cell{}
    atlQueue := []cell{}

    for i := 0; i < m; i++ {
        pacific[i][0] = true
        pacQueue = append(pacQueue, cell{i, 0})
        atlantic[i][n-1] = true
        atlQueue = append(atlQueue, cell{i, n - 1})
    }
    for j := 0; j < n; j++ {
        pacific[0][j] = true
        pacQueue = append(pacQueue, cell{0, j})
        atlantic[m-1][j] = true
        atlQueue = append(atlQueue, cell{m - 1, j})
    }

    bfs := func(queue []cell, visited [][]bool) {
        for len(queue) > 0 {
            curr := queue[0]
            queue = queue[1:]
            for _, d := range dirs {
                nr, nc := curr.r+d[0], curr.c+d[1]
                if nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && heights[nr][nc] >= heights[curr.r][curr.c] {
                    visited[nr][nc] = true
                    queue = append(queue, cell{nr, nc})
                }
            }
        }
    }

    bfs(pacQueue, pacific)
    bfs(atlQueue, atlantic)

    var result [][]int
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if pacific[i][j] && atlantic[i][j] {
                result = append(result, []int{i, j})
            }
        }
    }
    return result
}

Frequently asked questions

What is the optimal time complexity of Pacific Atlantic Water Flow?

The most efficient approach in this guide ("BFS from Ocean Borders") runs in O(m * n) where m and n are the dimensions of the grid time and uses O(m * n) for the two visited matrices and the queues extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Pacific Atlantic Water Flow use?

Pacific Atlantic Water Flow is a medium-level Graphs problem involving Graph, Depth-First Search, Breadth-First Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Pacific Atlantic Water Flow be solved without extra space?

The most space-efficient approach in this guide uses O(m * n) for the two visited matrices and the queues extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(m * n) for the two visited matrices and the recursion stack, while the optimized version uses O(m * n) for the two visited matrices and the queues.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Examples

Example 1

Example 2

Constraints

Approaches

DFS from Ocean Borders

Intuition

Algorithm

Code (C++ · Java · Python · Go)

BFS from Ocean Borders

Intuition

Algorithm

Code (C++ · Java · Python · Go)

Frequently asked questions

What is the optimal time complexity of Pacific Atlantic Water Flow?

What pattern does Pacific Atlantic Water Flow use?

Can Pacific Atlantic Water Flow be solved without extra space?

Which programming languages does this Ratta solution support?

Related Problems