42. Trapping Rain Water - Explanation

Problem Link

Description

You are given an array of non-negative integers height which represent an elevation map. Each value height[i] represents the height of a bar, which has a width of 1.

Return the maximum area of water that can be trapped between the bars.

Example 1:

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

Output: 9

Constraints:

• 1 <= height.length <= 1000
• 0 <= height[i] <= 1000

1. Brute Force

Intuition

For each position, the water trapped above it depends on the tallest bar to its left and the tallest bar to its right.
If we know these two values, the water at index i is:

min(leftMax, rightMax) - height[i]

The brute-force method recomputes the left maximum and right maximum for every index by scanning the array each time.

Algorithm

1. If the input list is empty, return 0.
2. Let n be the length of the array and initialize res = 0.
3. For each index i:
   • Compute leftMax by scanning from index 0 to i.
   • Compute rightMax by scanning from index i + 1 to the end.
   • Add min(leftMax, rightMax) - height[i] to res.
4. After processing all positions, return res.

  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 0 │ 1 │ 0 │ 2 │ 1 │ 0 │ 1 │ 3 │ 2 │ 1 │ 2 │ 1 │  height
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
    0   1   2   3   4   5   6   7   8   9  10  11

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(1)$

2. Prefix & Suffix Arrays

Intuition

Instead of recomputing the tallest bar to the left and right for every index, we can precompute these values once.
We build two arrays:

• leftMax[i] = tallest bar from the start up to index i
• rightMax[i] = tallest bar from the end up to index i

Once we have these, the trapped water at position i is simply:

min(leftMax[i], rightMax[i]) - height[i]

This removes the repeated work from the brute-force approach and makes the solution more efficient and easier to understand.

Algorithm

1. If the array is empty, return 0.
2. Create two arrays:
   • leftMax of size n
   • rightMax of size n
3. Fill leftMax:
   • leftMax[0] = height[0]
   • For each i from 1 to n - 1,
     leftMax[i] = max(leftMax[i - 1], height[i])
4. Fill rightMax:
   • rightMax[n - 1] = height[n - 1]
   • For each i from n - 2 down to 0,
     rightMax[i] = max(rightMax[i + 1], height[i])
5. Compute trapped water:
   • For each index i, add min(leftMax[i], rightMax[i]) - height[i] to the result.
6. Return the total trapped water.

  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 0 │ 1 │ 0 │ 2 │ 1 │ 0 │ 1 │ 3 │ 2 │ 1 │ 2 │ 1 │  height
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
    0   1   2   3   4   5   6   7   8   9  10  11

  leftMax[i] = max height from index 0 to i

  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 0 │ 1 │ 1 │ 2 │ 2 │ 2 │ 2 │ 3 │ 3 │ 3 │ 3 │ 3 │  leftMax
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
    0   1   2   3   4   5   6   7   8   9  10  11

  rightMax[i] = max height from index i to n-1

  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 3 │ 3 │ 3 │ 3 │ 3 │ 3 │ 3 │ 3 │ 2 │ 2 │ 2 │ 1 │  rightMax
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
    0   1   2   3   4   5   6   7   8   9  10  11

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

3. Stack

Intuition

The stack helps us find places where water can collect.
When we see a bar that is taller than the bar on top of the stack, it means we've found a right wall for a container.
The bar we pop is the bottom, and the new top of the stack becomes the left wall.
With a left wall, bottom, and right wall, we can calculate how much water fits in between.
We keep doing this as long as the current bar keeps forming valid containers.

Algorithm

1. Create an empty stack and set res = 0.
2. Loop through each index i:
   • While the stack is not empty and height[i] is taller than the bar at the stack's top:
     • Pop the top index — that's the bottom.
     • If the stack is not empty:
       • Compute the trapped water between the new top (left wall) and the current bar (right wall).
       • Add it to res.
   • Push the current index onto the stack.
3. Return res after the loop finishes.

  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 0 │ 1 │ 0 │ 2 │ 1 │ 0 │ 1 │ 3 │ 2 │ 1 │ 2 │ 1 │  height
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
    0   1   2   3   4   5   6   7   8   9  10  11

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

