☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Pacific Atlantic Water Flow

Easy TUF ID 2403 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an m x n grid heights of an island. The Pacific Ocean touches the island’s top and left edges; the Atlantic Ocean touches its bottom and right edges. Rain falling on a cell flows to any of its four side neighbours whose height is less than or equal to the current cell’s height. Water in a cell on the border flows straight into the ocean that border touches.

Return every cell [r, c] from which rain can reach both oceans. The Java methods list them in row-major order (by row, then column).

Constraints: 1 ≤ m, n ≤ 200, 0 ≤ heights[r][c] ≤ 10^5.

Example 1

            Pacific (top and left)
   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
            Atlantic (bottom and right)
answer = [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

For example, (2,2) with height 5 can flow up to (1,2) = 3, then (0,2) = 2 on the top edge (Pacific), and also right to (2,3) = 3, then (2,4) = 1 on the right edge (Atlantic).

Example 2

heights = [[1]]
answer = [[0,0]]      // a single cell touches all four edges

Note that “flow” allows equal heights: on a flat grid every cell can reach every border.

Approach 1: Brute force, simulate the rain from every cell

Intuition. Take the question literally. For each cell, find every cell its water can reach by repeatedly moving to a neighbour that is not higher, using a BFS. While doing so, record whether the water ever stands on a top/left border cell (Pacific) or a bottom/right border cell (Atlantic). If both happen, the cell belongs in the answer. The search can stop early once both oceans are found.

Algorithm.

  1. For each cell (r, c): BFS with a fresh seen grid, moving only to neighbours with height <= current height.
  2. Set pacific if a visited cell has x == 0 or y == 0, and atlantic if x == m - 1 or y == n - 1.
  3. If both flags are set, add [r, c] to the result.
static List<List<Integer>> bruteForce(int[][] heights) {
    int 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++) {
            boolean pacific = false, atlantic = false;
            boolean[][] seen = new boolean[m][n];
            Deque<int[]> queue = new ArrayDeque<>();
            seen[r][c] = true;
            queue.add(new int[]{r, c});
            while (!queue.isEmpty() && !(pacific && atlantic)) {
                int[] cell = queue.poll();
                int x = cell[0], y = cell[1];
                if (x == 0 || y == 0) pacific = true;           // top or left edge
                if (x == m - 1 || y == n - 1) atlantic = true;  // bottom or right edge
                for (int d = 0; d < 4; d++) {
                    int nx = x + DR[d], ny = y + DC[d];
                    if (nx < 0 || ny < 0 || nx >= m || ny >= n || seen[nx][ny]) continue;
                    if (heights[nx][ny] <= heights[x][y]) {     // water moves to an equal or lower cell
                        seen[nx][ny] = true;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
            if (pacific && atlantic) result.add(List.of(r, c));
        }
    }
    return result;
}

Complexity. Time O((m · n)^2): one BFS of up to m · n cells for each of the m · n cells. With 200 x 200 that is 1.6 · 10^9 steps in the worst case. Space O(m · n) for one seen grid and queue.

The waste is that neighbouring cells repeat nearly the same search. And we are asking the question from the wrong end: there are m · n sources of rain but only two destinations.

Approach 2: Optimal, reverse the flow from each ocean

Intuition. Instead of asking “where can water from this cell go?”, ask “which cells can send water into this ocean?” Water flows from a cell A into a neighbour B when height[B] <= height[A]. Reverse every arrow: from B we may step back to A whenever height[A] >= height[B], that is, we climb to neighbours that are at least as high.

Start a BFS from all Pacific border cells at once (top row and left column). They reach the Pacific trivially. Climbing uphill from them reaches exactly the cells whose water can flow down into one of them, and so into the Pacific. Do the same from the Atlantic border (bottom row and right column). The answer is the set of cells marked by both searches.

This is a multi-source BFS: all border cells start in the queue together, and a shared reach grid ensures each cell is processed at most once per ocean, however many border cells could reach it.

Algorithm.

  1. Mark and enqueue every cell in column 0 and row 0 for the Pacific, and every cell in column n - 1 and row m - 1 for the Atlantic.
  2. For each ocean, BFS: from a cell, step to an in-bounds, unmarked neighbour whose height is >= the current height; mark and enqueue it.
  3. Collect the cells marked in both grids, in row-major order.
static List<List<Integer>> optimal(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
    Deque<int[]> pq = new ArrayDeque<>(), aq = new ArrayDeque<>();
    for (int r = 0; r < m; r++) {
        mark(pac, pq, r, 0);                          // left edge touches the Pacific
        mark(atl, aq, r, n - 1);                      // right edge touches the Atlantic
    }
    for (int c = 0; c < n; c++) {
        mark(pac, pq, 0, c);                          // top edge
        mark(atl, aq, m - 1, c);                      // bottom edge
    }
    climb(heights, pac, pq);
    climb(heights, atl, aq);
    List<List<Integer>> result = new ArrayList<>();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (pac[r][c] && atl[r][c]) result.add(List.of(r, c));
        }
    }
    return result;
}

static void mark(boolean[][] reach, Deque<int[]> queue, int r, int c) {
    if (reach[r][c]) return;
    reach[r][c] = true;
    queue.add(new int[]{r, c});
}

/** Multi-source BFS that only steps to neighbours at least as high: those are cells whose water could flow down to us. */
static void climb(int[][] heights, boolean[][] reach, Deque<int[]> queue) {
    int m = heights.length, n = heights[0].length;
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        for (int d = 0; d < 4; d++) {
            int nr = cell[0] + DR[d], nc = cell[1] + DC[d];
            if (nr < 0 || nc < 0 || nr >= m || nc >= n || reach[nr][nc]) continue;
            if (heights[nr][nc] >= heights[cell[0]][cell[1]]) mark(reach, queue, nr, nc);
        }
    }
}

Dry run on a small grid [[1, 2], [4, 3]]:

ocean border seeds climbs to reachable set
Pacific (0,0)=1, (0,1)=2, (1,0)=4 from (0,1)=2 up to (1,1)=3 all four cells
Atlantic (0,1)=2, (1,0)=4, (1,1)=3 (0,0)=1 is lower than both neighbours, never reached (0,1), (1,0), (1,1)

Intersection: [[0,1],[1,0],[1,1]]. Cell (0,0) is on the Pacific border, but its water is trapped below heights 2 and 4, so it never reaches the Atlantic. The brute force agrees: from (0,0) there is no allowed move at all.

Complexity. Time O(m · n): each search marks every cell at most once and checks four neighbours per cell, and the final intersection is one more pass. Space O(m · n) for the two boolean grids and the queues.

Edge cases and pitfalls