Trapping Rain Water

1. Initialize Two Pointers and Tracking Variables

• Set left = 0 (start of array) and right = height.length - 1 (end of array)
• Set leftMax = 0 to track the tallest bar seen from the left
• Set rightMax = 0 to track the tallest bar seen from the right
• Set water = 0 to accumulate the total trapped water

2. Compare Heights at Both Pointers

• At each step, compare height[left] with height[right]
• Process the side with the smaller height, because the water level at that position is determined by its own side's maximum (the other side is guaranteed to be at least as tall)

3. Process the Left Pointer

• If height[left] < height[right], process the left side
• If height[left] >= leftMax, update leftMax — this bar is a new boundary, no water is trapped here
• Otherwise, leftMax - height[left] units of water are trapped above this bar — add that to water
• Move left++

4. Process the Right Pointer

• If height[right] <= height[left], process the right side
• If height[right] >= rightMax, update rightMax — this bar is a new boundary, no water is trapped here
• Otherwise, rightMax - height[right] units of water are trapped above this bar — add that to water
• Move right--

5. Repeat Until Pointers Meet

• Continue the loop while left < right
• Each iteration processes exactly one position, giving O(n) time complexity
• Only a constant number of variables are used, giving O(1) space complexity

6. Return the Result

• After the loop, water contains the total amount of trapped rain water
• Return water

Key Insight

The water trapped at any position depends on the minimum of the tallest bar to its left and the tallest bar to its right, minus its own height. By processing from both ends inward and always choosing the smaller side, we can guarantee that the max on the opposite side is at least as large — so we only need to track the max on the side we are processing. This eliminates the need for precomputed arrays and achieves O(1) space.