4. Two Pointers

Intuition

Water at any position depends on the shorter wall between the left and right sides.
So if the left wall is shorter, the right wall can't help us—water is limited by the left side.
That means we safely move the left pointer inward and calculate how much water can be trapped there.
Similarly, if the right wall is shorter, we move the right pointer left.

As we move the pointers, we keep track of the highest wall seen so far on each side (leftMax and rightMax).
The water at each position is simply:

max wall on that side – height at that position

Algorithm

1. Set two pointers:
   • l at the start
   • r at the end
     Track leftMax and rightMax as the tallest walls seen.
2. While l < r:
   • If leftMax < rightMax:
     • Move l right.
     • Update leftMax.
     • Add leftMax - height[l] to the result.
   • Else:
     • Move r left.
     • Update rightMax.
     • Add rightMax - height[r] to the result.
3. Return the total trapped water.

  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 0 │ 1 │ 0 │ 2 │ 1 │ 0 │ 1 │ 3 │ 2 │ 1 │ 2 │ 1 │  height
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
    0   1   2   3   4   5   6   7   8   9  10  11

   L                                           R
   ↓                                           ↓
  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 0 │ 1 │ 0 │ 2 │ 1 │ 0 │ 1 │ 3 │ 2 │ 1 │ 2 │ 1 │
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
    0   1   2   3   4   5   6   7   8   9  10  11

  leftMax = 0    rightMax = 1    water = 0

           L                                   R
           ↓                                   ↓
  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 0 │ 1 │ 0 │ 2 │ 1 │ 0 │ 1 │ 3 │ 2 │ 1 │ 2 │ 1 │
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
    0   1   2   3   4   5   6   7   8   9  10  11
            ≈

  leftMax = 1    rightMax = 2    water = 1

               L                       R
               ↓                       ↓
  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 0 │ 1 │ 0 │ 2 │ 1 │ 0 │ 1 │ 3 │ 2 │ 1 │ 2 │ 1 │
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
    0   1   2   3   4   5   6   7   8   9  10  11
            ≈                           ≈

  leftMax = 2    rightMax = 2    water = 2

                           L       R
                           ↓       ↓
  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 0 │ 1 │ 0 │ 2 │ 1 │ 0 │ 1 │ 3 │ 2 │ 1 │ 2 │ 1 │
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
    0   1   2   3   4   5   6   7   8   9  10  11
            ≈       ≈   ≈   ≈           ≈

  leftMax = 2    rightMax = 3    water = 6

  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 0 │ 1 │ 0 │ 2 │ 1 │ 0 │ 1 │ 3 │ 2 │ 1 │ 2 │ 1 │  height
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
    0   1   2   3   4   5   6   7   8   9  10  11

  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
  │ 0 │ 0 │ 1 │ 0 │ 1 │ 2 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │  water
  └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
    0   1   2   3   4   5   6   7   8   9  10  11

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

Common Pitfalls

Calculating Water at Boundary Bars

The leftmost and rightmost bars can never hold water above them since there's no wall on one side to contain it. Including them in water calculations gives wrong results.

Using Current Bar Height Instead of Max Heights

Water at each position depends on the minimum of the maximum heights to its left and right, minus the current height. Using the current bar's height in the max comparison instead of tracking running maximums is incorrect.

# Wrong: comparing current height directly
water = min(height[l], height[r]) - height[i]
# Correct: use maximum heights seen so far
water = min(leftMax, rightMax) - height[i]

Negative Water Values

When the current bar is taller than the limiting wall, the water calculation yields a negative value. This happens at peaks and should contribute zero water, not negative.

# Wrong: can add negative water
res += leftMax - height[i]
# Correct: ensure non-negative
res += max(0, min(leftMax, rightMax) - height[i])

Wrong Pointer Movement in Two Pointers

In the two-pointer approach, always move the pointer on the side with the smaller max height. Moving the wrong pointer breaks the invariant that the smaller side determines the water level.