Trapping Rain Water

hard array two pointers

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Inputheight = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Output6

The classic profile traps six units of water in the dips between taller bars.

heights (non-negative, comma-separated)

def trap(height):
    l, r = 0, len(height) - 1
    left_max = right_max = water = 0
    while l < r:
        if height[l] < height[r]:
            left_max = max(left_max, height[l])
            water += left_max - height[l]
            l += 1
        else:
            right_max = max(right_max, height[r])
            water += right_max - height[r]
            r -= 1
    return water

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

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1;
        int leftMax = 0, rightMax = 0, water = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                leftMax = Math.max(leftMax, height[l]);
                water += leftMax - height[l];
                l++;
            } else {
                rightMax = Math.max(rightMax, height[r]);
                water += rightMax - height[r];
                r--;
            }
        }
        return water;
    }
}

int trap(vector<int>& height) {
    int l = 0, r = (int)height.size() - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (l < r) {
        if (height[l] < height[r]) {
            leftMax = max(leftMax, height[l]);
            water += leftMax - height[l];
            l++;
        } else {
            rightMax = max(rightMax, height[r]);
            water += rightMax - height[r];
            r--;
        }
    }
    return water;
}

Explanation

Water sitting above any bar is decided by the shorter of the tallest wall to its left and the tallest wall to its right. This solution finds that answer in a single pass using two pointers that walk inward from both ends.

We keep l on the left, r on the right, plus left_max and right_max for the tallest bar seen from each side so far.

The clever part: we always move the pointer on the lower side. If height[l] < height[r], then the left side is the limiter, so whatever left_max is must be the true bound for bar l — the water there is left_max - height[l]. Otherwise we do the same on the right.

Example: with [0,1,0,2,1,0,1,3,2,1,2,1], every dip between taller bars gets filled. Adding each contribution as we go totals 6 units.

It works because moving the shorter side guarantees the opposite wall is at least as tall, so the running max on the moving side is safe to trust. One pass, no extra arrays.

Time: O(n) Space: O(1)