Crack the Backend

Problem Statement

There is an m×n rectangular island; heights[r][c] is the height above sea level. The Pacific ocean touches the top and left edges; the Atlantic ocean touches the bottom and right. Water can flow from a cell to an adjacent cell if the neighbor's height is less than or equal to the current cell's height. Return all cells from which water can flow to both the Pacific and the Atlantic. (Flow can go to equal or lower neighbors.)

Reverse thinking: Instead of "where can water from (r,c) go?", we ask "which cells can receive water that ends in the Pacific?" That is: start from all Pacific border cells and do DFS/BFS where we can step to a neighbor with height >= current (water flows backward). Similarly from all Atlantic border cells. Cells that are reachable from both oceans (in the two reverse flows) are the answer.

Key Observations

Two passes: (1) From every cell on the Pacific border (r=0 or c=0), DFS/BFS with the rule: from (r,c) we can go to (nr,nc) if heights[nr][nc] >= heights[r][c]. Mark all reachable cells in pacific. (2) From every cell on the Atlantic border (r=m-1 or c=n-1), same rule, mark in atlantic. Return all (r,c) that are in both sets.
Use two boolean grids or sets. DFS is simpler; BFS works too.

Approach

High-level: pacific = reachable from Pacific border (reverse flow: step to neighbor with height >= current). atlantic = reachable from Atlantic border (same rule). Return (r,c) in both pacific and atlantic.

Steps: dfs(r, c, visited, heights): mark (r,c); for 4 neighbors in bounds, if heights[nr][nc] >= heights[r][c] and not visited, dfs(nr, nc, ...). Call dfs from all (0,j) and (i,0) into pacific set; from all (m-1,j) and (i,n-1) into atlantic set. Return cells in both.

Implementation

Java

public List<List<Integer>> pacificAtlantic(int[][] heights) {
    List<List<Integer>> result = new ArrayList<>();
    int m = heights.length, n = heights[0].length;
    boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];

    for (int r = 0; r < m; r++) { dfs(heights, pac, r, 0); dfs(heights, atl, r, n-1); }
    for (int c = 0; c < n; c++) { dfs(heights, pac, 0, c); dfs(heights, atl, m-1, c); }
    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;
}

void dfs(int[][] h, boolean[][] vis, int r, int c) {
    vis[r][c] = true;

    for (int[] d : new int[][]{{-1,0},{1,0},{0,-1},{0,1}}) {
        int nr = r+d[0], nc = c+d[1];

        if (nr>=0&&nr<h.length&&nc>=0&&nc<h[0].length&&!vis[nr][nc]&&h[nr][nc]>=h[r][c])
        dfs(h, vis, nr, nc);
    }
}

Test Cases

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

Expected

[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Explanation

Cells that flow to both oceans.

Complexity Analysis

Time: O(m*n).
Space: O(m*n).

Follow-ups

One ocean only; different flow rules.