Abstract / Summary

Given a list of heights, find the total amount of water that can be trapped between the bars after it rains.

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% (5+ million submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Monotonic Stack
• Stack
• Two Pointers

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 Solution.trap method computes the total volume of water that can be trapped after raining on a histogram represented by an integer list height. It follows a two-phase strategy: first it identifies the highest bar (the pivot), then it sweeps from both ends toward that pivot, accumulating water based on the highest boundary seen so far on each side. The algorithm works entirely with integer variables and simple loops, avoiding auxiliary data structures.

Key Steps

Finding the Pivot (Maximum Height Index)

pivot = 0
for h in range(len(height)):
    if height[h] > height[pivot]:
        pivot = h

A single forward pass scans the entire height array. The variable pivot holds the index of the tallest bar encountered. By updating pivot only when a strictly higher bar is found, the algorithm selects the leftmost occurrence of the maximum height, which serves as a natural dividing point for the subsequent scans.

Accumulating Water on the Left Side

water = 0
border = 0
for h in range(pivot):
    if border > height[h]:
        water += border - height[h]
    else:
        border = height[h]

Starting from the leftmost bar and moving up to (but not including) the pivot, the loop maintains border as the highest bar seen so far. When the current bar is lower than border, the difference represents trapped water at that position and is added to water. If the current bar exceeds border, border is updated, establishing a new left boundary for future positions.

Accumulating Water on the Right Side

border = 0
for h in range(len(height) - 1, pivot, -1):
    if border > height[h]:
        water += border - height[h]
    else:
        border = height[h]

A symmetric pass runs from the rightmost index down to the element just after the pivot. The same border logic applies, now tracking the highest bar encountered from the right. Water is added whenever the current bar lies below this right-hand boundary, and border is refreshed whenever a taller bar appears.

Returning the Result

return water

After both directional sweeps, the accumulated water variable holds the total trapped volume, which the method returns as an integer.

Edge Cases Handled

When height is empty, the initial pivot remains 0. Both the left-to-pivot and right-to-pivot loops iterate over empty ranges, leaving water at 0, which is the correct result.

If the list contains a single element, the same reasoning applies: no positions exist on either side of the pivot, so no water can be trapped and the method returns 0.

For monotonic sequences (strictly increasing or decreasing), the left or right scan will never encounter a bar lower than the current border, resulting in zero water accumulation.

When multiple bars share the maximum height, the algorithm selects the first such index as the pivot. The left scan stops before this bar, while the right scan processes all bars after it. Because the highest boundary on each side is never exceeded, the computed water volume remains accurate.

Performance Optimizations

The implementation achieves constant auxiliary space by reusing a few integer variables (pivot, border, water) throughout the computation. It avoids allocating additional arrays or stacks, which reduces memory pressure for large inputs.

The two directional sweeps each traverse only a portion of the array: the left scan stops at the pivot, and the right scan stops at the same pivot from the opposite end. This partitioning prevents redundant processing of the region already covered by the first scan, effectively halving the work compared to a naïve double-pass over the entire array.

All arithmetic operations are simple integer subtractions and additions, and the conditional checks are straightforward comparisons, ensuring minimal overhead inside the tight loops. The algorithm therefore scales efficiently with the size of the input while maintaining a clear and deterministic control flow.

Imagine a row of tall blocks of different heights standing side by side. Some are tall and some are short, creating little valleys between them. Rain starts to fall and fills up those valleys, creating puddles.

The first part of the code goes along the line to find the tallest block of all. This is the highest point that acts like a mountain peak.

The next part looks at everything to the left of that tall peak. It walks along and keeps track of the tallest wall seen so far. If a shorter empty spot is found next to a wall, the code fills that spot with rain until it reaches the same height as the wall.

Then the final part does the exact same thing but walks from the other side. It starts at the very end and moves toward the middle peak, filling up every little valley it finds with rain. By the time it finishes, every valley is filled, and all the water is accounted for.

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

Time: linear
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	C#	Rust				Go	PHP	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	begeekmyfriend							C
	BigEggStudy				C#
	black-shadows	C++
	bujosa					Rust
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	everthis						JS
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	fsq	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost									Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	qiyuangong		Python
	ruoru					Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vli02							C
	vthwang			Java
	wisdompeak	C++
	yuanliu666								Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
fsq	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	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