417. Pacific Atlantic Water Flow

How to solve Pacific Atlantic Water Flow (LeetCode 417): the approach in brief

The problem

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

Pattern

Pacific Atlantic Water Flow is a Graph Traversal Patterns (DFS & BFS) problem, in the Graph DFS - Connected Components / Island Counting subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.

Approach outline

1. Consider how to model the problem as a graph traversal where each cell is a node connected to its neighbors if water can flow between them.
2. Think about starting your traversal not from each cell individually, but from the ocean borders and moving inward to find which cells can reach the oceans.
3. Use two separate traversals (DFS or BFS): one starting from all cells adjacent to the Pacific Ocean and one from the Atlantic Ocean, marking reachable cells for each.

Complexity

The reference solution runs in O(m * n) time and O(m * n) space.

Asked at

Pacific Atlantic Water Flow has been reported in interviews at Amazon, Bloomberg, ByteDance, Facebook, Google, Microsoft, Oracle.