LeetCode - Trapping Rain Water
Description: https://leetcode.com/problems/trapping-rain-water/description/
To solve this problem, the main observation is that at each index i, the amount of water that can be trapped depends on the the highest bars to its left and right elements, minus its own height.
Key insights:
- Water level at
index_i = min(maxLeft, maxRight) - height[i]
- Two-pointer technique optimizes space complexity from %O(N)% to %O(1)%
Algorithm steps:
- Initialize two pointers (left, right) at array ends
- Track max heights seen from left and right
- Process smaller height side first:
- If current
height > max_seen
, update max - Else add trapped water (
max - current_height
)
- If current
- Move pointer inward and repeat
Here are interactive visualizations for two example test cases:
Why it works:
- When
height[left] < height[right]
, right bar guarantees water can be trapped based onleft_max
- Similarly for right side when
height[right] <= height[left]
- Always process the smaller side since it determines water level
Complexity:
- Time: %O(N)%
- Auxiliary space: %O(1)%
You can find the full source code solution at https://github.com/vndee/dsa-python/blob/main/linear_iteration/trapping_rain_water.py. Please consider subscribing to my blog to stay updated with more algorithm tutorials and coding insights.