Abstract / Summary

Water can flow to both the Pacific and Atlantic oceans from certain cells in a grid of heights.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 61% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Depth First Search
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “Pacific Atlantic Water Flow” problem. It determines every cell in a rectangular height map from which water can flow to both the Pacific and Atlantic oceans. The algorithm treats the ocean borders as sources and performs a depth-first flood fill that only moves to neighboring cells of equal or greater height. The final result is the intersection of the two reachable cell sets.

Core Logic

Dimension Extraction

width  = len(heights[0])
height = len(heights)

The code extracts the number of columns (width) and rows (height) from the input matrix. This information is used throughout the flood-fill to stay within bounds.

Recursive Flood-Fill Function

def up(x, y, ocean):
    if (y, x) in ocean:
        return
    ocean.add((y, x))

    level = heights[y][x]
    if x > 0          and heights[y][x - 1] >= level:
        up(x - 1, y, ocean)
    if x < width - 1  and heights[y][x + 1] >= level:
        up(x + 1, y, ocean)
    if y > 0          and heights[y - 1][x] >= level:
        up(x, y - 1, ocean)
    if y < height - 1 and heights[y + 1][x] >= level:
        up(x, y + 1, ocean)

The up function performs a depth-first search from a given cell (x, y). It first checks whether the cell has already been visited for the current ocean; if so, the recursion stops, preventing redundant work. The cell is then recorded in the ocean set. The function proceeds to explore the four orthogonal neighbors, but only when the neighbor’s height is not lower than the current cell’s height. This monotonic condition guarantees that water can flow from the neighbor to the current cell, which is the reverse of the natural flow direction.

Ocean Sets Initialization

pacific  = set()
atlantic = set()

Two distinct sets store the coordinates reachable from the Pacific and Atlantic borders, respectively. Using a set provides O(1) membership checks, which is crucial for the early-exit condition inside up.

Border Traversal

for i in range(width):
    up(i, 0,          pacific)
    up(i, height - 1, atlantic)

for i in range(height):
    up(0,         i,  pacific)
    up(width - 1, i,  atlantic)

The algorithm initiates flood-fills from every cell that touches an ocean. The first loop walks the top row (Pacific) and bottom row (Atlantic). The second loop walks the left column (Pacific) and right column (Atlantic). By launching a separate flood-fill from each border cell, the code ensures that any interior cell that can reach a border through non-decreasing heights will be captured in the corresponding set.

Intersection of Reachable Cells

return pacific & atlantic

The final result consists of cells that appear in both pacific and atlantic. The set intersection operation efficiently yields exactly those coordinates from which water can flow to both oceans.

Edge Cases Handled

The recursion guard if (y, x) in ocean: return protects against infinite loops on flat regions where neighboring cells share the same height. When the height map consists of a single row, the first loop processes the entire row for both oceans, while the second loop processes the same cells again; the guard prevents duplicate work. Similarly, a single column triggers the same protective behavior. Uniform height matrices are handled gracefully because every neighbor satisfies the >= level condition, yet each cell is visited only once per ocean due to the set membership check.

Performance Optimizations

The algorithm leverages several implicit optimizations. Storing visited cells in a hash set eliminates repeated exploration of the same coordinate, which is especially beneficial for large plateaus. The early return on already-visited cells reduces the recursion depth dramatically compared with a naïve flood-fill that would revisit cells through multiple paths. By launching flood-fills from the borders rather than from every interior cell, the total number of recursive calls is bounded by the size of the matrix rather than by the square of that size. The use of Python’s built-in set intersection (&) provides a fast, compiled implementation for combining the two result sets.

Overall, the solution combines a concise recursive flood-fill with set-based bookkeeping to achieve an elegant and efficient traversal of the height map, correctly identifying all cells that can drain into both oceans.

Imagine a big rectangular island covered in hills and valleys. Rain falls on the island, and the water wants to flow down into the sea. One sea is on the top and left sides of the island, and the other sea is on the bottom and right sides. This code acts like a tiny robot that starts at the beaches where the water meets the land.

The robot looks at each square of land and asks if the ground next to it is the same height or even higher. If the robot finds a spot that is taller or just as tall, it can hop over to that spot. It keeps hopping as far as it can go inland, marking every place it visits as a spot that can reach that specific sea.

The robot does this starting from the top and left edges to find all the places that can send water to the Pacific ocean. Then, it does the exact same thing starting from the bottom and right edges to find all the places that can send water to the Atlantic ocean. By the time the robot is finished hopping around, it looks for the special spots that were visited during both trips. Those spots are the only places on the island where water can flow down into both oceans at the same time.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		Rust			Go			TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	black-shadows	C++
	bujosa		Python
	charles-wangkai			Java
	everthis				JS
	fartem						Ruby
	fengvyi	C++
	fpdjsns	C++
	halfrost								Go
	JoshCrozier				JS
	linouk23	C++
	lkwq007		Python
	ruoru					Rust
	suxrobGM									C#
	trung-hn		Python
	varunu28			Java
	vli02										C
	vthwang			Java
	wisdompeak	C++
	withaarzoo	C++
	yuanliu666							Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
halfrost	Go
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
withaarzoo	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality