March 24
Trapping Rain Water
How to notice that water at each position depends on both side maximums and compress that into two pointers.
Arrays and Two Pointers Advanced 28 min TypeScript
Given an array height, where each value represents the height of a bar, return how much water is trapped after raining.
Example:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
What to notice before coding
- The water at one position depends on the smaller of the best wall on the left and the best wall on the right.
- There is no negative water. If the bar is already too tall, that position contributes zero.
- The hard part is not the formula. It is knowing when one side is already decided.
Common mistakes
- adding `min(leftMax, rightMax) - height[i]` without clamping it at zero
- moving pointers without justifying which side can already be resolved
Step 1 - Understand the local formula
At position i, the trapped water is:
min(maxLeft, maxRight) - height[i]
Because the water level can only rise up to the smaller of the two walls that contain it.
Step 2 - Write the most direct baseline
The natural baseline is:
- for each index
- find the highest value to the left
- find the highest value to the right
- calculate that position's contribution
It works.
But it repeats too much searching.
Step 3 - Ask what really decides one side
If you keep:
leftMaxas the highest wall seen from the leftrightMaxas the highest wall seen from the right
then when leftMax <= rightMax, the left side is already decided.
The reason is that, for the current left position, there will always be some wall on the right at least as high as leftMax.
Step 4 - Turn that into two pointers
With two pointers:
- if
leftMax <= rightMax, resolve the left side and advanceleft - otherwise, resolve the right side and move
rightback
That way, each index is processed once.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function trap(height: number[]): number {
// your solution here
return 0
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(1)
Solution 1 - Scan left and right for every index O(n²)
Good baseline because it makes the local formula concrete.
export function trap(height: number[]): number {
let water = 0
for (let index = 0; index < height.length; index += 1) {
let leftMax = 0
let rightMax = 0
for (let left = 0; left <= index; left += 1) {
leftMax = Math.max(leftMax, height[left])
}
for (let right = index; right < height.length; right += 1) {
rightMax = Math.max(rightMax, height[right])
}
water += Math.max(0, Math.min(leftMax, rightMax) - height[index])
}
return water
}It works, but it recalculates the same maximums many times.
Solution 2 - Two pointers with accumulated maximums in O(n)
Now you resolve each side when it is already decided.
export function trap(height: number[]): number {
let left = 0
let right = height.length - 1
let leftMax = 0
let rightMax = 0
let water = 0
while (left < right) {
leftMax = Math.max(leftMax, height[left])
rightMax = Math.max(rightMax, height[right])
if (leftMax <= rightMax) {
water += leftMax - height[left]
left += 1
} else {
water += rightMax - height[right]
right -= 1
}
}
return water
}The strong insight is knowing when one position can be finalized without knowing the rest in more detail.
What to say in the interview
A strong short explanation would be:
The local formula is
min(leftMax, rightMax) - height[i]. The baseline recalculates those maximums for every index. In the stronger version I maintainleftMaxandrightMaxwith two pointers. WhenleftMax <= rightMax, the left side is already limited and can be resolved immediately. The same logic works symmetrically on the right.
That shows that you:
- understand the local water formula
- can justify pointer movement
- explain why one side’s answer is already decided
When this pattern shows up again
This pattern comes back when you need to:
- maintain accumulated maximums from both sides
- decide locally when one side is already resolved
- use
two pointerswith stronger invariants - compare alternatives like prefix arrays, stack, and two pointers
The point is not memorizing
Trapping Rain Water.
The point is learning when partial information is already enough to close one side.