Trapping Rain Water

Trapping Rain Water is a famous hard array question. It scares people. But once you see what traps the water at one spot, it becomes simple. The interviewer wants to see if you can find the rule for one bar and then make it fast with two pointers.

🎯 The Problem

You get an array of bar heights. Picture a wall of bars on the ground. When it rains, water pools in the dips. Find the total water trapped. The rules:

• The water above one bar is decided by the tallest wall on its left and the tallest wall on its right.
• Water can only rise as high as the shorter of those two walls.
• So water above a bar is min(leftMax, rightMax) minus that bar’s own height.
• If that value is negative, no water sits there.
• Add the water above every bar for the total.

For the heights [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the total trapped water is 6.

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

Explanation: water pools in the dips between the taller bars.
             Adding the water above every bar gives 6 units.

Here is the idea for one bar. The water above it depends on the tallest wall on each side.

🐢 Approach 1: Scan Both Sides Per Bar (Brute Force)

Follow the rule directly for each bar.

The idea:

• For each bar, look left to find the tallest wall.
• Then look right to find the tallest wall.
• Water above this bar is the shorter wall minus the bar height.

Why it is weak:

• For every bar you scan all the way left and all the way right.
• That is two inner scans inside the main loop.
• Time is O(n²). Correct but slow.

Here is the brute-force code for that idea:

def trap(height):
    water = 0
    for i in range(len(height)):
        left_max = max(height[:i + 1])
        right_max = max(height[i:])
        water += min(left_max, right_max) - height[i]
    return water

⚡ Approach 2: Prefix Max Arrays (Better)

The idea in one line: precompute the left max and right max for every bar so you never rescan.

The idea:

• Build two helper arrays first.
• One holds the tallest wall to the left of each bar.
• The other holds the tallest wall to the right of each bar.

How it works:

• Fill the left max array in one pass from the start.
• Fill the right max array in one pass from the end.
• Loop once more. Water for a bar is min(leftMax, rightMax) minus its height.

Why it is fast:

• Each pass is O(n). Total time is O(n).

Why it is weak:

• It needs two extra arrays. So it costs O(n) memory.
• The best version removes that extra memory.

Here is the prefix/suffix array code for that idea:

def trap(height):
    n = len(height)
    if n == 0:
        return 0

    left_max = [0] * n
    right_max = [0] * n
    left_max[0] = height[0]
    right_max[-1] = height[-1]

    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))

⚡ Approach 3: Two Pointers (Best)

The idea in one line: walk in from both ends and always work on the shorter side, so one running max per side is enough.

The idea:

• Put one pointer at the left end and one at the right end.
• Keep leftMax, the tallest wall seen so far from the left.
• Keep rightMax, the tallest wall seen so far from the right.

How it works:

• Compare the two walls at the pointers. Work on the shorter side.
• Move the shorter pointer inward and update its running max.
• Add its running max minus its own height to the water.

Why it is safe:

• If the left wall is shorter, the left bar’s water is decided by leftMax alone.
• The right side is at least as tall, so we only need to know it is taller.
• We never need the exact other max.

Why it is fast:

• Each bar is visited once. Time is O(n) and space is O(1).

Here is a short dry-run showing the pointers and the running maxes.

Steps to Solve

1. Put a left pointer at the start and a right pointer at the end.
2. Set leftMax and rightMax to zero, and total water to zero.
3. While left is before right, look at the two bars under the pointers.
4. If the left bar is shorter, update leftMax, add leftMax minus the left height, then move left right.
5. Otherwise update rightMax, add rightMax minus the right height, then move right left.
6. Stop when the pointers meet. Return the total water.

#include <stdio.h>

int trap(int height[], int n) {
    int left = 0, right = n - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) leftMax = height[left]; // tallest so far
            else water += leftMax - height[left];                // water above this bar
            left++;
        } else {
            if (height[right] >= rightMax) rightMax = height[right];
            else water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

int main(void) {
    int height[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    printf("%d\n", trap(height, 12));
    return 0;
}

6

#include <iostream>
#include <vector>
using namespace std;

int trap(vector<int>& height) {
    int left = 0, right = (int)height.size() - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) leftMax = height[left];  // tallest so far
            else water += leftMax - height[left];                 // water above this bar
            left++;
        } else {
            if (height[right] >= rightMax) rightMax = height[right];
            else water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

int main() {
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    cout << trap(height) << endl;
    return 0;
}

6

public class TrapRain {
    public static 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]) {
                if (height[left] >= leftMax) leftMax = height[left];  // tallest so far
                else water += leftMax - height[left];                 // water above this bar
                left++;
            } else {
                if (height[right] >= rightMax) rightMax = height[right];
                else water += rightMax - height[right];
                right--;
            }
        }
        return water;
    }

    public static void main(String[] args) {
        int[] height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
        System.out.println(trap(height));
    }
}

6

def trap(height):
    left = 0                       # pointer at the start
    right = len(height) - 1        # pointer at the end
    left_max = 0
    right_max = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]          # new tallest wall on the left
            else:
                water += left_max - height[left] # water above this bar
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]        # new tallest wall on the right
            else:
                water += right_max - height[right]
            right -= 1
    return water


height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap(height))

6

function trap(height) {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= leftMax) leftMax = height[left];   // tallest so far
      else water += leftMax - height[left];                  // water above this bar
      left++;
    } else {
      if (height[right] >= rightMax) rightMax = height[right];
      else water += rightMax - height[right];
      right--;
    }
  }
  return water;
}

const height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
console.log(trap(height));

6

Let us walk through the Python version line by line. The clever part is why we only need one running max at a time.

left = 0 and right = len(height) - 1 set the two pointers at the ends. left_max and right_max start at zero. water is the total we build up.

while left < right: runs until the pointers meet.

if height[left] < height[right]: checks which wall is shorter. We always work on the shorter side. This is the heart of the proof. If the left wall is shorter, the water on the left bar is decided by the left side alone. The right side is at least as tall, so it cannot lower the water here.

Inside that branch, if height[left] >= left_max: left_max = height[left] updates the tallest left wall. A taller wall means no water sits on this bar, so we just record it. Otherwise water += left_max - height[left] adds the water above this bar. That is the left max minus the bar’s own height.

left += 1 moves the left pointer inward. The else: branch does the mirror image on the right side. We never look ahead and never store full arrays. One running max per side is enough.

⏱️ Time and Space Complexity

The brute force scans both sides for every bar, so it is O(n²) time. The prefix array method is O(n) time but uses O(n) extra memory for the two helper arrays. The two-pointer method is O(n) time and O(1) space. It is the best of both.

🧩 Key Takeaways

• ✅ Water above one bar is the shorter side max minus that bar’s height.
• ✅ The prefix array method is clean but costs O(n) extra memory.
• ✅ Two pointers always work on the shorter wall, which makes one running max enough per side.
• ✅ Moving the shorter pointer is safe because the taller side can only hold more water back.
• ✅ The two-pointer solution runs in O(n) time with O(1) extra memory.

🚀 What’s Next?

• Container With Most Water
• Valid Palindrome II