Sweaty Imposter

Pacific Atlantic Water Flow

MediumGraph BFS/DFSBlind 75MidOpen on LeetCodeUpdated

You're given an m x n grid heights of land elevations. The Pacific Ocean touches the top and left edges, and the Atlantic Ocean touches the bottom and right edges. Rain on a cell can flow to a neighbor up, down, left or right whose height is less than or equal to its own, and any cell on an edge flows straight into the ocean beside it. Return the coordinates [r, c] of every cell whose water can reach both oceans, in any order.

Examples

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]] returns [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

01234012341223532344245316714551124
Highlighted cells drain to both oceans. The Pacific is along the top and left, the Atlantic along the bottom and right.

Cell [2,2] (height 5) flows up through 3 and 2 to the top edge, reaching the Pacific, and right through 3 and 1 to the right edge, reaching the Atlantic. Corners [0,4] and [4,0] touch both oceans directly.

heights = [[1]] returns [[0,0]]

The only cell touches all four edges, so its water drains into both oceans.

Constraints

  • 1 <= m, n <= 200
  • 0 <= heights[i][j] <= 10^5

Hints

Hint 1

Instead of asking which cells can reach the oceans, what about starting from the oceans and asking which cells they can reach?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Rather than tracing downhill paths from every cell, work backwards from the oceans. Start a depth-first search from every Pacific border cell and step only to neighbors at the same height or higher, since water could flow from them back down to you, marking every cell reached. Do the same from the Atlantic border into a second set. Cells in both sets can reach both oceans. Each search visits a cell at most once, so O(m * n) time and space.

Time

O(m * n)

Space

O(m * n)

Pitfall

Climbing the wrong way: searching inward from an ocean, you move to neighbors with height >= the current cell, not <=. Use >= rather than >, because water flows across equal heights.

Solutions

class Solution {
    private int m, n;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m = heights.length; n = heights[0].length;
        boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(heights, i, 0, pac, heights[i][0]);
            dfs(heights, i, n - 1, atl, heights[i][n - 1]);
        }
        for (int j = 0; j < n; j++) {
            dfs(heights, 0, j, pac, heights[0][j]);
            dfs(heights, m - 1, j, atl, heights[m - 1][j]);
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
            if (pac[i][j] && atl[i][j]) result.add(Arrays.asList(i, j));
        }
        return result;
    }

    private void dfs(int[][] h, int i, int j, boolean[][] visited, int prev) {
        if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || h[i][j] < prev) return;
        visited[i][j] = true;
        dfs(h, i + 1, j, visited, h[i][j]);
        dfs(h, i - 1, j, visited, h[i][j]);
        dfs(h, i, j + 1, visited, h[i][j]);
        dfs(h, i, j - 1, visited, h[i][j]);
    }
}
Drill This