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
Precomputing left_max and right_max arrays reduces time to O(n) but uses O(n) space. The key insight is that by using two pointers starting at both ends and tracking left_max and right_max on the fly, the algorithm can decide which pointer to move based on which side has the smaller max height. This allows the trapped water calculation to be done in a single pass with O(1) extra space.
Optimal Approach
Initialize two pointers at the start and end of the array, along with left_max and right_max as the heights at these pointers. While the pointers do not meet, move the pointer with the smaller max height inward, update the max height for that side, and accumulate trapped water as the difference between the max height and the current bar height. This greedy approach guarantees all trapped water is counted correctly in O(n) time and O(1) space.
Time
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 |
| 1 | class Solution { |
| 2 | public int trap(int[] height) { |
| 3 | if (height.length == 0) { |
| 4 | return 0; |
| 5 | } |
| 6 | |
| 7 | int l = 0; |
| 8 | int r = height.length - 1; |
| 9 | int leftMax = height[l]; |
| 10 | int rightMax = height[r]; |
| 11 | int res = 0; |
| 12 | |
| 13 | while (l < r) { |
| 14 | if (leftMax < rightMax) { |
| 15 | l++; |
| 16 | leftMax = Math.max(leftMax, height[l]); |
| 17 | res += leftMax - height[l]; |
| 18 | } else { |
| 19 | r--; |
| 20 | rightMax = Math.max(rightMax, height[r]); |
| 21 | res += rightMax - height[r]; |
| 22 | } |
| 23 | } |
| 24 | |
| 25 | return res; |
| 26 | } |
| 27 | } |
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
| 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]
|
Objective
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.
Key Insight
The greedy choice to move the pointer with the smaller max height inward is based on the fact that trapped water is limited by the smaller boundary. By updating the max height on that side and adding the difference to the result, the algorithm correctly counts trapped water at each step without revisiting positions. This approach avoids the need for extra arrays and achieves O(1) space complexity.
Interview Quick-Check
Core Logic
At each step, move the pointer with the smaller max height inward, update that max height, and add the trapped water (max height - current height) to the result.
State & Boundaries
Continue until the two pointers meet, ensuring all positions are processed.
Common Pitfalls & Bugs
Failing to update max heights before calculating trapped water can lead to incorrect results.
Return Total Trapped Water
| 20 | return res |
Objective
To return the accumulated total amount of trapped rainwater after processing all bars.
Key Insight
After the two pointers meet, all positions have been evaluated for trapped water. Returning the accumulated result provides the final answer to the problem.
Interview Quick-Check
Core Logic
Returning the accumulated result after the loop completes gives the total trapped water.
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.
left_max, right_max = height[l], height[r]Initialize left_max and right_max to the heights at the pointers.
Tracking the maximum heights seen so far on each side is essential for determining trapped water at each position.
left_max = max(left_max, height[l])Update left_max to the maximum of current left_max and new height at left pointer.
Updating left_max maintains the highest boundary on the left side, which is critical for accurate trapped water calculation.
right_max = max(right_max, height[r])Update right_max to the maximum of current right_max and new height at right pointer.
Maintaining the highest boundary on the right side is necessary for correct trapped water calculation.
if not height:Check if the input height array is empty.
An empty array means no bars exist to trap water, so the result is zero immediately.
while l < r:Loop while left pointer is less than right pointer.
The loop condition ensures all positions between the pointers are processed exactly once.
return resReturn the total trapped water accumulated.
After processing all positions, returning the result provides the final answer to the problem.
l, r = 0, len(height) - 1Initialize left and right pointer at the start and end of the array respectively.
Starting the left pointer at index 0 sets the initial boundary for the left side of the trapping region. Starting the right pointer at the last index sets the initial boundary for the right side of the trapping region.
l += 1Increment the left pointer to move inward.
Moving the left pointer inward explores the next bar on the left side, where trapped water may accumulate.
else:Else branch: move the right pointer inward.
When right_max is less or equal, moving the right pointer inward explores the next bar on the right side.
r -= 1Decrement the right pointer to move inward.
Moving the right pointer inward allows the algorithm to process bars from the right side towards the center.
return 0Return 0 when the height array is empty.
This early return prevents unnecessary computation and handles edge cases gracefully.
res = 0Initialize the result accumulator for trapped water.
This variable accumulates the total trapped water as the algorithm progresses.
Test Your Understanding
Why does moving the pointer with the smaller max height guarantee that all trapped water is accounted for correctly?
Because the trapped water at the pointer depends on the smaller of the two max heights, moving the pointer with the smaller max height ensures that the boundary limiting the trapped water is known and fixed, allowing safe calculation of trapped water at that position without missing any contributions.
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