Thursday, 16 January 2025
0013 - Trapping Rain Water
You are given an array non-negative integers height which represent an elevation map. Each value height[i] represents the height of a bar, which has a width of 1.
Return the maximum area of water that can be trapped between the bars.
Example 1:
Input: height = [0,2,0,3,1,0,1,3,2,1]
Output: 9
Water trapped at any point depends on the minimum of tallest walls on its left and right, minus its own height.
Create 2 lists which keep track of max water on left and right of current position
Now in another for loop water trapped = min of left and right wall-current height. Increment water only if positive
In [ ]:
def trap(height):
left_walls=[0]*len(height)
right_walls=[0]*len(height)
max_left,max_right=0,0
water=0
for i in range(len(height)):
j=-1-j
left_walls[i]=max_left
right_walls[j]=max_right
max_left=max(left_walls[i],max_left)
max_right=max(right_walls[j],max_right)
for i in range(len(height)):
potential = min(left_walls[i],right_walls[i])
water+=max(0,potential-height[i])
return water
Subscribe to:
Posts (Atom)