Trapping Rain Water
Problem
Given an array height representing an elevation map where the width of each bar is 1, return the total amount of rainwater trapped after raining.
- n == height.length
- 1 ≤ n ≤ 2 * 10⁴
- 0 ≤ height[i] ≤ 10⁵
Example
height = [0,1,0,2,1,0,1,3,2,1,2,1]6The algorithm uses two pointers starting at the ends of the array. Initially, left pointer is at index 0 with height 0, and right pointer at index 11 with height 1. The left_max is 0 and right_max is 1. Since left_max < right_max, move left pointer to index 1 (height 1), update left_max to 1, and add trapped water (1 - 1 = 0). Next, left_max (1) is not less than right_max (1), so move right pointer to index 10 (height 2), update right_max to 2, and add trapped water (2 - 2 = 0). The process continues, moving pointers inward and accumulating trapped water based on the minimum of left_max and right_max. The critical insight is that water trapped at any position depends on the smaller of the maximum heights to its left and right. By moving the pointer with the smaller max inward, the algorithm ensures all trapped water is counted efficiently in a single pass.
Approach
Straightforward Solution
A brute-force approach calculates, for each bar, the maximum height to its left and right, then sums the minimum of these two minus the bar's height. This requires O(n^2) time due to nested scans, which is inefficient for large inputs.
Core Observation
The amount of water trapped at any position depends on the minimum of the maximum heights to its left and right minus the height at that position. This is a fundamental property of the problem and the basis for any solution.
Path to Optimal
PreviewPrecomputing left_max and right_max arrays reduces time to O(n) but uses O(n) space…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewInitialize two pointers at the start and end of the array, along with left_max and right_max as the heights at these pointers…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each pointer moves inward at most n times, resulting in a single pass through the array.
Space
O(1)
Only a fixed number of variables are used to track pointers and maximum heights, with no additional data structures proportional to input size.
Pattern Spotlight
Two Pointers (Greedy Contraction)
The logic of any optimal Two Pointers solution lies in finding the condition that allows you to permanently discard one end of the search space by moving the pointer that is the current 'limiting factor' to the solution.
Solution
| 1 | class Solution:
|
| 2 | def trap(self, height: list[int]) -> int:
|
| 3 | if not height:
|
| 4 | return 0
|
| 5 |
|
| 6 | l, r = 0, len(height) - 1
|
| 7 | left_max, right_max = height[l], height[r]
|
| 8 | res = 0
|
| 9 |
|
| 10 | while l < r:
|
| 11 | if left_max < right_max:
|
| 12 | l += 1
|
| 13 | left_max = max(left_max, height[l])
|
| 14 | res += left_max - height[l]
|
| 15 | else:
|
| 16 | r -= 1
|
| 17 | right_max = max(right_max, height[r])
|
| 18 | res += right_max - height[r]
|
| 19 |
|
| 20 | return res |
Step-by-Step Solution
Initialize Two Pointers and Maximum Heights
| 6 | l, r = 0, len(height) - 1
|
| 7 | left_max, right_max = height[l], height[r]
|
| 8 | res = 0
|
Objective
To set up the initial state for the two-pointer traversal, including pointers at both ends and their corresponding maximum heights.
Key Insight
Starting with pointers at the array boundaries and initializing left_max and right_max to the heights at these positions establishes the initial known boundaries for trapping water. This setup is crucial because it allows the algorithm to compare and move pointers inward based on these max heights, enabling the greedy contraction strategy.
Interview Quick-Check
Core Logic
Initializing left_max and right_max to the heights at the pointers ensures the algorithm always knows the current limiting heights on both sides.
State & Boundaries
Pointers start at indices 0 and len(height) - 1, covering the entire array.
Move Pointers Inward and Accumulate Trapped Water
To iteratively move the pointer with the smaller max height inward, update max heights, and accumulate trapped water based on the difference between max height and current bar height.
Return Total Trapped Water
To return the accumulated total amount of trapped rainwater after processing all bars.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if left_max < right_max:Compare left_max and right_max to decide which pointer to move.
This comparison is the core greedy decision that guarantees correctness: moving the pointer with the smaller max height ensures that the trapped water calculation is bounded by a known limiting height, preventing undercounting or overcounting.
res += left_max - height[l]Add trapped water at the left pointer position to the result.
This line performs the essential calculation of trapped water at the current position, leveraging the updated left_max to ensure correctness and completeness of the total.
res += right_max - height[r]Add trapped water at the right pointer position to the result.
This line is the counterpart to the left side calculation and is critical for accumulating trapped water correctly on the right side.
Full line-by-line criticality + rationale for all 15 lines available on Pro.
Test Your Understanding
Why does moving the pointer with the smaller max height guarantee that all trapped water is accounted for correctly?
See the answer with Pro.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Trapping Rain Water from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Trapping Rain Water drill