Here in the post I will explain and give solution to Leetcode problem number 42.
42. Trapping Rain Water
Level- hard
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
To reach the solution of this problem, first we need to understand the clues hidden in the question.
Clue 1: Count of tower should be more than two.
It's quite apparent that for any water to get stored within a area, first it should be enclosed inside the boundary of at least 2 towers. Hence there should be a minimum of 3 towers.
Clue 2: Block in ascending and descending order cannot form gap and hence cannot trap water.
Clue 3: Water the height for trapped water will depend on the minimum height between its left or right wall.
Combining all these information we can understand that trapped water for a block will be
(Min(Max left side block height, Max of right side block height) - Current Block height) * area of block.
As area of block will always be one so eventually it will be
Trapped Water On Block = Min(Max_Left_Block, Max_Right_Block)
To solve the problem we can can create a leftSideArray, which will determine the max height of block, left to the current block and max height of block, right to the current block.
Solution in Javascript
var trap = function(height) {
if(height.length < 3) {
return 0
}
let leftArray = findLeftMaxWall(height)
let rightArray = findRightMaxWall(height)
let trapArray = []
let totalTrappedWater = 0
let i = 0
let blockAreaWithTrappedWater = 0
while(i < height.length){
if(leftArray[i] == 0 || rightArray[i] == 0 || Math.min(leftArray[i], rightArray[i]) < height[i]){
blockAreaWithTrappedWater = 0
} else{
blockAreaWithTrappedWater = Math.min(leftArray[i], rightArray[i]) - height[i]
}
trapArray.push(blockAreaWithTrappedWater)
totalTrappedWater += blockAreaWithTrappedWater
i++
}
console.log(`trapArray, ${trapArray}`);
return totalTrappedWater
};
// Forming Max left Array
var findLeftMaxWall = function(height) {
let i = 0
let leftArray = []
let maxHeightLeft = 0
while(i < height.length){
if(i - 1 >= 0 && height[i-1] > maxHeightLeft){
maxHeightLeft = height[i-1]
}
leftArray.push(maxHeightLeft)
console.log(`leftArray:, ${leftArray}`);
i++
}
return leftArray
};
// Forming Max right Array
var findRightMaxWall = function(height) {
let i = height.length - 1
let rightArray = []
let maxHeightRight = 0
while(i >= 0){
if(i+1 <= height.length - 1 && height[i+1] > maxHeightRight){
maxHeightRight = height[i+1]
}
rightArray[i] = maxHeightRight
console.log(`rightArray:, ${rightArray}`);
i--
}
return rightArray
};
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]))
// Answer is 6
Solution in Python
# Function to return the maximum
# water that can be stored
def maxWater(arr, n):
# To store the maximum water
# that can be stored
res = 0
# For every element of the array
for i in range(1, n - 1):
# Find the maximum element on its left
left = arr[i]
for j in range(i):
left = max(left, arr[j])
# Find the maximum element on its right
right = arr[i]
for j in range(i + 1, n):
right = max(right, arr[j])
# Update the maximum water
res = res + (min(left, right) - arr[i])
return res
#Driver code
if __name__ == "__main__":
arr = [0, 1, 0, 2, 1, 0,
1, 3, 2, 1, 2, 1]
n = len(arr)
print(maxWater(arr, n))
Top comments (0)