Trapping Rain Water
Problem Statement
You are given an array non-negative integers height
which represent an elevation map. Each value height[i]
represents the height of a bar, which has a width of 1
.
Return the maximum area of water that can be trapped between the bars.
Example 1:
Input: height = [0,2,0,3,1,0,1,3,2,1]
Output: 9
Constraints:
1 <= height.length <= 1000
0 <= height[i] <= 1000
You should aim for a solution as good or better than O(n)
time and O(n)
space, where n
is the size of the input array.
Recommended Time and Space Complexity
You should aim for a solution as good or better than O(n)
time and O(n)
space, where n
is the size of the input array.
Hint 1
How can we determine the amount of water that can be trapped at a specific position in the array? Perhaps looking at the image might help clarify.
Hint 2
From the image, we can see that to calculate the amount of water trapped at a position, the greater element to the left l
and the greater element to the right r
of the current position are crucial. The formula for the trapped water at index i
is given by: min(height[l], height[r]) - height[i]
.
Hint 3
A brute force solution would involve iterating through the array with index i
, finding the greater elements to the left (l
) and right (r
) for each index, and then calculating the trapped water for that position. The total amount of trapped water would be the sum of the water trapped at each index. Finding l
and r
for each index involves repeated work, resulting in an O(n^2)
solution. Can you think of a more efficient approach? Maybe there is something that we can precompute and store in arrays.
Hint 4
We can store the prefix maximum in an array by iterating from left to right and the suffix maximum in another array by iterating from right to left. For example, in [1, 5, 2, 3, 4]
, for the element 3
, the prefix maximum is 5
, and the suffix maximum is 4
. Once these arrays are built, we can iterate through the array with index i
and calculate the total water trapped at each position using the formula: min(prefix[i], suffix[i]) - height[i]
.
Solution
Brute Force
def trap_brute_force(height: List[int]) -> int: if not height: return 0 n = len(height) res = 0
for i in range(n): left_max = right_max = height[i]
for j in range(i): left_max = max(left_max, height[j]) for j in range(i + 1, n): right_max = max(right_max, height[j])
res += min(left_max, right_max) - height[i] return res
Time complexity: O(n^2)
Space complexity: O(1)