11. Container With Most Water
Model: qwen3.5:9b
Topics: Array,Two Pointers
FAANG asked: 1
Acceptance rate: 52.9%
Problem Breakdown
We are given an array height where each element represents a vertical line at index i. We need to find two lines that form a container with the x-axis such that it holds the maximum amount of water (area). The area is calculated as .
Inputs: An array height of non-negative integers.
Output: A single integer representing the maximum volume/area.
Constraints & Edge Cases:
- Array length is at least 2 (so a container can always be formed).
- Heights are up to , so area fits within standard integer types (Python handles large ints automatically anyway).
- Since we need the maximum possible volume, an brute force checking every pair is infeasible for . We strictly need a linear time solution.
Intuition
If I were to solve this naively, I would iterate through all pairs and calculate the area. That’s . With up to , that’s roughly 10 billion operations—way too slow for a typical interview time limit (usually ~1 second).
To optimize this, I need to discard pairs without checking them if they can’t possibly beat the current maximum. The area is limited by the shorter of the two lines and their distance apart (). If we start with the widest possible container (leftmost index 0, rightmost index ), any move inward reduces width. To potentially increase area after reducing width, we must find a taller line to compensate for that loss in distance. Crucially, moving the pointer pointing at the taller line will never help us get more water because the height is still capped by the shorter line on the other side; it just reduces our width unnecessarily. Therefore, I should always move the pointer associated with the shorter line inward to try and find a taller one that might increase the area.
Approach
I’ll use the Two Pointers technique:
- Initialize
leftat index 0 andrightat index . - Maintain a variable for
max_area. - While
left < right:- Calculate current area using multiplied by
(right - left). - Update
max_areaif the current is larger. - Move pointers: If
height[left] < height[right], incrementleft. Otherwise, decrementright. (If heights are equal, moving either works; I’ll move one to be consistent).
- Calculate current area using multiplied by
- Return
max_area.
Complexity Analysis
- Time: . The two pointers start at opposite ends and converge towards the center. In each iteration, we increment or decrement a pointer by exactly one step until they meet. We visit every element constant times.
- Space: . We only use variables for indices (
left,right) and counters (max_area). No extra data structures are allocated based on input size.
Solution
def maxArea(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
# Calculate current height (limited by the shorter line) and width
h_min = min(height[left], height[right])
w = right - left
# Update maximum area found so far
if h_min * w > max_area:
max_area = h_min * w
# Move the pointer of the shorter wall inward.
# Moving the taller one cannot increase the potential height, only decrease width.
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
Edge Cases Handled
- Minimum Length (): The loop runs once for indices 0 and 1, correctly calculating the single possible container.
- All Heights Equal:
minis always equal; pointers move inward one by one until they meet. Correctly calculates width height at each step (max will be found early or late depending on logic). - Zeros in Array: If a line has 0 height, the area becomes 0 immediately for that pair. The pointer moves past it to find non-zero heights if possible.
- Large Heights/Widths: Python handles arbitrary precision integers, so overflow is not an issue even with .