A complete visual walkthrough of the two-pointer approach — watch water fill between bars in real time.
Given 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]; }
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
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; } }
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 regardless of input size.
Three approaches compared: Brute force is O(n^2) time, O(1) space. Prefix arrays are O(n) time, O(n) space. Two pointers achieves the best of both: O(n) time, O(1) space. The two-pointer approach is also simpler to code than the stack-based approach, which has the same complexity but more complex logic.