Pacific Atlantic Water Flow

Why it belongs on this sheet

This is a capstone grid problem because the winning idea is to reverse the perspective.

Pattern

Reverse traversal from boundaries

Approach

Instead of starting from every cell and checking both oceans, start from each ocean border and walk inward to cells that can flow back into it. Intersect the two reachable sets.

Java solution

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

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

  public List<List<Integer>> pacificAtlantic(int[][] heights) {
    int rows = heights.length;
    int cols = heights[0].length;
    boolean[][] pacific = new boolean[rows][cols];
    boolean[][] atlantic = new boolean[rows][cols];

    for (int row = 0; row < rows; row++) {
      dfs(heights, pacific, row, 0, heights[row][0]);
      dfs(heights, atlantic, row, cols - 1, heights[row][cols - 1]);
    }

    for (int col = 0; col < cols; col++) {
      dfs(heights, pacific, 0, col, heights[0][col]);
      dfs(heights, atlantic, rows - 1, col, heights[rows - 1][col]);
    }

    List<List<Integer>> answer = new ArrayList<>();
    for (int row = 0; row < rows; row++) {
      for (int col = 0; col < cols; col++) {
        if (pacific[row][col] && atlantic[row][col]) {
          answer.add(List.of(row, col));
        }
      }
    }

    return answer;
  }

  private void dfs(int[][] heights, boolean[][] seen, int row, int col, int previousHeight) {
    if (
      row < 0 || col < 0 || row == heights.length || col == heights[0].length
      || seen[row][col] || heights[row][col] < previousHeight
    ) {
      return;
    }

    seen[row][col] = true;
    for (int[] direction : DIRECTIONS) {
      dfs(heights, seen, row + direction[0], col + direction[1], heights[row][col]);
    }
  }
}

Complexity

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

Interview note

The sentence to remember is: "start from the oceans, not from every land cell."