Water tapping problem
Filed under OYO
Free read 1 of 3Use two pointers starting at both ends of the array.
The question
Given an array of non-negative integers representing an elevation map, compute how much water it can trap after raining.
Constraints
- Array length up to 10^5
- Elements are non-negative
- O(n) time complexity required
Examples
- Input
- [0,1,0,2,1,0,1,3,2,1,2,1]
- Output
- 6
- Why
- The elevation map traps 6 units of water.
Approach
Use two pointers starting at both ends of the array.
Maintain left_max and right_max variables to track the highest walls seen so far.
Move the pointer pointing to the smaller height, updating the trapped water based on the difference between current height and its respective max.
Solution
O(n) time, O(1) space
def trap(height):
l, r = 0, len(height) - 1
l_max, r_max = 0, 0
water = 0
while l < r:
if height[l] < height[r]:
l_max = max(l_max, height[l])
water += l_max - height[l]
l += 1
else:
r_max = max(r_max, height[r])
water += r_max - height[r]
r -= 1
return water
Tips
- What they are testing: Test with flat arrays and strictly increasing/decreasing arrays.
- Common mistake: Using a brute force O(n^2) approach by finding max left and right for every element.
Related OYO questions
Collected from public candidate posts and coding forums. Updated Nov 2026.