Description:
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.
Examples:
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: 9Solution in Python:
To solve the problem of computing how much water can be trapped after raining, we can use an efficient approach with two pointers. This method allows us to compute the amount of trapped water in O(n) time with O(1) additional space.
Python
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = 0, 0
water_trapped = 0
# Use two pointers to traverse the height array
while left < right:
if height[left] < height[right]:
# Process the left side
if height[left] >= left_max:
left_max = height[left]
else:
water_trapped += left_max - height[left]
left += 1
else:
# Process the right side
if height[right] >= right_max:
right_max = height[right]
else:
water_trapped += right_max - height[right]
right -= 1
return water_trappedExplanation of the Code:
- Initial Checks:
- We first check if the
heightlist is empty. If it is, we return0because no water can be trapped.
- We first check if the
- Initialization:
- We initialize two pointers,
leftandright, to point to the start and end of theheightlist, respectively. - We also initialize two variables,
left_maxandright_max, to keep track of the maximum heights encountered so far from the left and right, respectively. water_trappedis initialized to0to accumulate the total amount of trapped water.
- We initialize two pointers,
- Two-pointer Traversal:
- We use a while loop to traverse the height array until the
leftpointer is less than therightpointer. - If the height at the
leftpointer is less than the height at therightpointer, we process the left side:- If the current height at the
leftpointer is greater than or equal toleft_max, we updateleft_maxto the current height. - Otherwise, we add the difference between
left_maxand the current height towater_trapped(since this difference represents the trapped water at this position). - We then move the
leftpointer one step to the right.
- If the current height at the
- If the height at the
rightpointer is less than or equal to the height at theleftpointer, we process the right side:- If the current height at the
rightpointer is greater than or equal toright_max, we updateright_maxto the current height. - Otherwise, we add the difference between
right_maxand the current height towater_trapped. - We then move the
rightpointer one step to the left.
- If the current height at the
- We use a while loop to traverse the height array until the
- Return the Result:
- After the traversal,
water_trappedcontains the total amount of trapped water, and we return it.
- After the traversal,
This approach ensures that we efficiently compute the amount of trapped water using a single pass through the height array and minimal additional space.
Solution in Javascript:
JavaScript
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
if (!height || height.length === 0) {
return 0;
}
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0;
let waterTrapped = 0;
// Use two pointers to traverse the height array
while (left < right) {
if (height[left] < height[right]) {
// Process the left side
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
waterTrapped += leftMax - height[left];
}
left++;
} else {
// Process the right side
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
waterTrapped += rightMax - height[right];
}
right--;
}
}
return waterTrapped;
};Solution in Java:
Java
class Solution {
public int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int waterTrapped = 0;
// Use two pointers to traverse the height array
while (left < right) {
if (height[left] < height[right]) {
// Process the left side
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
waterTrapped += leftMax - height[left];
}
left++;
} else {
// Process the right side
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
waterTrapped += rightMax - height[right];
}
right--;
}
}
return waterTrapped;
}
}Solution in C#:
C#
public class Solution {
public int Trap(int[] height) {
if (height == null || height.Length == 0) {
return 0;
}
int left = 0, right = height.Length - 1;
int leftMax = 0, rightMax = 0;
int waterTrapped = 0;
// Use two pointers to traverse the height array
while (left < right) {
if (height[left] < height[right]) {
// Process the left side
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
waterTrapped += leftMax - height[left];
}
left++;
} else {
// Process the right side
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
waterTrapped += rightMax - height[right];
}
right--;
}
}
return waterTrapped;
}
}