LeetCode 42 - Trapping Rain Water

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack

Solution

Problem Understanding

The problem gives an array called height, where each element represents the height of a vertical bar in an elevation map. Every bar has width 1. After rainfall, water may become trapped between taller bars.

The task is to compute the total amount of water that can be trapped.

For example, consider the array:

[0,1,0,2,1,0,1,3,2,1,2,1]

The bars form valleys between taller walls. Water fills these valleys, and the total trapped water is 6.

The key observation is that the amount of water above a specific index depends on the tallest bar to its left and the tallest bar to its right.

At any position i:

water[i] = min(max_left, max_right) - height[i]

If either side does not have a taller boundary, then no water can be trapped there.

The constraints are important:

1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

An O(n^2) solution may still pass for smaller inputs, but it is inefficient and unnecessary. The problem strongly suggests looking for an O(n) solution.

Several edge cases are important:

Arrays with fewer than 3 bars cannot trap water.
Strictly increasing or strictly decreasing heights trap no water.
Multiple valleys may exist.
Very tall bars at the ends can trap large amounts of water inside.
Flat regions and repeated heights can cause incorrect calculations if boundary logic is wrong.

Approaches

Brute Force Approach

The brute force solution evaluates every position independently.

For each index:

Scan left to find the tallest bar on the left.
Scan right to find the tallest bar on the right.
The trapped water is the smaller of those two heights minus the current bar height.

This works because water level at any position is limited by the shorter boundary.

Although correct, this method is inefficient because each index performs two additional scans. With n elements, every position may require O(n) work, producing total complexity O(n^2).

With n = 20,000, this becomes unnecessarily slow.

Optimal Two Pointer Approach

The optimal solution uses two pointers and processes the array in a single pass.

The core insight is:

Water trapped at a position depends on the smaller boundary.
If the left boundary is smaller than the right boundary, then the left side determines the water level.
Similarly, if the right boundary is smaller, then the right side determines the water level.

This means we do not need to know the exact maximum on both sides at every step. We only need to track:

left_max
right_max

Using two pointers allows us to compute trapped water in O(n) time and O(1) extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recomputes left and right maximums for every index
Optimal	O(n)	O(1)	Uses two pointers and running maximums

Algorithm Walkthrough

Optimal Two Pointer Algorithm

Initialize two pointers:

left = 0
right = len(height) - 1

These pointers represent the current boundaries being processed. 2. Initialize two variables:

left_max = 0
right_max = 0

These store the tallest bars seen so far from each side. 3. Initialize trapped_water = 0. 4. While left < right, compare height[left] and height[right]. 5. If height[left] < height[right], process the left side:

If height[left] >= left_max, update left_max.
Otherwise, water can be trapped:

left_max - height[left]

Move left one step right.

Otherwise, process the right side:

If height[right] >= right_max, update right_max.
Otherwise, water can be trapped:

right_max - height[right]

Move right one step left.

Continue until the pointers meet.
Return trapped_water.

Why it works

The correctness depends on this invariant:

Water level at any position is determined by the smaller of the tallest boundaries on both sides.

When height[left] < height[right], we know the left side is the limiting boundary. Even if a taller wall exists further right, the current right boundary is already tall enough to guarantee that left_max determines the water level.

The same logic applies symmetrically for the right side.

Because every index is processed exactly once, the algorithm is both correct and efficient.

Python Solution

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3:
            return 0

        left = 0
        right = len(height) - 1

        left_max = 0
        right_max = 0

        trapped_water = 0

        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    trapped_water += left_max - height[left]

                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    trapped_water += right_max - height[right]

                right -= 1

        return trapped_water

The implementation begins by handling a small edge case. Arrays with fewer than three bars cannot trap water because at least two boundaries and one middle position are required.

Two pointers are initialized at opposite ends of the array. These pointers move inward as the algorithm processes bars.

left_max and right_max track the tallest bars encountered from each side.

At each iteration, the algorithm processes the side with the smaller height because that side determines the maximum possible water level.

If the current height exceeds the running maximum, the maximum is updated. Otherwise, trapped water is calculated using the difference between the running maximum and current height.

The algorithm continues until the pointers meet, ensuring every index is processed exactly once.

Go Solution

func trap(height []int) int {
    if len(height) < 3 {
        return 0
    }

    left := 0
    right := len(height) - 1

    leftMax := 0
    rightMax := 0

    trappedWater := 0

    for left < right {
        if height[left] < height[right] {
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                trappedWater += leftMax - height[left]
            }

            left++
        } else {
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                trappedWater += rightMax - height[right]
            }

            right--
        }
    }

    return trappedWater
}

The Go implementation follows the same logic as the Python solution.

