How to Solve the Trapping Rain Water Problem on LeetCode
The Trapping Rain Water problem is a classic LeetCode challenge. It tests your skills in array manipulation, two-pointer techniques, and optimizing both time and space complexity.
Problem Statement
Given n non-negative integers representing an elevation map, compute how much water it can trap after raining.
The input is an array of heights; each bar has width 1.
Example:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: 6 units of water can be trapped.
Why This Problem Matters for Interviews
This problem:
- Checks your grasp of array traversal and prefix/suffix computations
- Pushes you to optimize naive solutions
- Encourages clear thinking about edge cases and optimal pointer use
Approaches to Solve Trapping Rain Water
1. Brute Force
For each bar, find the max on the left and right, compute trapped water.
Time Complexity: O(n²)
def trap(height: list[int]) -> int:
n = len(height)
water = 0
for i in range(n):
left_max = max(height[:i+1])
right_max = max(height[i:])
water += min(left_max, right_max) - height[i]
return water
2. Two Pointers (Optimal)
Use two pointers moving inward from each end, keeping track of max left and right.
Time Complexity: O(n)
Space Complexity: O(1)
def trap(height: list[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return water
Key Interview Talking Points
- Intuition behind trapping water: the minimum of max-left and max-right.
- Why brute force fails on performance.
- Two-pointer optimization and how it works.
- Discuss stack-based solutions if time allows.
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force | O(n²) | O(1) |
| Two Pointers | O(n) | O(1) |
Pro Interview Tips
- Always clarify problem constraints (empty input? negative heights?).
- Trace your algorithm on a sample input out loud.
- Practice with test cases