Container With Most Water solution and explanation
TCS
Infosys
9 more videos on this problem
Container with Most Water - Leetcode 11 - PythonNeetCode · 12:37 · 554K views
Container with Most Water Problem | Brute & Optimal Solution | Two Pointer Approach - Leetcode 11Apna College · 32:00 · 362K views
Container With Maximum Water (LeetCode 11) | Full Solution with Visuals | Study AlgorithmsNikhil Lohia · 12:42 · 62K views
LeetCode Container With Most Water Explained - JavaNick White · 5:40 · 62K views
Container With Most Water | Detailed | With Dry Runs | Leetcode 11 | codestorywithMIKcodestorywithMIK · 18:38 · 34K views
Container With Most Water - Leetcode 11 - 2 Pointers (Python)Greg Hogg · 6:48 · 30K views
Container With Most Water | Live Coding with Explanation | Leetcode - 11Algorithms Made Easy · 4:58 · 25K views
11. Container With Most Water || LEETCODE || code + intuitionCode with Alisha · 8:01 · 17K views
LeetCode 11: Container With Most WaterAbstracted Away · 7:02 · 13K views
Container with most water | Leetcode #11Techdose · 12:33 · 6K views
The problem
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1] Output: 1
Constraints:
n == height.length2 <= n <= 1050 <= height[i] <= 104
Approach overview
Problem Overview: You get an array height where each value represents the height of a vertical line. Pick two lines that, together with the x-axis, form a container holding the maximum possible water. The container area is determined by the shorter line and the distance between the two indices.
Approach 1: Brute Force (O(n2) time, O(1) space)
The straightforward approach checks every pair of lines. For each pair (i, j), compute the container area using min(height[i], height[j]) * (j - i). Iterate with two nested loops and keep track of the maximum area seen so far. This works because it evaluates all possible containers, guaranteeing the correct result. The downside is the quadratic runtime since there are n(n-1)/2 pairs to examine. This approach mainly helps build intuition for the problem before applying optimizations with techniques like two pointers.
Approach 2: Two Pointers Technique (O(n) time, O(1) space)
The optimal solution uses two pointers starting at opposite ends of the array. One pointer begins at index 0 and the other at n-1. At each step, compute the current area using the width between the pointers and the smaller height. The key insight: the container height is limited by the shorter line, so moving the taller pointer cannot increase the area. Move the pointer pointing to the shorter line inward and recompute the area. This greedy decision removes impossible candidates while still exploring all potentially better containers.
This method works because reducing width is unavoidable when moving pointers, so the only chance to increase area is by finding a taller boundary. By always discarding the shorter wall, the algorithm systematically searches for a better height while keeping the widest possible distance early in the process. The result is a single linear scan of the array using the classic array traversal pattern combined with a greedy elimination strategy.
Recommended for interviews: Interviewers expect the Two Pointers solution. The brute force method shows you understand how the area formula works and can reason about all possibilities. The optimized approach demonstrates pattern recognition and algorithmic efficiency by reducing the search from O(n2) to O(n). Many array optimization problems follow the same pattern of shrinking the search space from both ends.
Approach 1: Approach 1: Two Pointers Technique
The two pointers approach efficiently searches for the maximum area by starting with the widest possible container and gradually narrowing it:
- Initialize two pointers, one at the beginning (left) and one at the end (right) of the array.
- Calculate the area using the current height at left and right pointers, and update the maximum area when a larger one is found.
- Move the pointer pointing to the shorter line inward, as this might lead to a taller container edge and potentially a larger area.
- Continue this process until the two pointers meet.
This approach works due to the observation that the area is limited by the shorter line, so the only way to get a larger area is to find a taller line.
class Solution:
def maxArea(self, height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
h = min(height[left], height[right])
max_area = max(max_area, h * (right - left))
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
if __name__ == "__main__":
sol = Solution()
print(sol.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))public class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
int h = Math.min(height[left], height[right]);
maxArea = Math.max(maxArea, h * (right - left));
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] height = {1,8,6,2,5,4,8,3,7};
System.out.println("Max area: " + solution.maxArea(height));
}
}#include <iostream>
#include <vector>
int maxArea(std::vector<int>& height) {
int left = 0, right = height.size() - 1;
int max_area = 0;
while (left < right) {
int h = std::min(height[left], height[right]);
max_area = std::max(max_area, h * (right - left));
height[left] < height[right] ? left++ : right--;
}
return max_area;
}
int main() {
std::vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
std::cout << "Max area: " << maxArea(height) << std::endl;
return 0;
}function maxArea(height) {
let left = 0;
let right = height.length - 1;
let maxArea = 0;
while (left < right) {
const h = Math.min(height[left], height[right]);
maxArea = Math.max(maxArea, h * (right - left));
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]));#include <stdio.h>
int maxArea(int* height, int heightSize) {
int left = 0, right = heightSize - 1;
int max_area = 0;
while (left < right) {
int h = height[left] < height[right] ? height[left] : height[right];
int current_area = h * (right - left);
if (current_area > max_area) max_area = current_area;
if (height[left] < height[right]) left++;
else right--;
}
return max_area;
}
int main() {
int height[] = {1,8,6,2,5,4,8,3,7};
int result = maxArea(height, sizeof(height) / sizeof(height[0]));
printf("Max area: %d\n", result);
return 0;
}using System;
public class Solution
{
public int MaxArea(int[] height)
{
int left = 0, right = height.Length - 1;
int maxArea = 0;
while (left < right)
{
int h = Math.Min(height[left], height[right]);
maxArea = Math.Max(maxArea, h * (right - left));
if (height[left] < height[right])
{
left++;
}
else
{
right--;
}
}
return maxArea;
}
public static void Main(string[] args)
{
Solution solution = new Solution();
int[] height = {1,8,6,2,5,4,8,3,7};
Console.WriteLine("Max area: " + solution.MaxArea(height));
}
}This Python solution efficiently finds the maximum water container area using the two-pointer technique. The while loop continues until the pointers meet, and the max_area is updated based on the minimum height between two pointers.
Time Complexity: O(n), where n is the number of heights.
Space Complexity: O(1) since only a small amount of space is used irrespective of input size.
Approach 2: Approach 2: Brute Force
Although not optimal for large inputs, the brute force approach explores every possible pair of lines to find the maximum container area:
- Iterate through each line starting from the first.
- For every line, consider all subsequent lines as a potential pair to form a container.
- Calculate the area for each pair, and keep track of the maximum area encountered.
- This method ensures all possible pairs are considered, leading to the correct result.
However, the complexity of this approach makes it unsuitable for large datasets due to its quadratic time complexity.
class Solution:
def maxArea(self, height):
max_area = 0
for i in range(len(height) - 1):
for j in range(i + 1, len(height)):
h = min(height[i], height[j])
max_area = max(max_area, h * (j - i))
return max_area
if __name__ == "__main__":
sol = Solution()
print(sol.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))public class Solution {
public int maxArea(int[] height) {
int maxArea = 0;
for (int i = 0; i < height.length - 1; i++) {
for (int j = i + 1; j < height.length; j++) {
int h = Math.min(height[i], height[j]);
maxArea = Math.max(maxArea, h * (j - i));
}
}
return maxArea;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] height = {1,8,6,2,5,4,8,3,7};
System.out.println("Max area: " + solution.maxArea(height));
}
}#include <iostream>
#include <vector>
int maxArea(std::vector<int>& height) {
int max_area = 0;
for (size_t i = 0; i < height.size() - 1; ++i) {
for (size_t j = i + 1; j < height.size(); ++j) {
int h = std::min(height[i], height[j]);
max_area = std::max(max_area, h * (j - i));
}
}
return max_area;
}
int main() {
std::vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
std::cout << "Max area: " << maxArea(height) << std::endl;
return 0;
}function maxArea(height) {
let maxArea = 0;
for (let i = 0; i < height.length - 1; i++) {
for (let j = i + 1; j < height.length; j++) {
const h = Math.min(height[i], height[j]);
maxArea = Math.max(maxArea, h * (j - i));
}
}
return maxArea;
}
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]));#include <stdio.h>
int maxArea(int* height, int heightSize) {
int max_area = 0;
for (int i = 0; i < heightSize - 1; i++) {
for (int j = i + 1; j < heightSize; j++) {
int h = height[i] < height[j] ? height[i] : height[j];
int area = h * (j - i);
if (area > max_area) max_area = area;
}
}
return max_area;
}
int main() {
int height[] = {1,8,6,2,5,4,8,3,7};
int result = maxArea(height, sizeof(height) / sizeof(height[0]));
printf("Max area: %d\n", result);
return 0;
}using System;
public class Solution
{
public int MaxArea(int[] height)
{
int maxArea = 0;
for (int i = 0; i < height.Length - 1; i++)
{
for (int j = i + 1; j < height.Length; j++)
{
int h = Math.Min(height[i], height[j]);
maxArea = Math.Max(maxArea, h * (j - i));
}
}
return maxArea;
}
public static void Main(string[] args)
{
Solution solution = new Solution();
int[] height = {1,8,6,2,5,4,8,3,7};
Console.WriteLine("Max area: " + solution.MaxArea(height));
}
}This brute force Python method calculates the maximum container area by evaluating all pairs of lines' possible areas and selecting the maximum.
Time Complexity: O(n^2) due to evaluating all line pairs.
Space Complexity: O(1), only a constant amount of space used.
Approach 3: Two Pointers
We use two pointers l and r to point to the left and right ends of the array, respectively, i.e., l = 0 and r = n - 1, where n is the length of the array.
Next, we use a variable ans to record the maximum capacity of the container, initially set to 0.
Then, we start a loop. In each iteration, we calculate the current capacity of the container, i.e., min(height[l], height[r]) times (r - l), and compare it with ans, assigning the larger value to ans. Then, we compare the values of height[l] and height[r]. If height[l] < height[r], moving the r pointer will not improve the result because the height of the container is determined by the shorter vertical line, so we move the l pointer. Otherwise, we move the r pointer.
After the iteration, we return ans.
The time complexity is O(n), where n is the length of the array height. The space complexity is O(1).
function maxArea(height: number[]): number {
let [l, r] = [0, height.length - 1];
let ans = 0;
while (l < r) {
const t = Math.min(height[l], height[r]) * (r - l);
ans = Math.max(ans, t);
if (height[l] < height[r]) {
++l;
} else {
--r;
}
}
return ans;
}func maxArea(height []int) (ans int) {
l, r := 0, len(height)-1
for l < r {
t := min(height[l], height[r]) * (r - l)
ans = max(ans, t)
if height[l] < height[r] {
l++
} else {
r--
}
}
return
}impl Solution {
pub fn max_area(height: Vec<i32>) -> i32 {
let mut l = 0;
let mut r = height.len() - 1;
let mut ans = 0;
while l < r {
ans = ans.max(height[l].min(height[r]) * ((r - l) as i32));
if height[l] < height[r] {
l += 1;
} else {
r -= 1;
}
}
ans
}
}class Solution {
/**
* @param Integer[] $height
* @return Integer
*/
function maxArea($height) {
$l = 0;
$r = count($height) - 1;
$ans = 0;
while ($l < $r) {
$t = min($height[$l], $height[$r]) * ($r - $l);
$ans = max($ans, $t);
if ($height[$l] < $height[$r]) {
++$l;
} else {
--$r;
}
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two Pointers Technique | Time Complexity: O(n), where n is the number of heights. |
| Approach 2: Brute Force | Time Complexity: O(n^2) due to evaluating all line pairs. |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Useful for understanding the area calculation and verifying logic on small inputs |
| Two Pointers Technique | O(n) | O(1) | Optimal solution for large arrays; standard interview approach for this problem |
Frequently asked questions
Is Container With Most Water easy or hard?
Container With Most Water is classified as a Medium problem. The brute force solution is straightforward, but recognizing the two-pointer optimization requires understanding how to eliminate unnecessary pairs while preserving the possibility of finding a larger area.
Container With Most Water Python/Java solution
Python and Java implementations typically follow the same two-pointer logic: initialize left and right indices, compute area using min(height[left], height[right]), update the maximum, and move the pointer with the smaller height. The loop continues until the pointers meet, achieving O(n) runtime.
How to solve Container With Most Water in O(n)?
Place two pointers at the leftmost and rightmost indices of the height array. Calculate the area using the shorter height and the width between pointers. Move the pointer pointing to the smaller height inward and repeat until the pointers meet. This strategy works because only a taller boundary can increase the possible container height.
What is the best approach for Container With Most Water?
The best approach uses the Two Pointers technique. Start with one pointer at the beginning of the array and another at the end, compute the container area, then move the pointer with the smaller height inward. This greedy rule ensures all useful candidates are considered while scanning the array once, giving O(n) time and O(1) space complexity.
Is Container With Most Water asked at Google/Amazon/Meta?
Container With Most Water is a common interview problem at companies like Google, Amazon, Meta, and Microsoft. It tests recognition of the two-pointer pattern, reasoning about greedy decisions, and the ability to reduce a brute force search space to a linear scan.
What data structure is used in Container With Most Water?
The problem primarily uses an array along with the two pointers technique. No additional data structures such as hash maps or stacks are required. The algorithm operates directly on the array indices while maintaining constant extra memory.
What is the time complexity of Container With Most Water?
The optimal solution runs in O(n) time using the two pointers technique because each pointer moves at most once across the array. The brute force method checks every pair of lines and takes O(n^2) time. Both approaches use O(1) additional space.