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
Solution¶
The key insight is that water trapped at any position depends on the minimum of the maximum heights to its left and right, minus the height at that position.
Finding boundaries (first loop):
- For each position, track the highest bar to its left and right
- Uses two-pointer technique (i from left, j from right) to fill both arrays in one pass
- left_walls[i] stores the maximum height to the left of position i
- right_walls[j] stores the maximum height to the right of position j
Calculating trapped water (second loop):
- For each position i, water trapped = min(left_max, right_max) - current_height
- Only add water if the result is positive (can't have negative water)
Time Complexity: O(n)
Space Complexity: O(n)
Example: Copyheight = [0,1,0,2,1,0,1,3,2,1,2,1]
- For position i=2 (height=0):
- left_max = 1
- right_max = 3
- trapped_water = min(1,3) - 0 = 1
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=-i-1
left_walls[i]=max_left
right_walls[j]=max_right
max_left=max(height[i],max_left)
max_right=max(height[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
trap([0,2,0,3,1,0,1,3,2,1])
9