Container with Most Water
Given an array of non-negative integers where each value represents the height of a vertical line at that index on the x-axis, determine the maximum amount of water that can be trapped between any two lines.
A container is formed by selecting any two lines and the x-axis. The amount of water the container can hold is determined by the shorter of the two lines (as water cannot overflow the shorter one) and the distance between the two lines (which determines the width).
Your goal is to identify the pair of lines that together form a container with the maximum possible area (height × width).
Example 1
Input: [2, 9, 6, 2, 5, 3, 5, 10, 1] Output: 54
The maximum container is formed between the lines at index 1 (height = 9) and index 7 (height = 10). The shorter line determines the height (9), and the width between them is 6. So, the area is 9 × 6 = 54.
Example 2
Input: [1, 1] Output: 1
There is only one possible container between the two lines, both of height 1. The width is 1, so the area is 1 × 1 = 1.
Solution: Two-pointer approach
In this approach, we use the two-pointer technique to find the maximum area formed between two vertical lines. We start by placing one pointer at the beginning (left) and the other at the end (right) of the heights array. At each step, we calculate the area formed between the lines at these two positions:
area = min(height[left], height[right]) x (right - left).
We keep track of the maximum area encountered so far.
To explore other possible containers, we move the pointer pointing to the shorter line, since the area is limited by the shorter height.
If height[left] < height[right], we increment left.
Else, we decrement right. This strategy helps us skip over lines that cannot possibly lead to a larger area.
By gradually shrinking the width while trying to maximize the height, we efficiently examine all meaningful pairs in time. This approach avoids the brute-force comparison and yields an optimal solution using a single pass through the array.
def max_area(heights: list[int]) -> int:
max_area = 0
l, r = 0, len(heights)-1
while l < r:
curr = min(heights[l],heights[r]) * (r-l)
max_area = max(max_area,curr)
if heights[l] < heights[r]:
l += 1
else:
r -= 1
return max_areaTime Complexity: O(n). Two pointers (left and right) move inward toward each other once — total n-1 steps.
Space Complexity: O(1). Only a few variables are used (left, right, max_area, curr), no extra space proportional to input size.
Check out our lesson on the two-pointer approach to learn more about it and its applications!