Pacific Atlantic Water Flow

Problem Description

There is an m × n rectangular island that borders both the Pacific Ocean (left and top edges) and Atlantic Ocean (right and bottom edges).

The island is partitioned into a grid of square cells. You are given an m × n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

Rain water can flow to neighboring cells in four directions (up, down, left, right) if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into that ocean.

Return a 2D list of grid coordinates result where result[i] = [r, c] denotes that rain water can flow from cell (r, c) to both the Pacific and Atlantic oceans.

Examples

Constraints

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

Reversing the Flow: Backtracking from Oceans to Peaks

Checking each cell individually to see if water can reach both oceans is too slow, costing O((M * N)²) time.

Instead of tracking water flowing downward from peaks to oceans, we reverse the logic: we track water flowing upward from the oceans to the peaks.

• Start a search from the top and left borders (Pacific Ocean cells). Any cell we can reach by stepping on nodes of equal or greater height can flow to the Pacific Ocean. Mark these cells in a pacific visited set.
• Start a search from the bottom and right borders (Atlantic Ocean cells) using the same logic. Mark these cells in an atlantic visited set.

After completing both searches, the cells that appear in both visited sets are the cells from which water can flow to both oceans.

Solution 1: DFS from Ocean Borders

Run a DFS starting from all border cells, climbing upward onto adjacent cells of equal or greater height.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> result = new ArrayList<>();
        if (heights == null || heights.length == 0) return result;

        int rows = heights.length;
        int cols = heights[0].length;
        boolean[][] pacific = new boolean[rows][cols];
        boolean[][] atlantic = new boolean[rows][cols];

        // dfs from top and bottom borders
        for (int c = 0; c < cols; c++) {
            dfs(heights, 0, c, Integer.MIN_VALUE, pacific);
            dfs(heights, rows - 1, c, Integer.MIN_VALUE, atlantic);
        }

        // dfs from left and right borders
        for (int r = 0; r < rows; r++) {
            dfs(heights, r, 0, Integer.MIN_VALUE, pacific);
            dfs(heights, r, cols - 1, Integer.MIN_VALUE, atlantic);
        }

        // collect cells reachable by both oceans
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (pacific[r][c] && atlantic[r][c]) {
                    result.add(Arrays.asList(r, c));
                }
            }
        }
        return result;
    }

    private void dfs(int[][] heights, int r, int c, int prevHeight, boolean[][] visited) {
        int rows = heights.length;
        int cols = heights[0].length;

        // boundary and height constraints (must climb upward, so heights[r][c] >= prevHeight)
        if (r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c] || heights[r][c] < prevHeight) {
            return;
        }

        visited[r][c] = true;

        dfs(heights, r + 1, c, heights[r][c], visited);
        dfs(heights, r - 1, c, heights[r][c], visited);
        dfs(heights, r, c + 1, heights[r][c], visited);
        dfs(heights, r, c - 1, heights[r][c], visited);
    }
}

class Solution:
    def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
        if not heights:
            return []

        rows, cols = len(heights), len(heights[0])
        pacific = [[False] * cols for _ in range(rows)]
        atlantic = [[False] * cols for _ in range(rows)]

        def dfs(r, c, prev_height, visited):
            # boundary and height constraints (must climb upward)
            if (
                r < 0
                or r >= rows
                or c < 0
                or c >= cols
                or visited[r][c]
                or heights[r][c] < prev_height
            ):
                return

            visited[r][c] = True

            dfs(r + 1, c, heights[r][c], visited)
            dfs(r - 1, c, heights[r][c], visited)
            dfs(r, c + 1, heights[r][c], visited)
            dfs(r, c - 1, heights[r][c], visited)

        # dfs from top and bottom borders
        for c in range(cols):
            dfs(0, c, -1, pacific)
            dfs(rows - 1, c, -1, atlantic)

        # dfs from left and right borders
        for r in range(rows):
            dfs(r, 0, -1, pacific)
            dfs(r, cols - 1, -1, atlantic)

        # collect cells reachable by both oceans
        result = []
        for r in range(rows):
            for c in range(cols):
                if pacific[r][c] and atlantic[r][c]:
                    result.append([r, c])

        return result

#include <vector>
#include <algorithm>

class Solution {
private:
    void dfs(std::vector<std::vector<int>>& heights, int r, int c, int prevHeight, std::vector<std::vector<bool>>& visited) {
        int rows = heights.size();
        int cols = heights[0].size();

        // boundary and height constraints (must climb upward)
        if (r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c] || heights[r][c] < prevHeight) {
            return;
        }

        visited[r][c] = true;

        dfs(heights, r + 1, c, heights[r][c], visited);
        dfs(heights, r - 1, c, heights[r][c], visited);
        dfs(heights, r, c + 1, heights[r][c], visited);
        dfs(heights, r, c - 1, heights[r][c], visited);
    }

public:
    std::vector<std::vector<int>> pacificAtlantic(std::vector<std::vector<int>>& heights) {
        std::vector<std::vector<int>> result;
        if (heights.empty()) return result;

        int rows = heights.size();
        int cols = heights[0].size();
        std::vector<std::vector<bool>> pacific(rows, std::vector<bool>(cols, false));
        std::vector<std::vector<bool>> atlantic(rows, std::vector<bool>(cols, false));

        // dfs from top and bottom borders
        for (int c = 0; c < cols; c++) {
            dfs(heights, 0, c, -1, pacific);
            dfs(heights, rows - 1, c, -1, atlantic);
        }

        // dfs from left and right borders
        for (int r = 0; r < rows; r++) {
            dfs(heights, r, 0, -1, pacific);
            dfs(heights, r, cols - 1, -1, atlantic);
        }

        // collect cells reachable by both oceans
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (pacific[r][c] && atlantic[r][c]) {
                    result.push_back({r, c});
                }
            }
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(M * N) where M is the number of rows and N is the number of columns. We initiate traversals from the borders, visiting each cell at most once per ocean search.
• Space Complexity: O(M * N) to store the pacific and atlantic visited matrices.

Where it breaks: On grids with flat heights (e.g. all values equal to 5), the search will scan the entire grid because heights[r][c] >= prevHeight is satisfied at every step. This is handled correctly, but can use the maximum stack space.

Common Mistakes

• Incorrect flow direction logic. Remember we are moving from the oceans inward to the peaks. This means we must check if the next cell is greater than or equal to the current cell, not smaller.
• Not tracking visited nodes independently for both oceans. If you use a single visited matrix, searches from the Pacific and Atlantic will block each other, producing incomplete results.
• Failing to reset limits correctly at starting borders. Initialize the prevHeight parameter to -1 or Integer.MIN_VALUE so that border cells (which can have a height of 0) pass the check.

Frequently Asked Questions

Can we solve this using Breadth-First Search (BFS)? Yes. You can initialize two queues (one for Pacific border cells, one for Atlantic) and run two standard BFS traversals, verifying the heights[neighbor] >= heights[curr] condition on insertion.

Is it possible to optimize the space complexity? You can use integer bitmasks in a single gridState array instead of two boolean arrays (e.g., set bit 0 for Pacific, bit 1 for Atlantic). This halves the auxiliary memory usage but keeps space complexity at O(M * N).

What does this problem test in interviews? It tests your ability to adapt graph search algorithms (DFS/BFS) by reversing the search perspective to avoid redundant calculations.

← All Problems