Max Contained Volume — Problem Statement & Solution Guide
Problem Description
Given a list of non-negative integers heights representing the heights of containers, find the maximum volume of liquid that can be stored between any two containers, where the volume is calculated as the minimum height of the two containers multiplied by the distance between their original indices.
Examples
Input
[1,8,6,2,5,4,8,3,7]
Output
49
Explanation: Step-by-step: with input [1,8,6,2,5,4,8,3,7], we calculate the volume between each pair of containers. The maximum volume is achieved between containers at indices 1 and 8, with heights 8 and 7 respectively. The distance between them is 8 - 1 = 7. The minimum height is min(8, 7) = 7. Therefore, the maximum volume is 7 * 7 = 49.
Input
[4,3,2,1,4]
Output
16
Explanation: Step-by-step: with input [4,3,2,1,4], we calculate the volume between each pair of containers. The maximum volume is achieved between containers at indices 0 and 4, with heights 4 and 4 respectively. The distance between them is 4 - 0 = 4. The minimum height is min(4, 4) = 4. Therefore, the maximum volume is 4 * 4 = 16.
Constraints
- 2 <= n <= 10^5
- 0 <= heights[i] <= 10^4
Optimal Approach & Strategy
Two pointers at start and end. Calculate area (min height * width). Move the pointer pointing to the shorter line inward, as moving the taller line can never increase the area. Time O(N), Space O(1).
Brute Force Approach
Calculate area for every possible pair of lines. Time O(N^2).
Verified Code Solutions
function maxArea(height) { let max = 0; let left = 0; let right = height.length - 1; while (left < right) { let h = Math.min(height[left], height[right]); let w = right - left; max = Math.max(max, h * w); if (height[left] < height[right]) { left++; } else { right--; } } return max; }class Solution { public: int maxArea(vector<int>& height) { int max = 0; int left = 0; int right = height.size() - 1; while (left < right) { int h = min(height[left], height[right]); int w = right - left; max = std::max(max, h * w); if (height[left] < height[right]) { left++; } else { right--; } } return max; } };class Solution { public int maxArea(int[] height) { int max = 0; int left = 0; int right = height.length - 1; while (left < right) { int h = Math.min(height[left], height[right]); int w = right - left; max = Math.max(max, h * w); if (height[left] < height[right]) { left++; } else { right--; } } return max; } }def maxArea(height): max_area = 0; left = 0; right = len(height) - 1; while left < right: h = min(height[left], height[right]); w = right - left; max_area = max(max_area, h * w); if height[left] < height[right]: left += 1; else: right -= 1; return max_areafunction maxArea(height) { let max = 0; let left = 0; let right = height.length - 1; while (left < right) { let h = Math.min(height[left], height[right]); let w = right - left; max = Math.max(max, h * w); if (height[left] < height[right]) { left++; } else { right--; } } return max; }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.