Trapping Rain Water

📌 Definition:

Given bar heights, compute how much rain water is trapped between them (e.g. [0,1,0,2,1,0,1,3,2,1,2,1] -> 6).

📖 Detailed Explanation:

Water above each bar is min(maxLeft, maxRight) - height. The two-pointer method walks inward from both ends, always advancing the side with the smaller running max, because that side's water is bounded by its own max. O(n) time, O(1) space — no prefix arrays needed.

💻 Solutions:

public static int trap(int[] h) {
    int left = 0, right = h.length - 1, leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (h[left] < h[right]) {
            leftMax = Math.max(leftMax, h[left]);
            water += leftMax - h[left];
            left++;
        } else {
            rightMax = Math.max(rightMax, h[right]);
            water += rightMax - h[right];
            right--;
        }
    }
    return water;
}

function trap(h) {
  let left = 0, right = h.length - 1, leftMax = 0, rightMax = 0, water = 0;
  while (left < right) {
    if (h[left] < h[right]) {
      leftMax = Math.max(leftMax, h[left]);
      water += leftMax - h[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, h[right]);
      water += rightMax - h[right];
      right--;
    }
  }
  return water;
}

def trap(h):
    left, right = 0, len(h) - 1
    left_max = right_max = water = 0
    while left < right:
        if h[left] < h[right]:
            left_max = max(left_max, h[left])
            water += left_max - h[left]
            left += 1
        else:
            right_max = max(right_max, h[right])
            water += right_max - h[right]
            right -= 1
    return water

🔑 Key Points:

Water[i] = min(maxLeft, maxRight) - height[i]
Two pointers, advance the smaller-max side
O(1) space vs prefix-max arrays
O(n) time

🌍 Real-World Example:

A famous hard-ish interview problem that rewards the insight of bounding each position by the smaller of two maxima — the same reasoning used in container and terrain problems.

🎯 Scenario-Based Interview Question:

Why is it safe to move the pointer on the side with the smaller running max?

‹ Previous

Longest Palindromic Substring

Next ›

Product of Array Except Self