Trapping Rain Water
HardPrompt
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] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward approach. For each bar, we find the highest bar on its left and its right. The amount of water that can be trapped above the current bar is the minimum of these two heights minus the current bar's height.
Algorithm
- Initialize a variable
totalWaterto 0. - Iterate through the
heightarray from the second element to the second-to-last element (indices1ton-2). Let the current index bei. - For each index
i:- Find the maximum height to the left of
i(includingi). Iterate from index0toiand findmaxLeft. - Find the maximum height to the right of
i(includingi). Iterate from indexiton-1and findmaxRight. - The water that can be trapped at index
iismin(maxLeft, maxRight) - height[i]. - If this value is positive, add it to
totalWater.
- Find the maximum height to the left of
- Return
totalWater.
Walkthrough
The core idea is that the water trapped at any position i is determined by the walls around it. Specifically, it's min(max_left_height, max_right_height) - height[i]. In this approach, we iterate through each bar of the elevation map (excluding the first and last, as they cannot trap water by themselves). For each bar at index i, we perform two additional scans: one to find the maximum height of all bars to its left (including itself), and another to find the maximum height of all bars to its right (including itself). The water level at position i is limited by the lower of these two maximums. We calculate the trapped water at i and add it to a running total.
class Solution { public int trap(int[] height) { if (height == null || height.length == 0) { return 0; } int n = height.length; int totalWater = 0; // Iterate through each bar from index 1 to n-2 for (int i = 1; i < n - 1; i++) { // Find the maximum height to the left of the current bar int maxLeft = 0; for (int j = i; j >= 0; j--) { maxLeft = Math.max(maxLeft, height[j]); } // Find the maximum height to the right of the current bar int maxRight = 0; for (int j = i; j < n; j++) { maxRight = Math.max(maxRight, height[j]); } // Water trapped at current bar is min(maxLeft, maxRight) - height[i] totalWater += Math.min(maxLeft, maxRight) - height[i]; } return totalWater; }}Complexity
Time
O(n^2)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space.
Cons
Highly inefficient due to repeated calculations for
maxLeftandmaxRightfor each bar.Likely to result in a 'Time Limit Exceeded' error on larger test cases.
This approach optimizes the brute-force method by pre-calculating the maximum heights. Instead of re-calculating the left and right maximums for each bar, we store them in two separate arrays. This reduces the overall time complexity from quadratic to linear.
Algorithm
- Create an array
leftMaxof sizen. - Fill
leftMax:leftMax[i]is the maximum height fromheight[0]toheight[i]. - Create an array
rightMaxof sizen. - Fill
rightMax:rightMax[i]is the maximum height fromheight[i]toheight[n-1]. - Initialize
totalWater = 0. - Iterate from
i = 0ton-1:- Add
min(leftMax[i], rightMax[i]) - height[i]tototalWater.
- Add
- Return
totalWater.
Walkthrough
The bottleneck in the brute-force approach is the repeated scanning to find maxLeft and maxRight. We can eliminate this redundancy by pre-computing these values for every index and storing them. We create two arrays, leftMax and rightMax. leftMax[i] will store the maximum height from index 0 to i, and rightMax[i] will store the maximum height from index i to n-1.
leftMax can be filled with a single pass from left to right. rightMax can be filled with a single pass from right to left.
Once these arrays are populated, we can iterate through the height array one more time. For each index i, the trapped water is simply min(leftMax[i], rightMax[i]) - height[i].
class Solution { public int trap(int[] height) { if (height == null || height.length == 0) { return 0; } int n = height.length; int totalWater = 0; int[] leftMax = new int[n]; leftMax[0] = height[0]; for (int i = 1; i < n; i++) { leftMax[i] = Math.max(height[i], leftMax[i - 1]); } int[] rightMax = new int[n]; rightMax[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; i--) { rightMax[i] = Math.max(height[i], rightMax[i + 1]); } for (int i = 0; i < n; i++) { totalWater += Math.min(leftMax[i], rightMax[i]) - height[i]; } return totalWater; }}Complexity
Time
O(n)
Space
O(n)
Trade-offs
Pros
Efficient linear time complexity.
Conceptually a clear improvement over brute force.
Cons
Requires extra space proportional to the input size for the two arrays.
This is the most optimal solution, achieving linear time complexity with constant space. It uses two pointers, one at the beginning and one at the end of the array, that move towards each other. This method avoids the need for extra storage arrays by processing the bars and calculating trapped water on the fly.
Algorithm
- Initialize
left = 0,right = n-1,leftMax = 0,rightMax = 0, andtotalWater = 0. - Loop while
left < right:- If
height[left] < height[right]:- If
height[left] >= leftMax, updateleftMax = height[left]. - Else, add
leftMax - height[left]tototalWater. - Increment
left.
- If
- Else (
height[right] <= height[left]):- If
height[right] >= rightMax, updaterightMax = height[right]. - Else, add
rightMax - height[right]tototalWater. - Decrement
right.
- If
- If
- Return
totalWater.
Walkthrough
This approach optimizes the space complexity of the DP solution. Instead of storing the leftMax and rightMax for all elements in arrays, we can compute the trapped water in a single pass using two pointers, left and right, starting at the two ends of the array. We also maintain leftMax and rightMax variables, which track the maximum height encountered so far from the left and right ends, respectively.
At each step, we compare height[left] and height[right].
If height[left] is smaller, we know that the water level at the left pointer is determined by leftMax, because rightMax is guaranteed to be at least height[right], which is greater than height[left]. We can then calculate the trapped water at left as leftMax - height[left] and move left one step to the right.
If height[right] is smaller or equal, a similar logic applies to the right pointer. We calculate trapped water as rightMax - height[right] and move right one step to the left.
The process continues until the pointers meet.
class Solution { public int trap(int[] height) { if (height == null || height.length == 0) { return 0; } int n = height.length; int left = 0, right = n - 1; int leftMax = 0, rightMax = 0; int totalWater = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= leftMax) { leftMax = height[left]; } else { totalWater += leftMax - height[left]; } left++; } else { if (height[right] >= rightMax) { rightMax = height[right]; } else { totalWater += rightMax - height[right]; } right--; } } return totalWater; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Optimal solution with O(n) time and O(1) space.
Efficient and elegant.
Cons
The logic can be slightly more complex to understand initially compared to the DP approach.
Solutions
Solution
public class Solution { public int Trap ( int [] height ) { int n = height . Length ; int [] left = new int [ n ]; int [] right = new int [ n ]; left [ 0 ] = height [ 0 ]; right [ n - 1 ] = height [ n - 1 ]; for ( int i = 1 ; i < n ; ++ i ) { left [ i ] = Math . Max ( left [ i - 1 ], height [ i ]); right [ n - i - 1 ] = Math . Max ( right [ n - i ], height [ n - i - 1 ]); } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { ans += Math . Min ( left [ i ], right [ i ]) - height [ i ]; } return ans ; } }public class Trapping_Rain_Water { public static void main ( String [] args ) { Trapping_Rain_Water out = new Trapping_Rain_Water (); Solution_local_minimum s = out . new Solution_local_minimum (); System . out . println ( s . trap ( new int []{ 5 , 2 , 1 , 2 , 1 , 5 })); } // The short board effect, the storage capacity is related to the short board of the bucket. // Find the longest slab in the height array, and then iterate from both ends to the long slab. When encountering a shorter one, find the storage capacity, and when encountering a longer one, update the edge. public class Solution_optimize { public int trap ( int [] height ) { if ( height == null || height . length == 0 ) return 0 ; int sum = 0 ; int maxind = 0 ; int max = Integer . MIN_VALUE ; // find max index for ( int i = 0 ; i < height . length ; i ++) { if ( height [ i ] > max ) { max = height [ i ]; maxind = i ; } } // left int leftmax = height [ 0 ]; for ( int i = 1 ; i < maxind ; i ++) { if ( leftmax < height [ i ]) { leftmax = height [ i ]; } sum += leftmax - height [ i ]; } // right int rightmax = height [ height . length - 1 ]; for ( int i = height . length - 2 ; i > maxind ; i --) { if ( rightmax < height [ i ]) { rightmax = height [ i ]; } sum += rightmax - height [ i ]; } return sum ; } } // local minimum solution is NOT doable. like [5,2,1,2,1,5], there are 2 local minimums with each holding 1 water // but they are just part of a global minimum class Solution_local_minimum { public int trap ( int [] height ) { // for each position, probe to left and right, find local minimum if ( height == null || height . length == 0 ) return 0 ; int sum = 0 ; int i = 1 ; // index=0 or index=length-1 will not be a local min, since nothing on its left to hold water while ( i < height . length - 1 ) { // only process local min index if ( height [ i ] < height [ i - 1 ] && height [ i ] < height [ i + 1 ]) { int left = i - 1 ; while ( left - 1 >= 0 && height [ left ] < height [ left - 1 ]) { left --; } int right = i + 1 ; while ( right + 1 < height . length && height [ right ] < height [ right + 1 ]) { right ++; } // now find its highest bar on both sides int lower = Math . min ( height [ left ], height [ right ]); // add up while ( left < right ) { if ( height [ left ] < lower ) { sum += lower - height [ left ]; } left ++; } // update pointer to search next local minimum i = right ; } else { i ++; } } return sum ; } } } ////// class Solution_notFindingMaxHeight { public int trap ( int [] height ) { if ( height == null || height . length == 0 ) return 0 ; int length = height . length ; int [] leftMax = new int [ length ]; // `leftMax` represents the maximum height in the subarray from the leftmost index to the current index int [] rightMax = new int [ length ]; // `rightMax` represents the maximum height in the subarray from the current index to the rightmost index leftMax [ 0 ] = height [ 0 ]; for ( int i = 1 ; i < length ; i ++) leftMax [ i ] = Math . max ( height [ i ], leftMax [ i - 1 ]); rightMax [ length - 1 ] = height [ length - 1 ]; for ( int i = length - 2 ; i >= 0 ; i --) rightMax [ i ] = Math . max ( height [ i ], rightMax [ i + 1 ]); int amount = 0 ; for ( int i = 0 ; i < length ; i ++) amount += Math . min ( leftMax [ i ], rightMax [ i ]) - height [ i ]; return amount ; } } ////// class Solution { public int trap ( int [] height ) { int n = height . length ; if ( n < 3 ) { return 0 ; } int [] lmx = new int [ n ]; int [] rmx = new int [ n ]; lmx [ 0 ] = height [ 0 ]; rmx [ n - 1 ] = height [ n - 1 ]; for ( int i = 1 ; i < n ; ++ i ) { lmx [ i ] = Math . max ( lmx [ i - 1 ], height [ i ]); rmx [ n - 1 - i ] = Math . max ( rmx [ n - i ], height [ n - i - 1 ]); } int res = 0 ; for ( int i = 0 ; i < n ; ++ i ) { res += Math . min ( lmx [ i ], rmx [ i ]) - height [ i ]; } return res ; } }class Solution: def trap(self, height: List[int]) -> int: n = len(height) if n < 3: return 0 lmx = [height[0]] * n rmx = [height[n - 1]] * n for i in range(1, n): lmx[i] = max(lmx[i - 1], height[i]) # i self compare rmx [ n - 1 - i ] = max ( rmx [ n - i ], height [ n - 1 - i ]) # no negative, worst is, min(left,right) is itself return sum ( min ( lmx [ i ], rmx [ i ]) - height [ i ] for i in range ( n ) ) ###### class Solution : # zip def trap ( self , height : List [ int ]) -> int : n = len ( height ) left = [ height [ 0 ]] * n right = [ height [ - 1 ]] * n for i in range ( 1 , n ): left [ i ] = max ( left [ i - 1 ], height [ i ]) right [ n - i - 1 ] = max ( right [ n - i ], height [ n - i - 1 ]) return sum ( min ( l , r ) - h for l , r , h in zip ( left , right , height )) ###### class Solution : # find the highest bar first def trap ( self , height : List [ int ]) -> int : if not height : return 0 total_water = 0 max_index = 0 max_height = float ( '-inf' ) # Find the index of the maximum height for i in range ( len ( height )): if height [ i ] > max_height : max_height = height [ i ] max_index = i # Calculate water trapped on the left side of the maximum height left_max = height [ 0 ] for i in range ( 1 , max_index ): if left_max < height [ i ]: left_max = height [ i ] total_water += left_max - height [ i ] # Calculate water trapped on the right side of the maximum height right_max = height [ - 1 ] for i in range ( len ( height ) - 2 , max_index , - 1 ): if right_max < height [ i ]: right_max = height [ i ] total_water += right_max - height [ i ] return total_water// OJ: https://leetcode.com/problems/trapping-rain-water/ // Time: O(N) // Space: O(N) class Solution { public: int trap ( vector < int >& A ) { int N = A . size (), ans = 0 ; vector < int > left ( N , 0 ), right ( N , 0 ); for ( int i = 1 ; i < N ; ++ i ) left [ i ] = max ( left [ i - 1 ], A [ i - 1 ]); for ( int i = N - 2 ; i >= 0 ; -- i ) right [ i ] = max ( right [ i + 1 ], A [ i + 1 ]); for ( int i = 1 ; i < N - 1 ; ++ i ) ans += max ( 0 , min ( left [ i ], right [ i ]) - A [ i ]); return ans ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.