Trapping Rain Water
Given an array of non-negative integers representing the height of bars in a histogram, find the amount of water that can be trapped between the bars.
Constraints:
- 1 <= height.length <= 2 * 10^4
- 0 <= height[i] <= 10^5
Examples:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map is represented as an array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of water (blue section) are being trapped.
Solutions
Two Pointers
We use two pointers, one at the beginning and one at the end of the array. We keep track of the maximum height of the bars on the left and right sides. We move the pointer that is pointing to the shorter bar towards the other end. If the height of the bar at the current position is greater than or equal to the maximum height on the same side, we update the maximum height. Otherwise, we add the difference between the maximum height and the height of the current bar to the result.
def trap(height):
left, right, max_left, max_right, res = 0, len(height) - 1, 0, 0, 0; while left <= right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]; else:
res += max_left - height[left]; left += 1; else:
if height[right] >= max_right:
max_right = height[right]; else:
res += max_right - height[right]; right -= 1; return resFollow-up:
What if the bars are not of equal width?
