ToolMight LogoToolMight
HardTwo PointersPattern: Two Pointers Max BoundariesPattern: Prefix/Suffix Max

Trapping Rain Water

Given an elevation map where width of each bar is 1, compute how much water it can trap after raining. The classic masterclass in two-pointer bottleneck derivation.

Problem Statement

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Examples & Constraints

Example 1
Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
Explanation: The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water are being trapped.
Example 2
Input: height = [4, 2, 0, 3, 2, 5]
Output: 9
Explanation: Water trapped between bars of heights 4 and 5 totals 9 units.
Constraints
  • n == height.length
  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5

Two Pointers with Running Max Boundaries (O(1) Space)

Optimal Approach
Time:O(n)
Space:O(1)

Converge left and right pointers while tracking maxLeft and maxRight. The trapped water at the lower boundary is min(maxLeft, maxRight) - height[i], computed in O(1) auxiliary space.

Time ComplexityO(n)

Each step moves either the left or right pointer by one bar. The two pointers traverse the array of length N in a single pass.

Space ComplexityO(1)

Operates strictly in-place with four primitive scalar variables (left, right, maxLeft, maxRight). Zero auxiliary arrays allocated.

Underlying algorithmic logic

The Water Level Formula

At any index i, the water held directly above the bar is:
water[i] = max(0, min(max_left, max_right) - height[i])

Where max_left is the tallest bar to the left of i, and max_right is the tallest bar to the right of i.

The Two-Pointer Optimization: Eliminating Arrays

A standard dynamic programming solution computes two auxiliary arrays (leftMax and rightMax) in O(n) space.

However, notice:

  • If maxLeft < maxRight, the water trapped above left is strictly bounded by `maxLeft`! It does not matter how much taller maxRight gets in the future; the bottleneck is already determined by maxLeft.
  • Conversely, if maxRight <= maxLeft, the water trapped above right is strictly bounded by `maxRight`.

Algorithm:

  1. Initialize left = 0, right = n - 1.
  2. Initialize maxLeft = 0, maxRight = 0, and totalWater = 0.
  3. While left < right:
  • If height[left] < height[right]:
  • If height[left] >= maxLeft, update maxLeft = height[left].
  • Else, add maxLeft - height[left] to totalWater.
  • Advance left++.
  • Else:
  • If height[right] >= maxRight, update maxRight = height[right].
  • Else, add maxRight - height[right] to totalWater.
  • Decrement right--.
  1. Return totalWater.

Step-by-step execution walkthrough

1
Initial Pointers

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. left = 0 (val 0), right = 11 (val 1). maxLeft = 0, maxRight = 0.

left = 0, right = 11, total = 0
2
Left Advances (Indices 0..2)

i=0: maxLeft=0. i=1: maxLeft=1. i=2 (height 0): height[2] < maxLeft (1) -> trapped = 1 - 0 = 1.

water trapped at index 2 = 1. total = 1
3
Valleys Between Heights

Water accumulates over indices 4, 5, 6 as left advances towards the peak at index 7 (height 3).

water at 4 (1), 5 (2), 6 (1). total = 5
4
Right Pointers Converge

Pointers meet at index 7 (highest bar). Total accumulated water is exactly 6 units.

Final total water = 6
Advantages
  • •Optimal O(n) single pass runtime
  • •O(1) auxiliary space without requiring extra prefix/suffix arrays
Trade-offs
  • •The logic condition (advancing based on height[left] < height[right]) requires careful proof

Code Implementations

Copy & paste production-ready solutions for Two Pointers with Running Max Boundaries (O(1) Space) in your language of choice

File: solution.py
Python
def trap(height: list[int]) -> int:
    if not height:
        return 0
    left, right = 0, len(height) - 1
    max_left, max_right = 0, 0
    total_water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= max_left:
                max_left = height[left]
            else:
                total_water += max_left - height[left]
            left += 1
        else:
            if height[right] >= max_right:
                max_right = height[right]
            else:
                total_water += max_right - height[right]
            right -= 1
    return total_water
if __name__ == "__main__":
    test1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    test2 = [4, 2, 0, 3, 2, 5]
    print("test1 trapped water:", trap(test1))
    print("test2 trapped water:", trap(test2))
Interactive visualizer available

Understand Array & Matrix Visually

Explore sequential element access, subsegment manipulations, insertion, deletion, and 2D grid matrix walks. Test live edge cases and watch memory state transitions step-by-step.

Launch Array & Matrix Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
MediumTwo Pointers
Visualizer

Container With Most Water

Find two vertical lines that together with the x-axis form a container holding the maximum amount of water. The premier problem for learning two-pointer greedy bottleneck elimination.

1 approach(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
EasyTwo Pointers
Visualizer

Valid Palindrome

Determine if a string is a palindrome considering only alphanumeric characters and ignoring case. The canonical problem for learning the two-pointer inward convergence technique.

1 approach(O(n))
Learn logic