Q14: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 (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.
Solution:
class Solution {
public:
int trap(vector<int>& height) {
int l = 0, r = height.size()-1, level = 0, water = 0;
while (l < r) {
int lower = height[height[l] < height[r] ? l++ : r--];
level = max(level, lower);
water += level - lower;
}
return water;
}
};
Explantion:
>The code uses a two-pointer approach (l and r) to traverse the height vector from both ends.
>level represents the current height of the water, and water is the accumulated water.
>The loop continues until the left pointer l is less than the right pointer r.
>The smaller of the two heights at the current pointers (l and r) is determined
and stored in the variable lower.
>level is updated to be the maximum of its current value and the lower height.
>The amount of water trapped between the current height and the lower height is
calculated and added to the water variable.
>The process continues until the entire vector is processed.
>The total accumulated water is returned as the result.
If anyone have better solution so please comment:)