42. Trapping Rain Water
Trapping Rain Water
Problem Overview
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.The above elevation map 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 trapped.
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 rain.
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.length1 <= n <= 2 * 1040 <= height[i] <= 105
Considering 2 histogram bars at a time, the enclosed space between the bars is the quantity of water.
Let us look at the algorithm. (Approach 1)
- Run the loop until all bars in the array are traversed.
- Find the max value on the left side of the current bar. Let this value be left_max.
- Find the max value on the right side of the current bar. Let this value be right_max.
- Find the minimum between left_max and right_max.
- Subtract the minimum value from the current bar.
- If the resulting value is greater than 0, add it to our result. Since we cannot have a negative amount of water trapped, we ignore it.
const trap = (height) => {
let largest = height[0];
let largestIndex = 0;
let water = 0;
for(let i=1; i height[i-1]) {
// what is the max water level
let fill = Math.min(largest, height[i]);
// fill in the water between largest and i
for(let j=largestIndex+1; j largest) {
largest = height[i];
largestIndex = i;
}
}
}
return water;
};Complexity analysis.
Time Complexity
We are traversing through the complete array which needs O(N). Additionally, we calculate max values while traversing through the array which takes O(N). Hence the time complexity is O(N²).
Space Complexity
Since we are not using any extra space, space complexity is O(1).
Can we make the algorithm any better? Yes Using two pointer approach
Approach 2:
We keep calculating the max value each time we hit a new bar. Can we keep track of the max value beforehand? We can have 2 arrays that keep track of the max value for the left side and the right side. Create an array for left and create an array for right, and initialize both as 0.
Run the loop for the left as well as the right of each bar and keep track of the max value and save them in the respective positions.
Once the above steps are completed, run the loop for each bar in the array.
Find the minimum among the left, and right, and subtract it from the current bar. Include this quantity in total water.
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
let left = 0,right = height.length-1;
let trappedWater = 0;
let leftMaxHegith = 0;
let rightMaxHegith = 0;
while(left <= right){
if(height[left] < height[right]){
if(height[left] > leftMaxHegith){
leftMaxHegith = height[left];
}else{
trappedWater+= leftMaxHegith - height[left];
}
left++;
}else{
if(height[right] > rightMaxHegith){
rightMaxHegith = height[right];
}else{
trappedWater+=rightMaxHegith-height[right];
}
right--;
}
}
return trappedWater;
};
Complexity analysis.
Time ComplexityWe are traversing through the complete array which needs O(N).
Space Complexity
We are using 2 extra arrays of size N to store max values, hence space complexity is O(N).
Approach 3:
Using stack, a smart approach
Time: O(n) all elements are pushed and pop once
var trap = function(height) {
let stack = new Stack()
let i = 0
let ret = 0
while(i < height.length) {
if (stack.isEmpty() || height[i] <= height[stack.peek()]) {
stack.push(i++)
} else {
let middle = stack.pop()
if (!stack.isEmpty()) {
let minHeight = Math.min(height[i], height[stack.peek()])
ret += (minHeight - height[middle]) * (i - stack.peek() - 1)
}
}
}
return ret
};
class Stack {
constructor() {
this.stack = []
}
push(a) {
this.stack.push(a)
}
pop() {
return this.stack.pop()
}
peek() {
return this.stack[this.stack.length - 1]
}
size() {
return this.stack.length
}
isEmpty() {
return this.stack.length == 0
}
}Resources:
Conclusion
That’s all folks! In this post, we solved LeetCode problem #42. Trapping Rain Water
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment