Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5] Output: 9
Constraints:
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105Problem Overview: Given an array where each element represents the height of a bar in an elevation map, determine how much rainwater can be trapped after raining. Water accumulates in the valleys between taller bars, and the amount at each index depends on the tallest boundary on both sides.
Approach 1: Two-Pass Dynamic Programming (O(n) time, O(n) space)
This method precomputes the tallest wall to the left and right of every index. Create two arrays: leftMax[i] stores the highest bar from the start up to index i, and rightMax[i] stores the highest bar from the end down to i. Iterate once from left to right to fill leftMax, then from right to left for rightMax. The trapped water at index i equals min(leftMax[i], rightMax[i]) - height[i]. If the value is positive, add it to the total. The key insight: water level is limited by the shorter boundary. This approach is straightforward and easy to reason about, which makes it a good first implementation when working with arrays and prefix-style precomputation similar to dynamic programming patterns.
Approach 2: Two-Pointer Technique (O(n) time, O(1) space)
The optimal solution removes the auxiliary arrays by scanning from both ends simultaneously. Initialize two pointers: left at the start and right at the end. Maintain two running values: leftMax and rightMax. At each step, move the pointer pointing to the shorter height. If height[left] < height[right], process the left side: update leftMax or accumulate trapped water using leftMax - height[left]. Otherwise process the right side with rightMax - height[right]. The insight is that the smaller boundary determines the maximum possible water level, so the opposite side cannot affect the current calculation. This reduces memory usage while keeping linear traversal. The pattern is common in two pointer problems where decisions depend on comparing boundary values.
Approach 3: Monotonic Stack (O(n) time, O(n) space)
A stack-based approach processes bars while maintaining a decreasing stack of indices. When a higher bar appears, repeatedly pop indices representing valleys. The popped index forms the bottom of a container, while the current index and the new stack top form the boundaries. Compute width as the distance between boundaries minus one, and height as the difference between the smaller boundary and the valley. Multiply width and height to get trapped water for that segment. This approach demonstrates how monotonic stacks model boundary problems where elements wait for the next greater value.
Recommended for interviews: The two-pointer solution is the expected answer in most interviews because it achieves O(n) time with O(1) space. Starting with the dynamic programming version shows you understand the water-boundary principle, then optimizing to two pointers demonstrates strong algorithmic reasoning.
This approach involves creating two auxiliary arrays to store the maximum heights on the left and right of each bar. With these arrays, you can calculate how much water each bar can trap.
The water trapped above a bar is determined by the minimum of the maximum heights on its left and right, minus the bar's height itself.
This implementation uses two arrays: leftMax and rightMax to keep track of the maximum height encountered from the left and right of each bar respectively. It then calculates the trapped water by iterating through each bar and adding the minimum of these maximum heights minus the bar's height.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) because we traverse the height array three times where n is the length of the array.
Space Complexity: O(n) due to the additional arrays used to store the maximum heights.
The two-pointer technique optimizes space by keeping track of the left and right bars with two pointers. It uses a single loop and calculates water based on the shorter of the two heights at the current pointers.
This approach leverages two pointers, starting from both ends of the array and moving towards the center. It dynamically updates the maximum height seen so far from either direction and calculates water trapped at the current position based on these max heights.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the input array since we process each bar only once.
Space Complexity: O(1) because we use only constant extra space.
| Approach | Complexity |
|---|---|
| Two-Pass Dynamic Programming | Time Complexity: O(n) because we traverse the height array three times where n is the length of the array. |
| Two-Pointer Technique | Time Complexity: O(n), where n is the length of the input array since we process each bar only once. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Dynamic Programming | O(n) | O(n) | Best for understanding the core idea using precomputed left and right maximum arrays |
| Two-Pointer Technique | O(n) | O(1) | Optimal interview solution when memory efficiency matters |
| Monotonic Stack | O(n) | O(n) | Useful when practicing stack patterns or solving related boundary/next-greater problems |
Trapping Rain Water - Google Interview Question - Leetcode 42 • NeetCode • 558,064 views views
Watch 9 more video solutions →Practice Trapping Rain Water with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor