{x}
blog image

Trapping Rain Water

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 * 104
  • 0 <= height[i] <= 105

Solution Explanation: Trapping Rain Water

This problem asks to calculate the amount of rainwater trapped between bars of varying heights represented as an array. We'll explore a Dynamic Programming solution, which offers an efficient approach with a time complexity of O(n).

Approach:

The core idea is to pre-compute, for each bar, the maximum height of a bar to its left and the maximum height of a bar to its right. The amount of water trapped above a bar is determined by the minimum of its left and right maximums, minus the bar's height itself. Summing this up for all bars gives the total trapped water.

Algorithm:

  1. Initialization: Create two arrays, leftMax and rightMax, of the same size as the input height array. These will store the maximum heights encountered while traversing from left-to-right and right-to-left, respectively.

  2. Left-to-Right Pass: Iterate through height from left to right. For each index i, leftMax[i] will be the maximum of height[i] and leftMax[i-1] (the maximum seen so far).

  3. Right-to-Left Pass: Iterate through height from right to left. For each index i, rightMax[i] will be the maximum of height[i] and rightMax[i+1] (the maximum seen so far).

  4. Water Calculation: Iterate through height again. For each index i, the trapped water above this bar is min(leftMax[i], rightMax[i]) - height[i]. Sum these values to get the total trapped water.

Time and Space Complexity:

  • Time Complexity: O(n), as we perform three linear passes through the height array.
  • Space Complexity: O(n), due to the creation of leftMax and rightMax arrays.

Code Implementation (Python):

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:  # Handle empty input
            return 0
 
        leftMax = [0] * n
        rightMax = [0] * n
 
        leftMax[0] = height[0]
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])
 
        rightMax[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])
 
        totalWater = 0
        for i in range(n):
            totalWater += max(0, min(leftMax[i], rightMax[i]) - height[i])
 
        return totalWater

The other language implementations follow the same algorithmic steps, only differing in syntax and specific library functions used. For example, the max and min functions might have slightly different names or require different import statements depending on the language. The core logic, however, remains consistent across all implementations.