A complete visual walkthrough of the two-pointer approach — watch water fill between bars in real time.
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 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5] Output: 9
Constraints:
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105Given an elevation map as an array of non-negative integers, compute how much rainwater is trapped between the bars after raining.
The gray bars are the elevation. The blue areas are trapped water. Total water = 6 units.
For each bar at index i, the water it can hold equals:
Where maxLeft is the tallest bar to the left of i (inclusive) and maxRight is the tallest to the right (inclusive). Water level at i is limited by the shorter of the two walls.
For each bar, scan left and right to find the maximums. This requires two nested loops.
for (int i = 0; i < n; i++) { int maxLeft = 0, maxRight = 0; for (int j = 0; j <= i; j++) maxLeft = Math.max(maxLeft, height[j]); for (int j = i; j < n; j++) maxRight = Math.max(maxRight, height[j]); water += Math.min(maxLeft, maxRight) - height[i]; }
for i := 0; i < n; i++ { maxLeft, maxRight := 0, 0 for j := 0; j <= i; j++ { if height[j] > maxLeft { maxLeft = height[j] } } for j := i; j < n; j++ { if height[j] > maxRight { maxRight = height[j] } } if maxLeft < maxRight { water += maxLeft - height[i] } else { water += maxRight - height[i] } }
for i in range(n): max_left = max(height[:i + 1]) max_right = max(height[i:]) water += min(max_left, max_right) - height[i]
for i in 0..n { let max_left = height[..=i].iter().copied().max().unwrap_or(0); let max_right = height[i..].iter().copied().max().unwrap_or(0); water += max_left.min(max_right) - height[i]; }
for (let i = 0; i < n; i++) { let maxLeft = 0, maxRight = 0; for (let j = 0; j <= i; j++) maxLeft = Math.max(maxLeft, height[j]); for (let j = i; j < n; j++) maxRight = Math.max(maxRight, height[j]); water += Math.min(maxLeft, maxRight) - height[i]; }
This works but is O(n^2). We can do much better.
The key question: can we avoid re-scanning for maxLeft and maxRight at every position? Yes — by tracking running maximums from each end.
Place a pointer at each end of the array. Track the running maximum from the left (leftMax) and from the right (rightMax). At each step, process the side with the smaller maximum.
If leftMax < rightMax, then we know the water at the left pointer is bounded by leftMax — regardless of what lies between the pointers. There might be even taller bars to the right, but leftMax is the bottleneck. So we can safely compute water at left and advance it.
One pass, no extra arrays. Unlike the prefix-max approach (which precomputes leftMax[] and rightMax[] arrays in O(n) space), the two-pointer approach computes everything on the fly in O(1) space.
Let's trace through height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] with the two-pointer approach.
Total water = 6
With 0, 1, or 2 bars there is no bar on both sides to trap water. Both prefix-max and suffix-max arrays still compute correctly, and every cell contributes min(left, right) - height = 0, so the answer is naturally 0.
For example, [1,2,3,4,5] or [5,4,3,2,1]. Every bar is either the tallest on its left or the tallest on its right, so min(left[i], right[i]) == height[i] for every position and no water is trapped.
For example, [3,3,3,3]. The prefix-max and suffix-max both equal 3 everywhere, so min(3,3) - 3 = 0 at every index. No water is trapped.
For example, [0,0,5,0,0]. The tall center bar acts as neither a left wall nor a right wall for itself. Water can only be trapped between two walls; isolated tall bars produce no contribution.
For example, [3,0,3]. The left-max is [3,3,3] and right-max is [3,3,3]. The middle cell contributes min(3,3) - 0 = 3 units of water, which is the maximum possible for this input.
class Solution { public int trap(int[] height) { int left = 0, right = height.length - 1; int leftMax = 0, rightMax = 0, water = 0; while (left < right) { if (height[left] < height[right]) { // Left side is the bottleneck leftMax = Math.max(leftMax, height[left]); water += leftMax - height[left]; // water at left left++; } else { // Right side is the bottleneck rightMax = Math.max(rightMax, height[right]); water += rightMax - height[right]; // water at right right--; } } return water; } }
func trap(height []int) int { left, right := 0, len(height)-1 leftMax, rightMax, water := 0, 0, 0 for left < right { if height[left] < height[right] { // Left side is the bottleneck if height[left] > leftMax { leftMax = height[left] } water += leftMax - height[left] // water at left left++ } else { // Right side is the bottleneck if height[right] > rightMax { rightMax = height[right] } water += rightMax - height[right] // water at right right-- } } return water }
def trap(height: list[int]) -> int: left, right = 0, len(height) - 1 left_max = right_max = water = 0 while left < right: if height[left] < height[right]: # Left side is the bottleneck left_max = max(left_max, height[left]) water += left_max - height[left] # water at left left += 1 else: # Right side is the bottleneck right_max = max(right_max, height[right]) water += right_max - height[right] # water at right right -= 1 return water
impl Solution { pub fn trap(height: Vec<i32>) -> i32 { let (mut left, mut right) = (0, height.len() - 1); let (mut left_max, mut right_max, mut water) = (0, 0, 0); while left < right { if height[left] < height[right] { // Left side is the bottleneck left_max = left_max.max(height[left]); water += left_max - height[left]; // water at left left += 1; } else { // Right side is the bottleneck right_max = right_max.max(height[right]); water += right_max - height[right]; // water at right right -= 1; } } water } }
function trap(height: number[]): number { let left = 0, right = height.length - 1; let leftMax = 0, rightMax = 0, water = 0; while (left < right) { if (height[left] < height[right]) { // Left side is the bottleneck leftMax = Math.max(leftMax, height[left]); water += leftMax - height[left]; // water at left left++; } else { // Right side is the bottleneck rightMax = Math.max(rightMax, height[right]); water += rightMax - height[right]; // water at right right--; } } return water; }
Enter heights and watch the two pointers converge. The bar chart updates in real time with water filling between bars.
Each pointer moves at most n times total, and each step does O(1) work -- a comparison, a max update, and an addition. We use only four variables (left, right, leftMax, rightMax) regardless of input size.
For each bar, two inner loops scan left and right to find maxLeft and maxRight. Each scan is O(n), repeated for all n bars, giving O(n2) total. Only a few variables are needed, so space is O(1).
Two O(n) passes precompute leftMax[] and rightMax[] arrays. A third pass computes water at each bar in O(1) using the precomputed values. Three passes total is still O(n), but the two auxiliary arrays cost O(n) space.
Left and right pointers converge in one pass. At each step, the smaller side's running max determines the water level, computed on the fly. Only four scalar variables are used -- no arrays -- achieving O(n) time with O(1) space.
Two pointers eliminate the prefix arrays. The shorter wall determines the water level, so we always process from the shorter side. This lets us compute leftMax and rightMax on the fly instead of precomputing them in O(n) arrays -- achieving the best of both: O(n) time, O(1) space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.