DSA · Graphs · #131
Pacific Atlantic Water Flow
Module 55 · difficulty 3/5·⏱ 30:00starts on first keystroke
You are given an `m x n` integer matrix `heights` representing the height of each cell on an island. The Pacific Ocean touches the island's **left** and **top** edges; the Atlantic Ocean touches its **right** and **bottom** edges. Rain water flows from a cell to a neighbouring cell (up, down, left, or right) only if the neighbour's height is **less than or equal to** the current cell's height. Water can flow into an ocean from any cell adjacent to that ocean's edge. Implement `pacificAtlantic(heights)` which returns a list of grid coordinates `[r, c]` for every cell from which water can flow to **both** the Pacific and the Atlantic oceans. The order of the returned coordinates does not matter.
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]]→[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]— These cells can drain to both oceans; ordering may differ.heights = [[1]]→[[0,0]]— A single cell touches all four edges, so it reaches both oceans.heights = [[2,1],[1,2]]→[[0,0],[0,1],[1,0],[1,1]]— Every cell is adjacent to both a Pacific edge and an Atlantic edge.
Constraints
- · m == heights.length
- · n == heights[0].length
- · 1 <= m, n <= 200
- · 0 <= heights[r][c] <= 10^5
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.