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
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:
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.
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).
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).
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:
height
array.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.