42. Trapping Rain Water Leetcode Solution
Trapping Rain Water Leetcode Problem :
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.
Trapping Rain Water Leetcode Solution :
Constraints :
- n == height.length
- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105
Example 1:
- Input: height = [4,2,0,3,2,5]
- Output: 9
Approach :
Iterate from left to right with two pointers.
When we come across height[end] >= height[start], fill the pool with water, while keeping track of ‘occupied area’ (i.e. elevations from steps in between).
At the same time, use a hash-set to keep track of the indices already filled. Because we can’t hash a pair<int,int>, we use a basic hashing function (start*20000 + end), since those are the size constraints, and we know the result of the hash fits within an int32 data type.
Then iterate from right to left. There must be a second sweep from right to left because we could have cases where there’s a huge ‘wall’ on the left and the left->right sweep wouldn’t conclude those pools to be fillable.
We do the same thing, but everytime the right->left sweep detects something fillable, check if that pool has already been filled by O(1) search on the hashset. If not, add to the accumulated fill area.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int trap(vector< int>& height) {
int n = height.size();
int lmax = height[0];
int rmax = height[n-1];
int lpos = 1;
int rpos = n-2;
int water = 0;
while(lpos <= rpos)
{
if(height[lpos] >= lmax)
{
lmax = height[lpos];
lpos++;
}
else if(height[rpos] >= rmax)
{
rmax = height[rpos];
rpos--;
}
else if(lmax <= rmax && height[lpos] < lmax)
{
water += lmax - height[lpos];
lpos++;
}
else
{
water += rmax - height[rpos];
rpos--;
}
}
return water;
}
};
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = height[0], rightMax = height[height.length - 1];
int water = 0;
while (left < right) {
if (leftMax < rightMax) {
left++;
if (leftMax < height[left]) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
} else {
right--;
if (rightMax < height[right]) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
}
}
return water;
}
}
class Solution:
def sumBackets(self, height: list[int], left, right):
minHeightLeft = height[left]
total = 0
leftBacket = 0
locationMinLeft = left
while left < right:
if height[left] < minHeightLeft:
leftBacket += minHeightLeft - height[left]
else:
minHeightLeft = height[left]
total += leftBacket
leftBacket = 0
locationMinLeft = left
left += 1
if minHeightLeft <= height[right]:
return total + leftBacket, right
else :
return total, locationMinLeft
def sumBacketsReverce(self, height: list[int], left, right):
minHeightRight = height[right]
total = 0
rightBacket = 0
locationMinRight = right
while left < right:
if height[right] < minHeightRight:
rightBacket += minHeightRight - height[right]
else :
minHeightRight = height[right]
total += rightBacket
rightBacket = 0
locationMinRight = right
right -= 1
if minHeightRight <= height[left]:
return total + rightBacket, left
else :
return total, locationMinRight
def trap(self, height: List[int]) -> int:
right = len(height)-1
left =0
totalSum =0
while left < right-1:
if( height[left]< height[right]):
total, left = self.sumBackets(height, left, right)
else:
total, right = self.sumBacketsReverce(height, left, right)
totalSum += total
return totalSum
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment