The Container With Most Water is a classic problem in algorithmic and computational thinking, that is often used to test the efficiency and problemsolving skills of developers.
The problem statement is as follows:
You are given a list of n
nonnegative integers, where each integer represents a vertical line at position i
with a height of height[i]
. The width of each vertical line is 1. Find two lines, which, together with the xaxis, forms a container that contains the most water.
In other words, you need to find two vertical lines in the list that create the largest possible rectangle with the xaxis. The area of the rectangle represents the amount of water that the container can hold.
For example, consider the following input list of heights
:
heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
The figure below shows the list of heights as vertical lines, and the largest container that can be formed by selecting the lines at indices 1
and 8
(highlighted in red). The area of this container is 49
(7×7).

 
 
  
   
   
    

1 8 6 2 5 4 8 3 7
In this case, selecting any other pair of lines would result in a smaller container.
Here are three approaches to solve the Container With Most Water problem, along with their pseudocode and explanations:
Approach 1: Brute Force
One simple approach to solving this problem is to use a brute force approach, which involves comparing every pair of lines and finding the one with the largest container.
max_area = 0
for i = 0 to n1 do
for j = i+1 to n1 do
area = (j  i) * min(height[i], height[j])
max_area = max(max_area, area)
return max_area
We use a nested loop to iterate over every possible pair of lines. For each pair of lines, we calculate the area of the container that they form by multiplying the difference in their indices by the minimum height between them.
We then update a variable max_area
with the maximum area we have found so far. Finally, we return max_area
.
The time complexity of this approach is O(n^2), because we visit each pair of lines exactly once.
Approach 2: TwoPointer Approach
A more efficient approach to solving this problem is to use the twopointer approach.
max_area = 0
left = 0
right = n1
while left < right do
area = (right  left) * min(height[left], height[right])
max_area = max(max_area, area)
if height[left] < height[right] then
left = left + 1
else
right = right  1
return max_area
We start with two pointers, one at the beginning of the list (left
) and one at the end (right
). We then calculate the area of the container formed by these two lines, and update max_area
with the maximum area we have found so far.
We then move the pointer with the smaller height inward (i.e., if height[left] < height[right]
, we move the left
pointer to the right, otherwise we move the right
pointer to the left). We repeat this process until the left
and right
pointers meet in the middle of the list.
The time complexity of this approach is O(n), since we visit each element in the list exactly once.
Approach 3: Using Stack
Another approach is to use a stack to keep track of the indices of the lines in the list. We can use the stack to keep track of the lines that might be useful in forming a larger container.
max_area = 0
stack = []
for i = 0 to n1 do
while stack is not empty and height[i] > height[stack.top()] do
top = stack.pop()
if stack is not empty then
width = i  stack.top()  1
else
width = i
area = width * height[top]
max_area = max(max_area, area)
stack.push(i)
while stack is not empty do
top = stack.pop()
if stack is not empty then
width = n  stack.top()  1
else
width = n
area = width * height[top]
max_area = max(max_area, area)
return max_area
We start by initializing an empty stack. We then iterate through the list of heights. For each height, we check if the height is greater than the height at the top of the stack. If it is, we pop the top element from the stack and calculate the area of the container that
The twopointer approach is generally considered to be the best approach for solving the Container With Most Water problem, because it has a time complexity of O(n), which is optimal for this problem.
The brute force approach has a time complexity of O(n^2), which is not efficient and will not work for large input sizes. The stackbased approach also has a time complexity of O(n), but it has higher constant factors and uses more memory than the twopointer approach.
In addition, the twopointer approach is simpler to understand and implement than the stackbased approach, and it does not require any additional data structures.
Therefore, the twopointer approach is the recommended approach for solving the Container With Most Water problem.
Container With Most Water: Java Solution
public int maxArea(int[] height) {
int maxArea = 0;
int left = 0;
int right = height.length  1;
while (left < right) {
int area = Math.min(height[left], height[right]) * (right  left);
maxArea = Math.max(maxArea, area);
if (height[left] < height[right]) {
left++;
} else {
right;
}
}
return maxArea;
}
Container With Most Water: JavaScript Solution
function maxArea(height) {
let maxArea = 0;
let left = 0;
let right = height.length  1;
while (left < right) {
const area = Math.min(height[left], height[right]) * (right  left);
maxArea = Math.max(maxArea, area);
if (height[left] < height[right]) {
left++;
} else {
right;
}
}
return maxArea;
}
Container With Most Water: Python Solution
def maxArea(height):
maxArea = 0
left = 0
right = len(height)  1
while left < right:
area = min(height[left], height[right]) * (right  left)
maxArea = max(maxArea, area)
if height[left] < height[right]:
left += 1
else:
right = 1
return maxArea
Container With Most Water: Ruby Solution
def max_area(height)
max_area = 0
left = 0
right = height.length  1
while left < right
area = [height[left], height[right]].min * (right  left)
max_area = [max_area, area].max
if height[left] < height[right]
left += 1
else
right = 1
end
end
return max_area
end
The general idea behind the twopointer approach is to use two pointers to explore the solution space in a more efficient way than brute force.
In the case of the Container With Most Water problem, we can use two pointers left
and right
to represent the two lines that form the container.
We start with left
at the beginning of the list and right
at the end of the list. We calculate the area of the container formed by these two lines using the formula:
area = (right  left) * min(height[left], height[right])
We then update a variable maxArea
with the maximum area we have found so far, and then move the pointer with the smaller height inward. We repeat this process until the pointers meet in the middle of the list.