Largest Container
You are given an integer array height of length n, where each
element represents the height of a vertical line drawn at that index
on the x-axis. Together with the x-axis, two of these lines form a
container.
Find two lines that, together with the x-axis, form a container that holds the most water, and return the maximum amount of water it can hold. The container's width is the distance between the two chosen indices, and its height is the shorter of the two lines (water can't rise above the shorter wall).
Example 1
Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: The lines at index 1 (height 8) and index 8 (height 7)
form a container of width 7 and height min(8, 7) = 7, holding
7 * 7 = 49 units of water — the maximum possible.
Example 2
Input: height = [1, 1]
Output: 1
Constraints
2 <= height.length <= 10^50 <= height[i] <= 10^4
Start with two pointers at the widest possible container: left = 0
and right = n - 1. Compute the area for the current pair and track
the maximum seen so far. The key insight is that the container's
height is capped by the shorter of the two lines, so moving the
pointer at the taller line inward can never help — the width only
shrinks while the height stays capped by the same (or a shorter) line.
So we always move the pointer at the shorter line inward, hoping to
find a taller line that might offset the lost width. This greedy
choice is safe because every container we "skip" by moving the
shorter pointer would have been strictly worse than the one we just
measured.
A brute-force check of every pair of lines takes O(n^2) time. The two-pointer approach discards one candidate per step and never revisits it, giving O(n) time.
def largest_container(height: list[int]) -> int:
left, right = 0, len(height) - 1
best = 0
while left < right:
width = right - left
current_height = min(height[left], height[right])
best = max(best, width * current_height)
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
Complexity: O(n) time, since left and right together move at
most n steps before meeting. O(1) extra space.
Share this question