In the Leetcode Trapping Rain Water problem solution 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 1:
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.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints:
- n == height.length
- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105
Solution in C Programming
int trap(int* height, int heightSize){
int lm,rm,i,res=0,left,right;
left=0;
right=heightSize-1;
lm=0;
rm=0;
res=0;
while(left<right){
if(height[left]<=height[right]){
if(height[left]>lm)
lm=height[left];
else
res+=lm-height[left];
left++;
}
else{
if(height[right]>rm){
rm=height[right];
}
else
res+=rm-height[right];
right--;
}
}
return res;
}Solution in C++ Programming
class Solution {
public:
int trap(vector<int>& height) {
int n=height.size();
vector<int>left(n,0);
vector<int>right(n,0);
left[0]=height[0];
right[n-1]=height[n-1];
for(int i=1;i<n;i++){
left[i]=max(left[i-1],height[i]);
}
for(int i=n-2;i>=0;i--){
right[i]=max(right[i+1],height[i]);
}
int ans=0;
for(int i=0;i<n;i++){
ans+=min(left[i],right[i])-height[i];
}
return ans;
}
};Solution in Java Programming
class Solution {
public int trap(int[] height) {
int leftMax = 0, rightMax = 0;
int i=0,j=height.length-1;
int trapped=0;
while(i<j){
if(height[i]>leftMax) leftMax = height[i];
if(height[j]>rightMax) rightMax = height[j];
if(leftMax<rightMax){
trapped+=(leftMax-height[i]);
i++;
}
else{
trapped+=(rightMax-height[j]);
j--;
}
}
return trapped;
}
}
Solution in Python Programming
class Solution:
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if not height or len(height) == 1: return 0
res, size = 0, len(height)
leftMax, rightMax = [None] * size, [None] * size
leftMax[0], rightMax[-1] = height[0], height[-1]
for i in range(1, size):
leftMax[i] = max(leftMax[i - 1], height[i])
for i in range(size - 2, 0, -1):
rightMax[i] = max(rightMax[i + 1], height[i])
for i in range(1, size - 1):
res += min(rightMax[i], leftMax[i]) - height[i]
return resSolution in C# Programming
public class Solution {
int Puddles(int[] height, bool allowEqual = false) {
int total = 0;
int highest = 0;
int proposedPuddle = 0;
for (int i=0; i<height.Length; i++) {
if (height[i] > height[highest] || (allowEqual && height[i] == height[highest])) {
int puddle = proposedPuddle;
if (puddle > 0)
total += puddle;
highest = i;
proposedPuddle = 0;
}
proposedPuddle += Math.Max(height[highest] - height[i], 0);
}
return total;
}
public int Trap(int[] height) {
int total = Puddles(height, true);
Array.Reverse(height);
total += Puddles(height, false);
return total;
}
}Also read,