150NeetCode 150

83.Pacific Atlantic Water Flow

MediumBlind 75Graphs · 4/19
LeetCode #417Video

Problem

An m x n island is described by heights, where heights[r][c] is the height of cell (r, c). The Pacific Ocean touches the island's top and left edges; the Atlantic Ocean touches its bottom and right edges.

Rain water can flow from a cell to a 4-directionally adjacent cell if that neighbour's height is less than or equal to the current height. Water flows from any cell on an edge directly into the ocean beside that edge.

Return a list of grid coordinates [r, c] from which rain water can reach both the Pacific and the Atlantic. The order of the result does not matter.

Examples

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: e.g. from (2,2) (height 5) water flows up 5→3→2 to the top edge (Pacific) and right 5→3→1 to the right edge (Atlantic).
Input:  heights = [[1]]
Output: [[0,0]]
Explanation: A single cell touches all four edges, so it drains into both oceans.
Input:  heights = [
  [1,2,3],
  [8,9,4],
  [7,6,5]
]
Output: [[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
Explanation: (0,0) and (0,1) are surrounded by higher cells on the Atlantic side, so they only reach the Pacific.

Constraints

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

💡 Key Insight

Asking "where can water from this cell go?" for every cell repeats the same searches. Flip the direction: start at the oceans and walk uphill (to neighbours with height >= the current one). Every cell reached from the Pacific border can drain into the Pacific, and likewise for the Atlantic. Run one multi-source search per ocean, then return the cells marked by both. Each search visits each cell at most once, so the total is O(m·n).

Brute Force

TimeO((m·n)²)SpaceO(m·n)

Intuition

Simulate the rain directly. From each cell, explore every cell water could flow to (neighbours with height <= the current cell). If that exploration touches the top/left edge the cell reaches the Pacific; if it touches the bottom/right edge it reaches the Atlantic. Stop as soon as both are confirmed.

Algorithm

  1. For each cell (r, c):
    • BFS downhill with a fresh visited array.
    • For every reached cell, set pacific = true if its row is 0 or column is 0, and atlantic = true if its row is m - 1 or column is n - 1.
    • If both are true, add [r, c] to the result.
  2. Return the result.

Visualization

heights           start (0,1) = 2, flow to cells with height <= 2
1 2 3
8 9 4             reached: (0,1) → (0,0)=1
7 6 5             (0,0) touches top/left → Pacific ✓
                  no reached cell on bottom row / right column → Atlantic ✗
                  → (0,1) not in answer

Code

java
import java.util.*;

class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int rows = heights.length, cols = heights[0].length;
        List<List<Integer>> result = new ArrayList<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (reachesBoth(heights, r, c)) {
                    result.add(Arrays.asList(r, c));
                }
            }
        }
        return result;
    }

    // BFS downhill from (r, c) and see which ocean edges are touched
    private boolean reachesBoth(int[][] heights, int r, int c) {
        int rows = heights.length, cols = heights[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;
        boolean pacific = false, atlantic = false;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int cr = cell[0], cc = cell[1];
            if (cr == 0 || cc == 0) pacific = true;
            if (cr == rows - 1 || cc == cols - 1) atlantic = true;
            if (pacific && atlantic) return true;

            for (int[] d : DIRS) {
                int nr = cr + d[0], nc = cc + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]
                        && heights[nr][nc] <= heights[cr][cc]) { // water flows down or level
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        return false;
    }
}

Complexity

  • Time: O((m·n)²) — a BFS of up to m·n cells is launched from each of the m·n cells.
  • Space: O(m·n) — visited and the queue for one search.

Complexity Comparison

Approach Time Space
Brute Force O((m·n)²) O(m·n)
Reverse DFS O(m·n) O(m·n)
Reverse Multi-Source BFS O(m·n) O(m·n)

Common Pitfalls

  • Using the downhill comparison (<=) in the reverse search — from the ocean you must climb, so the neighbour must satisfy heights[nr][nc] >= heights[r][c].
  • Using strict > and missing flat plateaus; water flows between cells of equal height.
  • Mixing up the edges: Pacific is top row + left column, Atlantic is bottom row + right column. Corner (0, n-1) and (m-1, 0) touch both oceans.
  • Sharing one visited matrix between the two oceans — a cell reached from the Pacific would then never be explored from the Atlantic.
  • Memoizing per-cell results in the brute force with plain DFS; cycles between equal-height cells make naive memoization return wrong answers.