Max Contained Volume — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Two Pointers and solve the Max Contained Volume problem optimally.
O(n)O(1)Problem Description
Given an array heights of non‑negative integers where each element denotes the height of a vertical line positioned at its index, determine the maximum amount of water that can be trapped between any two lines. The water volume for a pair of indices i and j (i<j) equals min(heights[i],heights[j]) * (j‑i). Return the largest possible volume.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Max Contained Volume"
WHY DOES IT MATTER?
The two‑pointer pattern transforms a quadratic search space into a linear sweep, which is essential for scaling algorithms that involve pairwise constraints on ordered data, such as container volume, max distance with constraints, or skyline problems.
OPTIMIZATION CHALLENGE
Recognizing that the limiting factor is the shorter line lets us discard it safely; this insight eliminates the need to examine every combination and reduces the complexity from O(n²) to O(n).
REAL-WORLD CONNECTION
Think of two flood barriers on a riverbank: moving the shorter barrier inward cannot increase the water held because the limiting height stays the same while the river width shrinks—mirroring the pointer movement in code.
During an interview, start by stating the greedy invariant (the shorter side is the bottleneck) and then walk through the pointer‑move rule; this demonstrates both problem understanding and algorithmic rigor.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem is a classic two‑pointer scenario often called the "Container With Most Water". The naive solution examines every pair of lines, computing min(height[i],height[j])*(j-i) which is O(n²) and quickly becomes infeasible for n up to 10⁵ or more. The optimal insight stems from the fact that the volume is limited by the shorter line of the pair; therefore, moving the taller line inward can never increase the area because the width shrinks while the limiting height does not improve. By initializing pointers at both ends and repeatedly discarding the shorter side, we guarantee that any future pair will have a smaller or equal height on that side, allowing us to explore all promising candidates in linear time. This greedy two‑pointer sweep preserves optimality while reducing both time and auxiliary space, making it the go‑to paradigm for any "max‑area between two indices" problem.
Interview Questions on This Problem
Q1How would you adapt the two‑pointer solution if the array could contain negative heights, representing lines that extend below a baseline?
Treat negative values as zero because water cannot be trapped below the baseline; the same two‑pointer logic applies after clamping negatives to zero, preserving O(n) time.
Q2A fintech platform stores daily price ranges as (low, high) pairs. How can you use the container‑with‑most‑water technique to find the two days that maximize the product of price spread and days apart?
Map each day to a single height equal to the spread (high‑low) and apply the two‑pointer algorithm on the spread array; the resulting max area corresponds to the desired product of spread and day distance.
Q3In a high‑growth startup, you need to compute the maximum bandwidth between any two servers given an array of link capacities. Explain why the two‑pointer approach is preferable to a segment‑tree solution here.
The two‑pointer method runs in O(n) with O(1) extra space, whereas a segment tree would require O(n log n) preprocessing and O(log n) per query; for a single global maximum, the linear scan is far simpler and faster.
Examples
Input
[1,8,6,2,5,4,8,3,7]
Output
49
Explanation: Choosing lines at indices 1 (height 8) and 8 (height 7) gives min(8,7)=7 and distance 7, volume 7*7=49, which is maximal.
Input
[4,3,2,1,4]
Output
16
Explanation: Lines at indices 0 and 4 have heights 4 and 4, distance 4, volume 4*4=16, which exceeds any other pair.
Input
[1,2,1]
Output
2
Explanation: The outermost lines (indices 0 and 2) give min(1,1)=1 and distance 2, volume 2; the inner pair yields volume 0, so 2 is maximum.
Constraints
- 1 <= heights.length <= 100000
- 0 <= heights[i] <= 10^9
Optimal Approach & Strategy
Use two pointers at the ends, calculate area, move the pointer at the shorter line inward, and repeat – O(n) time, O(1) space.
Brute Force Approach
Check every possible pair of indices, compute min(height[i],height[j])*(j-i), and keep the maximum – O(n²) time.
Code Solutions
/**
* @param {number[]} heights
* @return {number}
*/
var maxContainedVolume = function(heights) {
let left = 0;
let right = heights.length - 1;
let maxVolume = 0;
while (left < right) {
const width = right - left;
const height = Math.min(heights[left], heights[right]);
const volume = width * height;
maxVolume = Math.max(maxVolume, volume);
if (heights[left] < heights[right]) {
left++;
} else {
right--;
}
}
return maxVolume;
};
// Driver code
function main() {
const input = require('fs').readFileSync(0, 'utf8').trim().split('\n');
const n = parseInt(input[0]);
const heights = input[1].split(' ').map(Number);
console.log(maxContainedVolume(heights));
}
main();#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxContainedVolume(vector<int>& heights) {
int left = 0;
int right = heights.size() - 1;
int maxVolume = 0;
while (left < right) {
int width = right - left;
int height = min(heights[left], heights[right]);
int volume = width * height;
maxVolume = max(maxVolume, volume);
if (heights[left] < heights[right]) {
left++;
} else {
right--;
}
}
return maxVolume;
}
};
int main() {
int n;
cin >> n;
vector<int> heights(n);
for (int i = 0; i < n; ++i) {
cin >> heights[i];
}
Solution sol;
cout << sol.maxContainedVolume(heights) << endl;
return 0;
}import java.util.*;
import java.io.*;
public class Main {
public static int maxContainedVolume(int[] heights) {
int left = 0;
int right = heights.length - 1;
int maxVolume = 0;
while (left < right) {
int width = right - left;
int height = Math.min(heights[left], heights[right]);
int volume = width * height;
maxVolume = Math.max(maxVolume, volume);
if (heights[left] < heights[right]) {
left++;
} else {
right--;
}
}
return maxVolume;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
String[] parts = br.readLine().trim().split(" ");
int[] heights = new int[n];
for (int i = 0; i < n; i++) {
heights[i] = Integer.parseInt(parts[i]);
}
System.out.println(maxContainedVolume(heights));
}
}from typing import List
class Solution:
def maxContainedVolume(self, heights: List[int]) -> int:
left = 0
right = len(heights) - 1
max_volume = 0
while left < right:
width = right - left
height = min(heights[left], heights[right])
volume = width * height
max_volume = max(max_volume, volume)
if heights[left] < heights[right]:
left += 1
else:
right -= 1
return max_volume
if __name__ == "__main__":
import sys
input_data = sys.stdin.read().split()
n = int(input_data[0])
heights = list(map(int, input_data[1:1+n]))
solution = Solution()
print(solution.maxContainedVolume(heights))/**
* @param {number[]} heights
* @return {number}
*/
var maxContainedVolume = function(heights) {
let left = 0;
let right = heights.length - 1;
let maxVolume = 0;
while (left < right) {
const width = right - left;
const height = Math.min(heights[left], heights[right]);
const volume = width * height;
maxVolume = Math.max(maxVolume, volume);
if (heights[left] < heights[right]) {
left++;
} else {
right--;
}
}
return maxVolume;
};
// Driver code
function main() {
const input = require('fs').readFileSync(0, 'utf8').trim().split('\n');
const n = parseInt(input[0]);
const heights = input[1].split(' ').map(Number);
console.log(maxContainedVolume(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.