Pacific Atlantic Water Flow

Explanation & Solution

Description

You are given an m x n rectangular island heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island borders two oceans:

The Pacific Ocean touches the island's top and left edges.
The Atlantic Ocean touches the island's bottom and right edges.

Water can flow from a cell to an adjacent cell (up, down, left, or right) if the adjacent cell's height is less than or equal to the current cell's height. Water can also flow to the ocean if the cell is adjacent to that ocean.

Return a list of coordinates [r, c] where water can flow to both the Pacific and Atlantic oceans. The result may be returned in any order.

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: The cells marked can reach both oceans. For example, cell [2,2] (height 5) is a local peak — water flows left/up toward the Pacific and right/down toward the Atlantic.

Constraints

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 100000

Approach

Graphs pattern

1. Reverse the Problem — Start from the Oceans

Instead of checking if each cell can reach both oceans (expensive), we reverse the direction
Start DFS from every ocean border cell and flow uphill (to cells with equal or greater height)
Build two boolean grids: pacific and atlantic

2. Initialize DFS from Pacific Border

The Pacific touches the top row and the left column
For every cell in the top row, run DFS marking all reachable cells in the pacific grid
For every cell in the left column, do the same

3. Initialize DFS from Atlantic Border

The Atlantic touches the bottom row and the right column
For every cell in the bottom row, run DFS marking all reachable cells in the atlantic grid
For every cell in the right column, do the same

4. DFS Logic (Reverse Flow)

Base cases: out of bounds, already visited, or current cell height is less than the previous cell (water can't flow uphill in the original direction, but in reverse we require equal or greater)
Mark the cell as reachable and recurse into all four neighbors

5. Find the Intersection

Iterate through every cell in the grid
If a cell is marked true in both pacific and atlantic, it can reach both oceans
Add [r, c] to the result list

Key Insight

Reversing the flow direction turns an expensive per-cell search into just two multi-source DFS passes — one from each ocean's border

Time

O(m × n)each cell is visited at most twice (once per ocean)

Space

O(m × n)for the two boolean grids and the recursion stack

Visualization

Input:

DFS Traversal5×5 grid

output—

Press play to start dfs traversal

CurrentQueuedVisitedSource

153 steps

Solution Code

Surrounded Regions

Word Search