Trapping Rain Water — Day 11(Python)
Today we will be looking at one of the leetcode’s hard tagged questions.
42. Trapping Rain Water
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.
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 being trapped.
Before we look into the solution, let us run through a few examples.
Input: [3, 0, 3]
Input: [3, 0, 1, 0, 3]
Input: [3, 0, 1, 0, 2]
Considering 2 histogram bars at a time, the enclosed space between the bars is the quantity of water. Let us look at the algorithm.
- Run the loop until all bars in the array is traversed.
2. Find the max value on the left side of the current bar. Let this value be left_max.
3. Find the max value on the right side of the current bar. Let this value be right_max.
4. Find the minimum between left_max and right_max.
5. Subtract the minimum value from the current bar.
6. If the resulting value is greater than 0, add it to our result. Since we cannot have a negative amount of water being trapped, we ignore it.
def trap(self, height: List[int]) -> int:
total_water = 0
for i in range(1, len(height)-1):
l = max(height[:i])
r = max(height[i+1:])
water = min(l, r) - height[i]
total_water += water
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²).
Since we are not using any extra space, space complexity is O(1).
Can we make the algorithm any better?
We keep calculating the max value each time we hit a new bar. Can we keep track of max value beforehand? We can have 2 arrays that keep track of max value for the left side and the right side.
- Create an array for left and create an array for right, 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, right, and subtract it from the current bar. Include this quantity in total water.
def trap(self, height: List[int]) -> int: if height == :
return 0 left = [0 for i in range(len(height))]
right = [0 for i in range(len(height))]
total_water = 0
left = height
for i in range(1, len(height)):
left[i] = max(left[i-1], height[i])
right[-1] = height[-1]
for i in range(len(height)-2, -1, -1):
right[i] = max(right[i+1], height[i])
for i in range(len(height)):
total_water += min(left[i], right[i]) - height[i]
We are traversing through the complete array which needs O(N).
We are using 2 extra arrays of size N to store max values, hence space complexity is O(N).
Kindly let me know in case you find any errors in the article. Additionally, I would like to improve my writing skills, any suggestions or comments are welcomed.