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: You are given an array where each element represents the height of a vertical bar in an elevation map. After rain, water collects in the gaps between bars. The task is to compute how many total units of water remain trapped after the rain.
Approach 1: Two-Pass Dynamic Programming (O(n) time, O(n) space)
This approach precomputes the tallest bar on the left and right of every index. Create two arrays: leftMax[i] stores the maximum height from the start up to i, and rightMax[i] stores the maximum height from the end down to i. The water trapped above index i is min(leftMax[i], rightMax[i]) - height[i]. Iterate through the array once to fill leftMax, once for rightMax, and once more to accumulate trapped water. Time complexity is O(n) and space complexity is O(n). This method is straightforward and a good way to understand the core insight that water level depends on the shorter boundary.
This problem is a classic example involving arrays and boundary precomputation using dynamic programming style prefix/suffix information.
Approach 2: Two-Pointer Technique (O(n) time, O(1) space)
The optimal solution eliminates the extra arrays by processing from both ends simultaneously. Maintain two pointers: left at the start and right at the end. Track the highest bars seen so far from both directions using leftMax and rightMax. If height[left] < height[right], the trapped water depends only on the left side because the right boundary is guaranteed to be taller. Update leftMax or accumulate water, then move left. Otherwise process the right side similarly. Each index is visited once, producing O(n) time and O(1) extra space. This technique relies on the observation that the smaller boundary determines the water level.
This strategy is a standard pattern when solving problems with two pointers moving toward each other while maintaining partial state.
Approach 3: Monotonic Stack (O(n) time, O(n) space)
A stack-based solution processes bars while maintaining a decreasing stack of indices. When the current bar becomes taller than the bar at the top of the stack, a container boundary is discovered. Pop the stack to form a valley, compute the bounded height using the difference between the current bar and the new stack top, and multiply by the horizontal distance. Each index enters and leaves the stack once, so the time complexity remains O(n) with O(n) auxiliary space. This approach highlights how trapped water forms between two boundaries and is often discussed when learning monotonic stacks.
Recommended for interviews: Interviewers typically expect the two-pointer solution. The dynamic programming version clearly demonstrates the core insight and is a good stepping stone, but the two-pointer technique proves you can reduce memory while maintaining linear time.
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.
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.
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) | When clarity matters and extra memory is acceptable |
| Two-Pointer Technique | O(n) | O(1) | Optimal interview solution with constant extra space |
| Monotonic Stack | O(n) | O(n) | Useful when learning stack-based boundary detection |
Trapping Rain Water - Google Interview Question - Leetcode 42 • NeetCode • 726,398 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