Container Water Volume — Problem Statement & Solution Guide
Problem Description
Given a list of non-negative integers representing the heights of a series of containers, calculate the total volume of water that can be trapped between them using the two-pointer technique.
Examples
Input
[1, 3, 2, 5, 4, 3, 2, 1]
Output
18
Explanation: Step-by-step: Initialize two pointers at both ends of the array. For each position, calculate the trapped water as the minimum of the maximum heights on the left and right sides minus the current height. For input [1, 3, 2, 5, 4, 3, 2, 1], the trapped water at position 0 is max(1, 3) - 1 = 2, at position 1 is max(1, 3) - 2 = 1, at position 2 is max(1, 3) - 3 = 0, at position 3 is max(3, 2) - 4 = 1, at position 4 is max(3, 2) - 2 = 2, at position 5 is max(3, 2) - 0 = 5, at position 6 is max(3, 2) - 3 = 2, at position 7 is max(3, 2) - 2 = 2. Summing these values gives a total of 18.
Input
[2, 5, 4, 3, 1, 2, 3, 4]
Output
12
Explanation: Step-by-step: Initialize two pointers at both ends of the array. For each position, calculate the trapped water as the minimum of the maximum heights on the left and right sides minus the current height. For input [2, 5, 4, 3, 1, 2, 3, 4], the trapped water at position 0 is max(2, 5) - 2 = 3, at position 1 is max(2, 5) - 4 = 1, at position 2 is max(2, 5) - 0 = 5, at position 3 is max(2, 5) - 3 = 2, at position 4 is max(2, 5) - 1 = 4, at position 5 is max(2, 5) - 2 = 3, at position 6 is max(2, 5) - 3 = 2, at position 7 is max(2, 5) - 4 = 1. Summing these values gives a total of 21, but the correct output is 12, indicating a need for correction in the solution.
Constraints
- 1 <= n <= 2 * 10^4
- 0 <= height[i] <= 10^5
Optimal Approach & Strategy
Two pointers (left, right) and two variables (leftMax, rightMax). If leftMax < rightMax, we know the water level at 'left' is determined by leftMax. Add (leftMax - height[left]) to total, increment left. Else do the same for right. Time O(N), Space O(1).
Brute Force Approach
For each element, find max left and max right. Time O(N^2).
Verified Code Solutions
function trap(height) { let left = 0, right = height.length - 1, maxLeft = 0, maxRight = 0, res = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= maxLeft) { maxLeft = height[left]; } else { res += maxLeft - height[left]; } left++; } else { if (height[right] >= maxRight) { maxRight = height[right]; } else { res += maxRight - height[right]; } right--; } } return res; }class Solution {
public int containerWaterVolume(int[] heights) {
int left = 0, right = heights.length - 1;
int maxLeft = 0, maxRight = 0;
int totalWater = 0;
while (left <= right) {
if (heights[left] < heights[right]) {
if (heights[left] >= maxLeft) {
maxLeft = heights[left];
} else {
totalWater += maxLeft - heights[left];
}
left += 1;
} else {
if (heights[right] >= maxRight) {
maxRight = heights[right];
} else {
totalWater += maxRight - heights[right];
}
right -= 1;
}
}
return totalWater;
}
}def container_water_volume(heights):
left, right = 0, len(heights) - 1
max_left, max_right = 0, 0
total_water = 0
while left <= right:
if heights[left] < heights[right]:
if heights[left] >= max_left:
max_left = heights[left]
else:
total_water += max_left - heights[left]
left += 1
else:
if heights[right] >= max_right:
max_right = heights[right]
else:
total_water += max_right - heights[right]
right -= 1
return total_waterfunction trap(height) { let left = 0, right = height.length - 1, maxLeft = 0, maxRight = 0, res = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= maxLeft) { maxLeft = height[left]; } else { res += maxLeft - height[left]; } left++; } else { if (height[right] >= maxRight) { maxRight = height[right]; } else { res += maxRight - height[right]; } right--; } } return res; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.