Container Water Volume — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Two Pointers and solve the Container Water Volume problem optimally.
O(n)O(1)Problem Description
Given an integer array heights where heights[i] denotes the elevation of a vertical wall at position i, compute the total amount of water that can be retained after raining. Water can be trapped only between two walls that are taller than the space between them. Return the sum of water units over all positions. Your algorithm must run in linear time and use constant extra space.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Container Water Volume"
WHY DOES IT MATTER?
The two‑pointer pattern transforms a quadratic search space into a linear one by leveraging problem‑specific monotonic constraints, a skill that recurs in many interview problems involving arrays, strings, and linked lists.
OPTIMIZATION CHALLENGE
Recognizing that the water level is limited by the shorter side and that moving the taller side cannot improve the current bound is the key insight that collapses O(n²) to O(n) while using only a few scalar variables.
REAL-WORLD CONNECTION
Think of two engineers scanning a pipeline from opposite ends, each stopping when they encounter a blockage; they only need to move the side with the weaker pressure, mirroring how the algorithm discards the shorter wall to find the optimal flow capacity.
During the interview, write the loop invariant explicitly: "All positions outside the current pointers have been processed and cannot contribute to a larger container" – this keeps you from over‑thinking pointer moves.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The classic "Container With Most Water" problem can be solved with a two‑pointer technique that exploits the monotonic property of the water level bound by the shorter wall. A naive scan that, for each left index, searches every possible right index to compute the area leads to O(n²) time, which quickly becomes infeasible for n in the order of 10⁵ or more. The optimal linear solution works by placing one pointer at the start and another at the end of the array, then moving the pointer that points to the shorter wall inward. This works because the amount of water that can be trapped is limited by the shorter side; moving the taller side cannot increase the water level, so we safely discard it. By continuously updating the maximum height seen so far from each side, we can compute the water contribution at each step in constant extra space, achieving O(n) time and O(1) space.
Interview Questions on This Problem
Q1How does the two‑pointer approach guarantee that we never miss a larger container when solving the water‑trapping problem?
Because at each step we discard the side with the smaller height; any container using that side as the limiting wall cannot be larger than the current water level, and a larger container would require a taller wall on that side, which we will encounter later as the pointer moves inward.
Q2Can you modify the two‑pointer solution to also return the indices of the walls that form the maximum water container?
Yes, maintain variables bestLeft and bestRight; whenever a larger area is computed, update them with the current left and right pointer positions before moving the pointers.
Q3Why does the two‑pointer method work for both the "Container With Most Water" and the "Trapping Rain Water" problems, even though their formulations differ?
Both problems rely on the fact that water level is bounded by the minimum of the two extreme heights; the two‑pointer technique incrementally narrows the search space while preserving the invariant that any better solution must involve the remaining pointers, allowing a single linear pass for both variants.
Examples
Input
[0,2,0,4,0,3,0,1]
Output
6
Explanation: Scanning from both ends, the highest wall to the left of each index and the highest wall to the right are determined. The water above index 2 is min(2,4)-0=2, above index 4 is min(4,3)-0=3, and above index 6 is min(4,1)-0=1. All other positions hold no water, giving a total of 6.
Input
[5,0,0,0,5]
Output
15
Explanation: The leftmost and rightmost walls are height 5. Every interior position can hold water up to height 5, so each of the three middle slots stores 5 units, for a total of 15.
Input
[1,2,3,4,5]
Output
0
Explanation: Heights never decrease, therefore no pair of walls creates a basin; each position’s water level equals its own height, resulting in zero trapped water.
Constraints
- 1 <= heights.length <= 100000
- 0 <= heights[i] <= 1000000000
- Solution must run in O(n) time and O(1) auxiliary space
Optimal Approach & Strategy
Use two pointers at the ends, track the max left and max right heights, and move the pointer with the smaller current height inward, adding water based on the difference between the max height and the current height; this runs in O(n) with O(1) extra space.
Brute Force Approach
For each index, scan all other indices to the right, compute the min of the two heights, subtract the current height, and keep the maximum; this is O(n²).
Code Solutions
function trapWater(heights) {
let left = 0, right = heights.length - 1;
let leftMax = 0, rightMax = 0;
let ans = 0;
while (left < right) {
if (heights[left] < heights[right]) {
if (heights[left] >= leftMax) leftMax = heights[left];
else ans += leftMax - heights[left];
left++;
} else {
if (heights[right] >= rightMax) rightMax = heights[right];
else ans += rightMax - heights[right];
right--;
}
}
return ans;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
const n = data[0];
const heights = data.slice(1,1+n);
console.log(trapWater(heights));
}
main();#include <bits/stdc++.h>
using namespace std;
long long trapWater(const vector<int>& h) {
int left = 0, right = (int)h.size() - 1;
int leftMax = 0, rightMax = 0;
long long ans = 0;
while (left < right) {
if (h[left] < h[right]) {
if (h[left] >= leftMax) leftMax = h[left];
else ans += (long long)leftMax - h[left];
++left;
} else {
if (h[right] >= rightMax) rightMax = h[right];
else ans += (long long)rightMax - h[right];
--right;
}
}
return ans;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
int n; if(!(cin>>n)) return 0; vector<int> h(n); for(int i=0;i<n;++i)cin>>h[i];
cout<<trapWater(h);
return 0;}
import java.io.*;
import java.util.*;
public class Main {
public static long trapWater(int[] h) {
int left = 0, right = h.length - 1;
int leftMax = 0, rightMax = 0;
long ans = 0;
while (left < right) {
if (h[left] < h[right]) {
if (h[left] >= leftMax) leftMax = h[left];
else ans += (long)leftMax - h[left];
left++;
} else {
if (h[right] >= rightMax) rightMax = h[right];
else ans += (long)rightMax - h[right];
right--;
}
}
return ans;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
int[] heights = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) heights[i] = Integer.parseInt(st.nextToken());
System.out.println(trapWater(heights));
}
}def trap_water(heights):
left, right = 0, len(heights) - 1
left_max = right_max = 0
ans = 0
while left < right:
if heights[left] < heights[right]:
if heights[left] >= left_max:
left_max = heights[left]
else:
ans += left_max - heights[left]
left += 1
else:
if heights[right] >= right_max:
right_max = heights[right]
else:
ans += right_max - heights[right]
right -= 1
return ans
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip().split()
if not data:
sys.exit()
n = int(data[0])
heights = list(map(int, data[1:1+n]))
print(trap_water(heights))function trapWater(heights) {
let left = 0, right = heights.length - 1;
let leftMax = 0, rightMax = 0;
let ans = 0;
while (left < right) {
if (heights[left] < heights[right]) {
if (heights[left] >= leftMax) leftMax = heights[left];
else ans += leftMax - heights[left];
left++;
} else {
if (heights[right] >= rightMax) rightMax = heights[right];
else ans += rightMax - heights[right];
right--;
}
}
return ans;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
const n = data[0];
const heights = data.slice(1,1+n);
console.log(trapWater(heights));
}
main();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.