Trapping Rain Water
LeetCode #42 · Hard · Two Pointers · C++ solution with worked-out approach and complexity analysis.
Approach
Two Pointers
Key insight
Water trapped at position i = min(maxLeft, maxRight) - height[i] Instead of computing maxLeft and maxRight for every position separately, we use two pointers starting from both ends and track running maximums.
Strategy
- 1Start with pointers at both ends (l=0, r=n-1)
- 2Track maxL (max height from left) and maxR (max height from right)
- 3Always process the side with the smaller max height:
Time
O(n)
single pass through the array
Space
O(1)
only using a few variables
Problem description(from LeetCode)
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.
Examples
Example 1
- Input:
- height = [0,1,0,2,1,0,1,3,2,1,2,1]
- Output:
- 6
- Note:
- The elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Input: height = [4,2,0,3,2,5] Output: 9
Constraints
- •n == height.length
- •1 <= n <= 2 * 10^4
- •0 <= height[i] <= 10^5
C++ Solution
solution.cpp
class Solution {
public:
int trap(vector<int> &height) {
int res = 0, l = 0, r = height.size() - 1;
int maxL = height[l], maxR = height[r];
while (l <= r) {
if (maxL <= maxR) {
res += max(maxL - height[l], 0);
maxL = max(maxL, height[l]);
l++;
} else {
res += max(maxR - height[r], 0);
maxR = max(maxR, height[r]);
r--;
}
}
return res;
}
};