15. Trapping Rain Water · DSA Practice

height is an elevation map where each bar has width 1. After it rains, how many units of water are trapped between the bars?

Example 1

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

Output: 7

Explanation: Positions 1, 2 and 3 hold 3, 1 and 3 units.

Example 2

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

Output: 4

Hint 1

Water above bar i = min(highest bar on its left, highest bar on its right) − height[i].

Hint 2

Two pointers: whichever side has the lower wall is already decided.

Two PointersStackDynamic Programming

Approach 1: Prefix / suffix maxima

Precompute leftMax[i] and rightMax[i] arrays, then sum min − height.

⏱ Time O(n)💾 Space O(n)

Approach 2: Monotonic stack

Pop bars when a taller bar arrives and add the water trapped in each “bowl”.

⏱ Time O(n)💾 Space O(n)

Approach 3: Two pointers ✅

Move the side with the lower wall; its running max decides the water there.

⏱ Time O(n)💾 Space O(1)

Reference solution for Two pointers (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def trap(self, height: List[int]) -> int:
        lo, hi = 0, len(height) - 1
        left_max = right_max = water = 0
        while lo < hi:
            if height[lo] < height[hi]:            # the left side is the bottleneck
                left_max = max(left_max, height[lo])
                water += left_max - height[lo]
                lo += 1
            else:
                right_max = max(right_max, height[hi])
                water += right_max - height[hi]
                hi -= 1
        return water

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

class Solution {
public:
    int trap(vector<int>& height) {
        int lo = 0, hi = (int)height.size() - 1, leftMax = 0, rightMax = 0, water = 0;
        while (lo < hi) {
            if (height[lo] < height[hi]) {
                leftMax = max(leftMax, height[lo]);
                water += leftMax - height[lo++];
            } else {
                rightMax = max(rightMax, height[hi]);
                water += rightMax - height[hi--];
            }
        }
        return water;
    }
};

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

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

This problem is explained in the lesson Two Pointers.