Trapping Rain Water

HARD

Description

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.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

Approaches

Checkout 3 different approaches to solve Trapping Rain Water. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

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 totalWater to 0.
Iterate through the height array from the second element to the second-to-last element (indices 1 to n-2). Let the current index be i.
For each index i:
- Find the maximum height to the left of i (including i). Iterate from index 0 to i and find maxLeft.
- Find the maximum height to the right of i (including i). Iterate from index i to n-1 and find maxRight.
- The water that can be trapped at index i is min(maxLeft, maxRight) - height[i].
- If this value is positive, add it to totalWater.
Return totalWater.

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 Analysis

Time Complexity: O(n^2)Space Complexity: O(1)

Pros and Cons

Pros:

Simple to understand and implement.
Uses constant extra space.

Cons:

Highly inefficient due to repeated calculations for maxLeft and maxRight for each bar.
Likely to result in a 'Time Limit Exceeded' error on larger test cases.

Code Solutions

Checking out 4 solutions in different languages for Trapping Rain Water. Click on different languages to view the code.

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 ; } }

Video Solution

Watch the video walkthrough for Trapping Rain Water

Patterns:

Two PointersDynamic Programming

Data Structures:

ArrayStackMonotonic Stack

Companies:

Accolite |Adobe |Airbnb |Amazon |