Abstract / Summary

Given a heightmap, calculate how much rainwater can be trapped after raining.

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 64% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Heap (Priority Queue)
• 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 trapRainWater method computes the total volume of water that can be retained after raining on a rectangular elevation map. It treats the map as a grid of cells, each with a height, and determines how much water can be trapped above interior cells by progressively raising the surrounding “walls”. The algorithm relies on a priority queue (min-heap) to always expand from the lowest boundary, guaranteeing that water flows outward from the lowest points first.

Initialization

At the start, the accumulator result is set to zero. The dimensions of the grid are stored in height and width. Two containers are prepared: walls, a min-heap that will hold the current boundary cells ordered by height, and inside, a set that tracks interior cells that have not yet been processed.

result = 0
height = len(heightMap)
width  = len(heightMap[0])
walls  = []    # min-heap
inside = set() # cells where water might be trapped

Boundary Identification

A double loop iterates over every coordinate. Cells that lie strictly inside the rectangle (i.e., not on the outermost rows or columns) are added to inside. All cells on the perimeter are pushed onto walls together with their height, establishing the initial boundary of the region.

for y in range(height):
    for x in range(width):
        if 0 < x < width - 1 and 0 < y < height - 1:
            inside.add((x, y))
        else:
            heappush(walls, (heightMap[y][x], x, y))

Neighbor Traversal Representation

The array delta = [0, +1, 0, -1, 0] encodes the four cardinal directions in a compact form. By pairing successive elements, the algorithm obtains (dx, dy) offsets for right, down, left, and up moves without constructing separate tuples for each direction. This reduces allocation overhead inside the main loop.

Main Processing Loop

The core of the algorithm repeatedly extracts the lowest wall from the heap. For each extracted cell, its four orthogonal neighbors are examined. If a neighbor is still marked as interior, the potential water depth is the difference between the current wall height and the neighbor’s ground height. Positive differences are added to result. The neighbor is then promoted to a wall with a height equal to the higher of the current wall and its own ground level, and it is removed from inside. This process continues until the heap is exhausted, meaning all interior cells have been evaluated.

delta = [0, +1, 0, -1, 0]
while walls:
    height, x, y = heappop(walls)
    for dx, dy in zip(delta, delta[1:]):
        nx = x + dx
        ny = y + dy
        if (nx, ny) not in inside:
            continue
        trapped = height - heightMap[ny][nx]
        if trapped > 0:
            result += trapped
        heappush(walls, (max(height, heightMap[ny][nx]), nx, ny))
        inside.discard((nx, ny))
return result

Edge Cases Handled

The algorithm gracefully handles maps where the interior region is empty, such as a single row or a single column, because the inner-cell condition 0 < x < width - 1 and 0 < y < height - 1 will never be satisfied, leaving inside empty and causing the while-loop to terminate immediately with a result of zero. When neighboring cells have equal or higher elevation than the current wall, the computed trapped value becomes non-positive, and the conditional guard prevents any addition to the accumulator. The use of inside.discard ensures that attempts to remove a cell that may already have been processed do not raise an exception, preserving correctness even if duplicate neighbor checks occur.

Performance Optimizations

The priority queue guarantees that the next cell to be examined is always the lowest boundary, which minimizes unnecessary water-level updates and avoids revisiting cells with higher surrounding walls. Membership checks against inside are O(1) due to the hash-set implementation, allowing rapid determination of whether a neighbor still requires processing. The compact delta array eliminates the need to allocate a list of direction tuples on each iteration, reducing memory churn. Updating a neighbor’s wall height with max(height, heightMap[ny][nx]) directly captures the effective barrier without extra conditional branches. Finally, inside.discard is used instead of remove to avoid the cost of exception handling when a cell is already absent from the set.

Imagine a big box filled with lots of little square pillars of different heights. Some are tall and some are short. If you pour water into this box, the water will stay trapped in the low parts as long as the surrounding pillars are tall enough to hold it in.

The code starts by looking at the very edge of the box. Any water poured near the edge would just spill right out. It keeps track of these edge pillars because they act like the walls of a container. It also makes a big list of all the empty spaces inside where water might get stuck.

To figure out how much water stays, it always looks for the shortest wall first. That is where the water is most likely to spill over. It checks the neighbors of that wall to see if they are shorter. If a neighbor is shorter than the wall, that hole fills up with water until it reaches the same height as the wall.

Once a smaller space is checked and filled, that spot essentially becomes a new part of the wall. By always starting from the outside and working inward toward the middle, it keeps track of every drop of water that cannot escape. It repeats this process until every single spot in the box has been checked and the total amount of trapped water is calculated.

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

Time: loglinear
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++		Java							Python	TS
	WalkCCC	C++		Java							Python
	leetcode.ca	C++		Java						Go	Python	TS
	LeetcodeHelp	C++		Java							Python
	Progiez	C++		Java							Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fartem					Ruby
	JoshCrozier		JS
	linouk23	C++
	MacJim	C++
	ruoru				Rust
	Shamik07						Dart
	suxrobGM							C#
	varunu28			Java
	vli02								C
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
JoshCrozier	JavaScript
linouk23	C++
MacJim	C++
ruoru	Rust
Shamik07	Dart
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
withaarzoo	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