Problem statement

You are given an m x n matrix heights of island cell heights. The Pacific touches the top and left edges; the Atlantic touches the bottom and right edges.

Water flows from a cell to a neighbouring cell (up, down, left or right) only if that neighbour is at the same height or lower. Return every cell from which water can reach both oceans, as [row, col] pairs sorted by row and then column.

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

Example 2

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

Example 3

Input: heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]

Constraints

• 1 <= heights.length, heights[i].length <= 10
• 0 <= heights[i][j] <= 100000

Hints for Pacific Atlantic Water Flow

1. Hint 1

   Searching downhill from every cell is quadratic — search uphill from the oceans instead.

2. Hint 2

   Flood inward from all Pacific-edge cells at once, moving only to neighbours of equal or greater height, then repeat for the Atlantic.

3. Hint 3

   The answer is the intersection of the two reachable sets.

How to solve Pacific Atlantic Water Flow

Search uphill from each ocean: flood from all Pacific-edge cells moving to neighbours of equal or greater height, repeat for the Atlantic, and intersect.

Approach

1. flow(starts) DFS from the edge cells, stepping only to heights[next] >= heights[cur].
2. Run it for the top/left edges and the bottom/right edges.
3. Emit cells marked by both, in row-major order.

Why it works

Water flows downhill from a cell to an ocean iff the reverse walk climbs from the ocean to the cell, so the two uphill floods compute exactly the cells that drain to each ocean.

Complexity

• Time — O(m · n)
• Space — O(m · n)

Pitfalls

• Flooding downhill from every cell repeats work and is quadratic.

Reference solution

Python

def pacificAtlantic(heights):
    rows, cols = len(heights), len(heights[0])

    def flow(starts):
        seen = [[False] * cols for _ in range(rows)]
        stack = []
        for r, c in starts:
            seen[r][c] = True
            stack.append((r, c))
        while stack:
            r, c = stack.pop()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and not seen[nr][nc]:
                    if heights[nr][nc] >= heights[r][c]:
                        seen[nr][nc] = True
                        stack.append((nr, nc))
        return seen

    pacific_starts = [(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)]
    atlantic_starts = [(rows - 1, c) for c in range(cols)] + [(r, cols - 1) for r in range(rows)]
    pacific = flow(pacific_starts)
    atlantic = flow(atlantic_starts)
    return [[r, c] for r in range(rows) for c in range(cols) if pacific[r][c] and atlantic[r][c]]

Java

private static boolean[][] oceanFlow(int[][] heights, List<int[]> starts) {
    int rows = heights.length, cols = heights[0].length;
    boolean[][] seen = new boolean[rows][cols];
    Deque<int[]> stack = new ArrayDeque<>();
    for (int[] s : starts) {
        seen[s[0]][s[1]] = true;
        stack.push(s);
    }
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    while (!stack.isEmpty()) {
        int[] cell = stack.pop();
        for (int d = 0; d < 4; d++) {
            int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || seen[nr][nc]) continue;
            if (heights[nr][nc] < heights[cell[0]][cell[1]]) continue;
            seen[nr][nc] = true;
            stack.push(new int[]{nr, nc});
        }
    }
    return seen;
}

public static int[][] pacificAtlantic(int[][] heights) {
    int rows = heights.length, cols = heights[0].length;
    List<int[]> pacificStarts = new ArrayList<>();
    List<int[]> atlanticStarts = new ArrayList<>();
    for (int c = 0; c < cols; c++) {
        pacificStarts.add(new int[]{0, c});
        atlanticStarts.add(new int[]{rows - 1, c});
    }
    for (int r = 0; r < rows; r++) {
        pacificStarts.add(new int[]{r, 0});
        atlanticStarts.add(new int[]{r, cols - 1});
    }
    boolean[][] pacific = oceanFlow(heights, pacificStarts);
    boolean[][] atlantic = oceanFlow(heights, atlanticStarts);
    List<int[]> out = new ArrayList<>();
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (pacific[r][c] && atlantic[r][c]) out.add(new int[]{r, c});
        }
    }
    return out.toArray(new int[0][]);
}

C++

static vector<vector<bool>> oceanFlow(vector<vector<int>>& heights, vector<pair<int,int>>& starts) {
    int rows = (int) heights.size(), cols = (int) heights[0].size();
    vector<vector<bool>> seen(rows, vector<bool>(cols, false));
    vector<pair<int,int>> stack;
    for (const auto& s : starts) {
        seen[s.first][s.second] = true;
        stack.push_back(s);
    }
    int dr[4] = {1, -1, 0, 0};
    int dc[4] = {0, 0, 1, -1};
    while (!stack.empty()) {
        pair<int,int> cell = stack.back();
        stack.pop_back();
        for (int d = 0; d < 4; d++) {
            int nr = cell.first + dr[d], nc = cell.second + dc[d];
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || seen[nr][nc]) continue;
            if (heights[nr][nc] < heights[cell.first][cell.second]) continue;
            seen[nr][nc] = true;
            stack.push_back(make_pair(nr, nc));
        }
    }
    return seen;
}

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int rows = (int) heights.size(), cols = (int) heights[0].size();
    vector<pair<int,int>> pacificStarts, atlanticStarts;
    for (int c = 0; c < cols; c++) {
        pacificStarts.push_back(make_pair(0, c));
        atlanticStarts.push_back(make_pair(rows - 1, c));
    }
    for (int r = 0; r < rows; r++) {
        pacificStarts.push_back(make_pair(r, 0));
        atlanticStarts.push_back(make_pair(r, cols - 1));
    }
    vector<vector<bool>> pacific = oceanFlow(heights, pacificStarts);
    vector<vector<bool>> atlantic = oceanFlow(heights, atlanticStarts);
    vector<vector<int>> out;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (pacific[r][c] && atlantic[r][c]) out.push_back(vector<int>{r, c});
        }
    }
    return out;
}

JavaScript

var pacificAtlantic = function(heights) {
    const rows = heights.length, cols = heights[0].length;
    const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    const flow = function(starts) {
        const seen = [];
        for (let r = 0; r < rows; r++) {
            const row = [];
            for (let c = 0; c < cols; c++) row.push(false);
            seen.push(row);
        }
        const stack = [];
        for (let i = 0; i < starts.length; i++) {
            seen[starts[i][0]][starts[i][1]] = true;
            stack.push(starts[i]);
        }
        while (stack.length > 0) {
            const cell = stack.pop();
            for (let d = 0; d < 4; d++) {
                const nr = cell[0] + dr[d], nc = cell[1] + dc[d];
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || seen[nr][nc]) continue;
                if (heights[nr][nc] < heights[cell[0]][cell[1]]) continue;
                seen[nr][nc] = true;
                stack.push([nr, nc]);
            }
        }
        return seen;
    };
    const pacificStarts = [], atlanticStarts = [];
    for (let c = 0; c < cols; c++) {
        pacificStarts.push([0, c]);
        atlanticStarts.push([rows - 1, c]);
    }
    for (let r = 0; r < rows; r++) {
        pacificStarts.push([r, 0]);
        atlanticStarts.push([r, cols - 1]);
    }
    const pacific = flow(pacificStarts);
    const atlantic = flow(atlanticStarts);
    const out = [];
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (pacific[r][c] && atlantic[r][c]) out.push([r, c]);
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium