Container With Most Water - A Greedy Two-Pointer Strategy (Java)

We've explored various array problems, including the nuances of "Trapping Rain Water." Today, we tackle another classic: "Container With Most Water" (LeetCode #11). While both involve water and bars, this problem has a distinct goal and an elegant solution using the Two-Pointer pattern combined with a greedy strategy.
Understanding the Problem:
We are given an integer array heights
, where heights[i]
represents the height of the i
-th bar. Each bar has a width of 1.
Our task is to choose any two bars to form a container and return the maximum amount of water that this container can store. The container's base will be the distance between the two chosen bars, and its height will be limited by the shorter of the two bars.
Formula for Area: Area = min(height[left_bar], height[right_bar]) * (right_bar_index - left_bar_index)
Example:
Input:
heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output:
49
Let's visualize the example (the bars at index 1 (height 8) and index 6 (height 8) form the largest container):
# #
# # # #
# # # # # #
# # # # # # # #
# # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # #
_ _ _ _ _ _ _ _ _ _ _ _
1 8 6 2 5 4 8 3 7 (Heights)
My Thought Process & Approach (Two-Pointer Greedy Strategy):
A naive approach might be to try every possible pair of bars, calculate the area, and find the maximum. This would involve nested loops, leading to an O(N^2) time complexity, which is too slow for larger inputs.
The problem's structure (finding a pair, maximizing something based on their relative positions) combined with the desire for efficiency often points to the Two-Pointer pattern. But how do we move the pointers to guarantee we find the optimal solution? This is where the greedy part comes in.
Here's the core idea:
Initialize Pointers:
Set a
left
pointer (i
) at the beginning of the array (index 0).Set a
right
pointer (j
) at the end of the array (indexheights.length - 1
).Initialize
ans
to 0 to store the maximum area found so far.
Iterate and Adjust (The Greedy Move):
While
i
is less thanj
(meaning our pointers haven't crossed):Calculate the
area
of the container formed byheights[i]
andheights[j]
. This isMath.min(heights[i], heights[j]) * (j - i)
.Update
ans
with the maximum of its current value andarea
.Now, for the crucial part: Which pointer do we move?
The width (
j - i
) will always decrease as we move pointers inward. To maximize the area, we need to maximizemin(heights[i], heights[j])
.If
heights[i]
is less thanheights[j]
, thenheights[i]
is the limiting factor for the current container's height. To potentially find a larger area, we must try to find a taller left wall. Movingj
inwards would only decrease the width and still be limited by the sameheights[i]
. So, we incrementi
.If
heights[j]
is less thanheights[i]
, thenheights[j]
is the limiting factor. We decrementj
to search for a potentially taller right wall.If
heights[i]
andheights[j]
are equal, both are limiting. Moving either (or both) will explore new possibilities. Moving both is a safe and common practice to reduce search space efficiently.
Return: After the pointers cross (
i >= j
), the loop terminates, andans
will hold the maximum water that could be contained.
This greedy two-pointer strategy ensures that at each step, we're making the locally optimal choice that will lead to the globally optimal solution. We avoid configurations that we know cannot be better than our current best.
Java Code Implementation:
class Solution {
public int maxArea(int[] heights) {
int i =0;
int j = heights.length-1;
int ans = 0;
while(i<j){
int area = Math.min(heights[i],heights[j])*(j-i);
if(heights[i]>heights[j]){
j--;
}
else if(heights[i]<heights[j]){
i++;
}
else{
i++;j--;
}
ans = Math.max(ans,area);
}
return ans;
}
}
Time and Space Complexity Analysis:
Time Complexity: O(N)
The
while
loop iterates as thei
pointer moves towardsj
, orj
moves towardsi
. In each step, at least one pointer moves inwards.In the worst case, the pointers will traverse the entire array once.
Each operation inside the loop (comparison,
Math.min
,Math.max
, arithmetic) is constant time.Therefore, the total time complexity is O(N). This is optimal as you need to at least look at a significant portion of the bars.
Space Complexity: O(1)
We only use a few constant-space variables (
i
,j
,area
,ans
).No auxiliary data structures are used whose size depends on the input
N
.This makes it a highly space-efficient solution.
Subscribe to my newsletter
Read articles from Kaushal Maurya directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
