Abstract / Summary

Find the earliest time when you can move from the top left to the bottom right by only stepping on cells with height less than or equal to the current time.

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 68% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Breadth First Search
• Depth First Search
• Heap (Priority Queue)
• Matrix
• Union Find

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 implementation solves the “Swim in Rising Water” problem by treating the grid as a graph where each cell is a node and edges exist between orthogonal neighbours. The algorithm explores the graph using a priority queue (min-heap) that always expands the reachable cell with the smallest water level requirement. The current water level is tracked as the maximum of all visited cell values, and the search stops as soon as the bottom-right corner is reached, returning that level.

Key Steps

Initialization

The size of the square grid is stored, the initial water level is set to the value at the top-left corner, and the priority queue is seeded with a tuple containing that level and the starting coordinates. An empty set records visited positions.

n = len(grid)

level = grid[0][0]
todo  = [ ( level, 0, 0 ) ]   # min-heap
seen  = set()

Main Loop

The algorithm repeatedly extracts the smallest-level entry from the heap. If the coordinates have already been processed, the iteration skips to the next entry. Otherwise the coordinates are marked as visited and the current water level is updated to the larger of the previous level and the extracted cell’s value.

while True:
    l, x, y = heappop(todo)

    if ( x, y ) in seen:
        continue
    seen.add(( x, y ))

    level = max(level, l)

Destination Check

Immediately after updating the level, the code checks whether the extracted cell is the target (bottom-right). If so, the current water level is the answer and the function returns it.

    if x == n - 1 and y == n - 1:
        return level

Neighbor Expansion

For each of the four possible orthogonal moves, the algorithm verifies that the neighbour lies inside the grid bounds and has not been visited. If both conditions hold, a new entry is pushed onto the heap containing the neighbour’s grid value and its coordinates. This ensures that the heap always contains the next cheapest cells to explore.

    if x > 0     and ( x - 1, y ) not in seen:
        heappush(todo, ( grid[y][x - 1], x - 1, y ))
    if x < n - 1 and ( x + 1, y ) not in seen:
        heappush(todo, ( grid[y][x + 1], x + 1, y ))
    if y > 0     and ( x, y - 1 ) not in seen:
        heappush(todo, ( grid[y - 1][x], x, y - 1 ))
    if y < n - 1 and ( x, y + 1 ) not in seen:
        heappush(todo, ( grid[y + 1][x], x, y + 1 ))

Edge Cases Handled

When the grid consists of a single cell, the initialization pushes the only cell onto the heap, the loop extracts it, the destination check succeeds immediately, and the function returns the value of that cell. The seen set prevents re-processing of cells that may be inserted multiple times due to different paths converging on the same neighbour. The condition if ( x, y ) in seen: continue safely discards stale heap entries without affecting correctness.

The algorithm also correctly handles grids where the water level required to move to a neighbour is lower than the current level; the max(level, l) statement ensures the water level never decreases, reflecting the physical constraint that the water can only rise.

Performance Optimizations

The use of a min-heap (todo) guarantees that the next cell examined always has the smallest possible water level among all frontier cells, which minimizes unnecessary expansions. By updating the level only when a larger cell value is encountered, the algorithm avoids recomputing the maximum over the entire visited set. The seen set provides O(1) membership checks, preventing duplicate work and ensuring each cell is processed at most once. Early termination upon reaching the target eliminates further heap operations once the answer is known, saving work especially in larger grids. The explicit bound checks (x > 0, x < n - 1, etc.) avoid index errors and keep the neighbor generation tight.

Imagine a big grid like a treasure map filled with water of different depths. There is a little swimmer who wants to get from the top left corner to the very bottom right corner. Some squares have deep water and some have shallow water.

To get across, the swimmer always wants to pick the easiest path possible. The swimmer has a backpack called todo that keeps track of all the reachable squares. The swimmer looks at all the squares they can reach right now and always picks the one with the shallowest water first.

As the swimmer moves, they keep track of the deepest water they have had to swim through so far. This is called the level. If the swimmer hits a patch of deep water, the level goes up to make sure they can handle it.

The swimmer also has a special notebook called seen to write down every place they have already visited. This way, they do not swim in circles. The swimmer looks at the squares to their left, right, above, and below. If a square is new and has not been visited, it gets added to the backpack.

This continues over and over. The swimmer picks the next best spot, checks if they have been there, updates the level if the water is deeper than before, and looks for new places to go. Eventually, the swimmer reaches the finish line at the bottom right corner, and the level represents the highest water depth encountered on the chosen path.

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++		Java
	leetcode.ca	C++	Python	Java		Rust	Go		TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	FelixFan1122			Java
	fpdjsns	C++
	gouthampradhan			Java
	halfrost						Go
	haoel		Python
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	ruoru					Rust
	suxrobGM							C#
	trung-hn		Python
	wisdompeak	C++
	withaarzoo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
FelixFan1122	Java
fpdjsns	C++
gouthampradhan	Java
halfrost	Go
haoel	Python
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
wisdompeak	C++
withaarzoo	C++
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