Go slices are dynamically sized views into arrays, so no special handling is needed beyond checking length.

All arithmetic uses int, which is sufficient because the maximum trapped water value fits comfortably within Go's integer range under the given constraints.

Unlike Python, Go requires explicit variable declarations and increment syntax.

Worked Examples

Example 1

Input:

height = [0,1,0,2,1,0,1,3,2,1,2,1]

Step-by-step Trace

Step	left	right	left_max	right_max	Water Added	Total
Start	0	11	0	0	0	0
Process left	0	11	0	0	0	0
Process right	1	11	0	1	0	0
Process left	1	10	1	1	0	0
Process left	2	10	1	1	1	1
Process right	3	10	1	2	0	1
Process right	3	9	1	2	1	2
Process right	3	8	1	2	0	2
Process left	3	7	2	2	0	2
Process left	4	7	2	2	1	3
Process left	5	7	2	2	2	5
Process left	6	7	2	2	1	6

Final answer:

Example 2

Input:

height = [4,2,0,3,2,5]

Step-by-step Trace

Step	left	right	left_max	Water Added	Total
Start	0	5	0	0	0
Process left	0	5	4	0	0
Process left	1	5	4	2	2
Process left	2	5	4	4	6
Process left	3	5	4	1	7
Process left	4	5	4	2	9

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer moves across the array at most once
Space	O(1)	Only a few variables are used

The algorithm performs a single linear scan of the array. Neither pointer ever moves backward, so total work is proportional to n.

No auxiliary arrays, stacks, or maps are used, making the extra space constant.

Test Cases

solution = Solution()

assert solution.trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6  # provided example
assert solution.trap([4,2,0,3,2,5]) == 9  # provided example

assert solution.trap([]) == 0  # empty array
assert solution.trap([1]) == 0  # single bar
assert solution.trap([1,2]) == 0  # two bars cannot trap water

assert solution.trap([1,2,3,4,5]) == 0  # strictly increasing
assert solution.trap([5,4,3,2,1]) == 0  # strictly decreasing

assert solution.trap([3,0,3]) == 3  # simple valley
assert solution.trap([2,0,2]) == 2  # symmetric trapping
assert solution.trap([5,0,5]) == 5  # deep valley

assert solution.trap([4,2,3]) == 1  # uneven boundaries
assert solution.trap([0,0,0]) == 0  # all zeros
assert solution.trap([3,3,3]) == 0  # flat plateau

assert solution.trap([5,1,2,1,5]) == 11  # multiple trapped sections
assert solution.trap([2,1,0,1,2]) == 4  # symmetric bowl

assert solution.trap([100000,0,100000]) == 100000  # large values

Test	Why
`[0,1,0,2,1,0,1,3,2,1,2,1]`	Validates standard multi-valley case
`[4,2,0,3,2,5]`	Tests uneven boundaries
`[]`	Ensures empty input is handled
`[1]`	Single element edge case
`[1,2]`	Two-element edge case
`[1,2,3,4,5]`	Increasing heights trap no water
`[5,4,3,2,1]`	Decreasing heights trap no water
`[3,0,3]`	Simplest non-trivial trapping case
`[2,0,2]`	Symmetric bowl
`[5,0,5]`	Large single valley
`[4,2,3]`	Right boundary smaller than left
`[0,0,0]`	All zero heights
`[3,3,3]`	Flat plateau
`[5,1,2,1,5]`	Multiple trapped regions
`[2,1,0,1,2]`	Symmetric nested valley
`[100000,0,100000]`	Large constraint values

Edge Cases

Arrays Smaller Than Three Elements

An array with fewer than three bars cannot trap water because there are not enough boundaries to create a container.

Examples:

[]
[1]
[1,2]

A common bug is attempting to process these arrays normally, which may lead to unnecessary logic or index errors. The implementation handles this immediately with:

if len(height) < 3:
    return 0

Strictly Increasing or Decreasing Heights

Arrays like:

[1,2,3,4,5]

[5,4,3,2,1]

cannot trap water because there is never a valley enclosed by taller bars.

Naive implementations sometimes incorrectly assume every lower bar traps water. The two pointer algorithm avoids this by only adding water when a valid boundary maximum already exists.

Flat Regions and Equal Heights

Arrays such as:

[3,3,3]
[0,0,0]

contain no valleys.

Equal heights can cause pointer movement mistakes if comparison logic is incorrect. The implementation safely processes equal heights using the else branch, ensuring pointers always move and no infinite loops occur.

Deep Valleys With Large Values

Cases like:

[100000,0,100000]

test whether the implementation correctly handles large trapped volumes.

The algorithm computes:

100000 - 0 = 100000

without overflow issues in either Python or Go under the given constraints.