◀ THE GRIND — GRAPHS

Pacific Atlantic Water Flow

MEDIUM✓ CHIP-TIMEDLC #417 — FULL STATEMENT ↗

The drill: A height grid touches the Pacific along its top and left edges and the Atlantic along its bottom and right edges. Water flows from a cell to a neighbour only when the neighbour's height is less than or equal to its own. Find every cell that can reach both oceans.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A grid of heights represents terrain, with the Pacific Ocean bordering the top and left edges and the Atlantic bordering the bottom and right edges. Water can flow from any cell to an orthogonal neighbor only when that neighbor's height is equal to or lower than the current cell's.

The task is to find every cell from which water could eventually reach both oceans by following that downhill-or-flat rule repeatedly, in any direction the terrain allows.

A cell sitting right on two borders at once already touches both oceans directly. The answer is the full list of such dual-reaching cells, in any order.

EX 01
heights = [[5]]
→ [[0, 0]]
SINGLE CELL TOUCHES BOTH OCEANS TRIVIALLY
EX 02
heights = [[3, 3, 3]]
→ [[0, 0], [0, 1], [0, 2]]
SINGLE ROW TOUCHES BOTH OCEANS ON EVERY CELL
EX 03
heights = [[5], [3], [8]]
→ [[0, 0], [1, 0], [2, 0]]
SINGLE COLUMN TOUCHES BOTH OCEANS ON EVERY CELL
THE HINTS — TAKE ONLY WHAT YOU NEED
HINT 1 THE NUDGE

Checking, for every cell, whether it can downhill-flow all the way to both borders is correct but repeats the same downhill paths over and over. What if the search started from the oceans instead?

HINT 2 THE STRUCTURE

Run the flow backwards from the border: from an ocean's edge cells, walk to any neighbour that is equal or taller — the reverse of 'flows to' — and that's exactly the set of cells that can flow down to that ocean.

HINT 3 ONE STEP FROM THE ANSWER

Two multi-source searches, one seeded from every Pacific-edge cell and one from every Atlantic-edge cell, each moving to equal-or-taller neighbours; the answer is every cell visited by both searches.

COACH'S BOARD — THE PATTERN, STEP BY STEP
THE UPHILL FLOODPATTERN · REVERSE FLOW FROM BOTH OCEANSheights = [[5,4,3],[4,3,2],[3,2,1]]
5
4
3
4
3
2
3
2
1
STEP 1

Heights slope down from a peak of 5 at the top-left to 1 at the bottom-right. Flood backward: from each ocean to a neighbor that's equal or TALLER.

STEP 1 / 7 · ← → WORK TOO
THE SPLITS — TWO PACES, TWO LANGUAGES
grind/pacific-atlantic-water-flow.py — RACE PACE
LANG ▸
PACE ▸
class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        rows, cols = len(heights), len(heights[0])
        pacific = [[False] * cols for _ in range(rows)]
        atlantic = [[False] * cols for _ in range(rows)]

        def flood(visited, starts):
            queue = collections.deque(starts)
            for r, c in starts:
                visited[r][c] = True
            while queue:
                r, c = queue.popleft()
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and heights[nr][nc] >= heights[r][c]:
                        visited[nr][nc] = True
                        queue.append((nr, nc))

        pacific_starts = [(r, 0) for r in range(rows)] + [(0, c) for c in range(cols)]
        atlantic_starts = [(r, cols - 1) for r in range(rows)] + [(rows - 1, c) for c in range(cols)]
        flood(pacific, pacific_starts)
        flood(atlantic, atlantic_starts)

        return [[r, c] for r in range(rows) for c in range(cols) if pacific[r][c] and atlantic[r][c]]
TIME O(ROWS·COLS)SPACE O(ROWS·COLS)PYTHON · RACE PACE · 24 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED