Calculate the trapped rainwater between bars in a given array.
Hard
Given an array of non-negative integers representing the heights of bars in a histogram, compute the amount of water that can be trapped between the bars after a rainfall.
The histogram is represented by an array where the width of each bar is 1. Water can be trapped if there are dips between taller bars that can hold the water.
Example
Input: [5, 0, 4] Output: 4 Explanation: Amount of water trapped is limited by shorter bar Input: [1, 1, 1] Output: 0 Explanation: No water can be trapped
Our solution processes the input array of heights by iterating through it while maintaining two pointers (left and right) and two variables (leftMax and rightMax) to track the maximum heights encountered from the left and right, respectively. We also use a variable (waterTrapped) to accumulate the total amount of water trapped.
For each element in the array:
- We compare the heights at the
leftandrightpointers. - If the height at the
leftpointer is less than the height at therightpointer:
- We move the
leftpointer to the right. - We update
leftMaxto be the maximum ofleftMaxand the current height atleft. - We calculate the water trapped above the current bar as
leftMax - height[left]and add this towaterTrapped.
- If the height at the
rightpointer is less than or equal to the height at theleftpointer:
- We move the
rightpointer to the left. - We update
rightMaxto be the maximum ofrightMaxand the current height atright. - We calculate the water trapped above the current bar as
rightMax - height[right]and add this towaterTrapped.
This process continues until the left pointer is greater than or equal to the right pointer.
The use of two pointers ensures that each element is processed efficiently, without the need for nested loops.
Time Complexity: The solution has a time complexity of O(n), where n is the number of elements in the array. This is because we iterate through the array once, moving the left and right pointers towards each other.
Space Complexity: The solution uses O(1) space, as it only requires a constant amount of extra space for the pointers and variables (left, right, leftMax, rightMax, and waterTrapped), regardless of the input size.
Related courses
