This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#42) before relying on it.
Home → Algorithms → Trapping Rain Water

Trapping Rain Water

An interactive visualization of how the two-pointer technique calculates water trapped between elevation bars. Watch left and right pointers converge while tracking maximum heights.

Two Pointers LeetCode 42 ↗ Hard

The Problem

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.

Example: For height = [0,1,0,2,1,0,1,3,2,1,2,1], the answer is 6 units of water trapped.

The key insight is that the water above any bar depends on the minimum of the tallest bar to its left and the tallest bar to its right, minus its own height.

Interactive Visualization

Speed:
Water Trapped: 0
Left Pointer
0
Right Pointer
11
left_max
0
right_max
0
Water at Pos
-
Elevation Map & Water Fill
Code
fun trap(height: IntArray): Int {    var left = 0; var right = height.size - 1    var leftMax = 0; var rightMax = 0    var water = 0    while (left < right) {        if (height[left] < height[right]) {            if (height[left] >= leftMax)                leftMax = height[left]            else                water += leftMax - height[left]            left++        } else {            if (height[right] >= rightMax)                rightMax = height[right]            else                water += rightMax - height[right]            right--    } }    return water}
Status & Log
Press Step or Play to begin.

How It Works

Key Insight

The water above any position i is determined by the minimum of the maximum heights to its left and right, minus its own height: water[i] = min(left_max, right_max) - height[i]. The two-pointer approach exploits the fact that we only need to know the smaller of the two maxima at any time, which is always on the side of the shorter pointer.

Algorithm Steps

  • Initialize: Place left at index 0 and right at the last index. Set left_max = 0 and right_max = 0.
  • Compare heights: If height[left] < height[right], the left side is the bottleneck — process the left pointer.
  • Process left: If height[left] >= left_max, update left_max. Otherwise, water at this position is left_max - height[left]. Then advance left.
  • Process right: Same logic symmetrically. If height[right] >= right_max, update right_max. Otherwise, add right_max - height[right]. Then decrease right.
  • Terminate: When left >= right, all positions have been processed.

Complexity

Time O(n)
Space O(1)

Each pointer moves at most n steps total, so the algorithm processes the entire array in a single pass with constant extra space. This is optimal — we must examine each element at least once.