Trapping Rain Water — Two Pointer O(1) Space

Problem

Given heights, compute how much water can be trapped.

Example: [0,1,0,2,1,0,1,3,2,1,2,1] → 6

Approach 1 — Two Pointers (O(1) space)

Maintain left, right pointers and max_left, max_right. Water at position = min(max_l, max_r) - height.

Approach 2 — Monotonic Stack

For each bar popped from stack, the water above it = min(current height, stack top height) - popped height.

Time: O(n) | Space: O(1) two-pointer

Solutions

Python — Two Pointer

class Solution:
    def trap(self, height: list[int]) -> int:
        l,r=0,len(height)-1; ml=mr=0; water=0
        while l<r:
            if height[l]<=height[r]:
                if height[l]>=ml: ml=height[l]
                else: water+=ml-height[l]
                l+=1
            else:
                if height[r]>=mr: mr=height[r]
                else: water+=mr-height[r]
                r-=1
        return water

Python — Monotonic Stack

class Solution:
    def trap(self, height: list[int]) -> int:
        stack=[]; water=0
        for i,h in enumerate(height):
            while stack and height[stack[-1]]<h:
                bot=stack.pop()
                if not stack: break
                w=i-stack[-1]-1
                ht=min(height[stack[-1]],h)-height[bot]
                water+=w*ht
            stack.append(i)
        return water

C++

class Solution {
public:
    int trap(vector<int>& h){
        int l=0,r=h.size()-1,ml=0,mr=0,w=0;
        while(l<r){
            if(h[l]<=h[r]){ml=max(ml,h[l]);w+=ml-h[l];l++;}
            else{mr=max(mr,h[r]);w+=mr-h[r];r--;}
        }
        return w;
    }
};

Complexity

Time: O(n) | Space: O(1) two-pointer, O(n) stack