TIC
The Interns Company

Pacific Atlantic Water Flow

MediumAcceptance: 42.5%

Problem Statement

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. The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c). The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean. Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Constraints:

  • m == heights.length
  • n == heights[r].length
  • 1 <= m, n <= 200
  • 0 <= heights[r][c] <= 10^5

Input Format:

  • An m x n integer matrix heights

Output Format:

  • A 2D list of grid coordinates where water can flow to both oceans

Examples:

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

Output:

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

Explanation:

The following cells can flow to both the Pacific and Atlantic oceans: [0,4], [1,3], [1,4], [2,2], [3,0], [3,1], [4,0].

Example 2:

Input:

heights = [[2,1],[1,2]]

Output:

[[0,0],[0,1],[1,0],[1,1]]

Explanation:

The following cells can flow to both the Pacific and Atlantic oceans: [0,0], [0,1], [1,0], [1,1].

Solutions

DFS Approach

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

Use DFS to find all cells that can reach each ocean. Start DFS from the borders of the matrix (which are adjacent to the oceans) and traverse inward. Then find cells that can reach both oceans.

BFS Approach

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

Use BFS to find all cells that can reach each ocean. Start BFS from the borders of the matrix and work inward. Then find cells that can reach both oceans.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Initialize pacific and atlantic visited arrays
  2. Perform DFS from Pacific borders (left and top)
  3. Perform DFS from Atlantic borders (right and bottom)
  4. Find cells that appear in both pacific and atlantic visited arrays
  5. Return [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Hints

Hint 1
Think about starting from the ocean and working backwards.
Hint 2
You can perform DFS or BFS from each ocean to find cells that can be reached from that ocean.
Hint 3
Then find the cells that can be reached from both oceans.

Video Tutorial

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the matrix with different colors showing cells reachable from the Pacific, Atlantic, or both oceans.

Key visualization elements:

  • Pacific reachable
  • Atlantic reachable
  • Both oceans reachable

Implementation Notes

This problem tests understanding of matrix traversal and is a good example of using DFS/BFS from the edges inward rather than traditional traversal.