Link to Question

HARD

Trapping Rain Water

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.

Example

Input:

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

Output:

6

Explanation:
The above elevation map (represented by array [0,1,0,2,1,0,1,3,2,1,2,1]) is able to trap 6 units of rain water.

---

Constraints

• 1 ≤ height.length ≤ 2 × 10⁴
• 0 ≤ height[i] ≤ 10⁵

---

Solution: Two Pointers

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

C++

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