An Interactive Visual Explainer
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: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1], Output: 6
// class Solution { ...
public int trap(int[] height) {
if (height == null || height.length == 0) return 0;
// Step 1: Initialization
int left = 0;
int right = height.length - 1;
int total = 0;
int leftMax = height[left];
int rightMax = height[right];
// Step 2: Loop until pointers meet
while(left < right){
// Step 3: Compare heights to find the bottleneck
if(height[left] < height[right]){
// Step 4: Process the left side
left++;
leftMax = Math.max(leftMax, height[left]);
if(leftMax - height[left] > 0){
total += leftMax - height[left];
}
}
else{
// Step 5: Process the right side
right--;
rightMax = Math.max(rightMax, height[right]);
if(rightMax - height[right] > 0){
total += rightMax - height[right];
}
}
}
// Step 6: Return the total trapped water
return total;
}
// }The amount of water trapped above any bar is determined by the height of the walls on its left and right. Specifically, it's limited by the shorter of the two highest walls (leftMax and rightMax) surrounding it.
We use a two-pointer approach, starting from the edges of the array. At each step, we process the side with the lower height, as it's the bottleneck for trapping water. We move the corresponding pointer inward, update the max height for that side, and add any trapped water to our total.
Left Pointer
-
Right Pointer
-
Left Max
-
Right Max
-
Added Water
-
Total Water
-
Hello, and welcome to the interactive explainer for LeetCode problem 42: Trapping Rain Water.
The problem asks us to calculate how much rainwater can be trapped by a series of bars of different heights. We're given these heights in an array.
The core idea, or intuition, behind solving this is to realize that the water trapped above any single bar is limited by the height of the walls around it. More specifically, it's the minimum of the highest wall to its left and the highest wall to its right. The water level can only rise to the height of the shorter of these two "boundary" walls.
To implement this efficiently, we use a two-pointer approach. We start with a 'left' pointer at the very beginning of the array and a 'right' pointer at the very end. We also keep track of the maximum height seen so far from the left, called 'leftMax', and from the right, 'rightMax'.
The algorithm proceeds in a loop as long as the left pointer is to the left of the right pointer. In each step, we check which wall is shorter: the one at the left pointer or the one at the right pointer.
If the height at the left pointer is less than the height at the right pointer, we focus on the left side. This is because we know the right wall is taller, so the trapping boundary on the left side is determined solely by the 'leftMax'. We first move the left pointer, then update the leftMax, and finally check if this new position can trap water. If the current bar is shorter than 'leftMax', it traps water. The amount is 'leftMax' minus the current bar's height.
Conversely, if the height at the right pointer is less than or equal to the height on the left, we focus on the right side. The logic is symmetrical. We move the right pointer, update 'rightMax', and then check for trapped water. If the current right bar is shorter than 'rightMax', it traps water equal to 'rightMax' minus its height.
This process repeats, adding up the trapped water at each step, until the pointers meet in the middle. The final accumulated total is our answer. This method is highly efficient, running in linear time, O(N), because we traverse the array just once, and it uses constant extra space, O(1), for our variables.