How much water sits above a bar?

min(tallest bar to its left, tallest bar to its right) minus its own height, or 0 if that is negative. The water level is set by the lower of the two walls around it.

Why is it safe to use only left_max on the left side?

When left_max < right_max, some wall on the right is at least right_max, which is taller than left_max. So the lower wall for the left bar is left_max, and its water is known without seeing the rest of the right side.

What is the time and space complexity of Trapping Rain Water with two pointers?

O(n) time, since each step moves one pointer, and O(1) extra space, against O(n) space for the prefix-maximum arrays approach.

Trapping Rain Water

Q: Why is it safe to use only left_max on the left side?

When left_max < right_max, some wall on the right is at least right_max, which is taller than left_max. So the lower wall for the left bar is left_max, and its water is known without seeing the rest of the right side.

Q: What is the time and space complexity of Trapping Rain Water with two pointers?

O(n) time, since each step moves one pointer, and O(1) extra space, against O(n) space for the prefix-maximum arrays approach.

Compute how much water can be trapped after raining.

HardSolve on LeetCode

Examples

Input:height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output:6

Explain:

The elevation map [0,1,0,2,1,0,1,3,2,1,2,1] traps 6 units of rain water.

Problem Understanding

The Goal

You get an elevation map as an array of n non-negative bar heights, one bar per index and each bar one unit wide. Work out the total amount of rain water that stays trapped between the bars.

Imagine looking at the side profile of a structure built with blocks. When it rains, water fills the "valleys" formed between taller "peaks".

Key Insight

For any given bar at index i, the amount of water it can hold above it is determined by:
min(max_height_to_left, max_height_to_right) - height[i]

If this value is negative, it means the bar is taller than the water level, so it holds 0 water.

Algorithm Strategy

The Two Pointer Approach

Instead of pre-computing the max height to the left and right for every index (which takes O(n) space), we can use two pointers to solve this in O(n) time and O(1) space.

Initialize left = 0 and right = n - 1.
Track leftMax and rightMax seen so far.
The Logic: The amount of water trapped at a position is limited by the shorter of the two boundaries.
- If leftMax < rightMax: We know the water level at the left pointer is determined by leftMax (because there's a taller wall somewhere on the right). We move left forward, update leftMax, then add leftMax - height[left]. Updating first means a new tallest bar adds 0 rather than a negative amount.
- If leftMax >= rightMax: We know the water level at the right pointer is determined by rightMax (because there's a taller wall somewhere on the left). We move right backward, update rightMax, then add rightMax - height[right].

Interactive Visualization

Observe how the pointers move inward. The pointer on the side with the smaller max height moves, accumulating water as it goes.

Dry Run

Let’s trace height = [4, 2, 0, 3, 2, 5] with the code below.
Start: left = 0, right = 5, left_max = 4, right_max = 5, water = 0.

Step	left_max < right_max?	Move	Bar height	New left_max	Water added	Total
1	4 < 5, yes	left → 1	2	4	4 - 2 = 2	2
2	4 < 5, yes	left → 2	0	4	4 - 0 = 4	6
3	4 < 5, yes	left → 3	3	4	4 - 3 = 1	7
4	4 < 5, yes	left → 4	2	4	4 - 2 = 2	9
5	4 < 5, yes	left → 5	5	5	5 - 5 = 0	9

left now equals right, so the loop ends and the answer is 9.

Edge Cases & Common Mistakes

Edge Cases

Empty Array or < 3 bars: Cannot trap water => 0.
Ascending or Descending: No valleys => 0.
V-Shape: [5, 0, 5] => Traps water in the middle.

Common Mistakes

Off-by-one errors: Ensure pointers don't cross.
Forgetting to update Max: You must update leftMax or rightMax before or during the water calculation for the current step.

Solution

Optimal solution using Two Pointers.

Trapping Rain Water Code

1var trap = function(height) {
2    if (!height.length) return 0;
3    let left = 0, right = height.length - 1;
4    let leftMax = height[left], rightMax = height[right];
5    let water = 0;
6
7    while (left < right) {
8        if (leftMax < rightMax) {
9            left++;
10            leftMax = Math.max(leftMax, height[left]);
11            water += leftMax - height[left];
12        } else {
13            right--;
14            rightMax = Math.max(rightMax, height[right]);
15            water += rightMax - height[right];
16        }
17    }
18    return water;
19};

Sort Colors