Container With Most Water
Problem
Given an array of integers height representing vertical lines, return the maximum amount of water a container can store formed between two lines and the x-axis.
- 2 ≤ height.length ≤ 10⁵
- 0 ≤ height[i] ≤ 10⁴
Example
height = [1,8,6,2,5,4,8,3,7]49Starting with pointers at the outermost lines (indices 0 and 8), the container width is 8 and the limiting height is min(1,7) = 1, so area = 8 * 1 = 8. Since height[0] < height[8], move left pointer inward to index 1. Now width is 7, limiting height min(8,7) = 7, area = 49, which is larger. Continue moving pointers inward, always moving the pointer at the shorter line, updating the max area. The maximum area found is 49.
Approach
Straightforward Solution
A brute-force approach checks all pairs of lines, calculating area for each, resulting in O(n^2) time complexity, which is too slow for large inputs.
Core Observation
The container's area is determined by the width between two lines and the height of the shorter line. Maximizing area requires balancing these two factors.
Path to Optimal
Starting with the widest container (outermost lines), the key insight is that moving the pointer at the taller line inward cannot increase area because width decreases and height is limited by the shorter line. Moving the pointer at the shorter line inward may find a taller line that compensates for the reduced width, potentially increasing area. This greedy approach reduces the search space linearly.
Optimal Approach
Use two pointers at the start and end of the array. Calculate area, update max area, then move the pointer at the shorter line inward. Repeat until pointers meet. This guarantees O(n) time and O(1) space.
Time
O(n)
Each pointer moves inward at most n times, resulting in a single pass through the array.
Space
O(1)
Only a fixed number of variables are used regardless of input size.
Pattern Spotlight
Two Pointers (Greedy Contraction)
The logic of any optimal Two Pointers solution lies in finding the condition that allows you to permanently discard one end of the search space by moving the pointer that is the current 'limiting factor' to the solution.
Solution
| 1 | class Solution:
|
| 2 | def maxArea(self, height: list[int]) -> int:
|
| 3 | l, r = 0, len(height) - 1
|
| 4 | max_area = 0
|
| 5 |
|
| 6 | while l < r:
|
| 7 | area = (r - l) * min(height[l], height[r])
|
| 8 | max_area = max(max_area, area)
|
| 9 |
|
| 10 | if height[l] < height[r]:
|
| 11 | l += 1
|
| 12 | else:
|
| 13 | r -= 1
|
| 14 |
|
| 15 | return max_area |
| 1 | class Solution { |
| 2 | public int maxArea(int[] height) { |
| 3 | int l = 0; |
| 4 | int r = height.length - 1; |
| 5 | int maxArea = 0; |
| 6 | |
| 7 | while (l < r) { |
| 8 | int area = (r - l) * Math.min(height[l], height[r]); |
| 9 | maxArea = Math.max(maxArea, area); |
| 10 | |
| 11 | if (height[l] < height[r]) { |
| 12 | l++; |
| 13 | } else { |
| 14 | r--; |
| 15 | } |
| 16 | } |
| 17 | |
| 18 | return maxArea; |
| 19 | } |
| 20 | } |
Step-by-Step Solution
Initialize Two Pointers and Maximum Area
| 3 | l, r = 0, len(height) - 1
|
| 4 | max_area = 0
|
Objective
To set up pointers at both ends of the array and initialize the variable to track the maximum area found.
Key Insight
Starting with pointers at the extreme ends ensures the widest possible container, providing a baseline for comparison. Initializing max_area to zero prepares to track the best solution found during iteration.
Interview Quick-Check
Core Logic
Pointers at indices 0 and len(height) - 1 represent the widest container possible at the start.
State & Boundaries
Initialize max_area to zero to correctly handle cases where all heights might be zero.
Iteratively Calculate Area and Move Limiting Pointer
| 6 | while l < r:
|
| 7 | area = (r - l) * min(height[l], height[r])
|
| 8 | max_area = max(max_area, area)
|
| 10 | if height[l] < height[r]:
|
| 11 | l += 1
|
| 12 | else:
|
| 13 | r -= 1
|
Objective
To calculate the container area at the current pointers, update the maximum area, and move the pointer at the shorter line inward to explore potentially larger areas.
Key Insight
The area is the product of the width (distance between pointers) and the height of the shorter line. Moving the pointer at the shorter line inward is a greedy choice that discards suboptimal containers and focuses the search on potentially better candidates, ensuring linear time complexity.
Interview Quick-Check
Core Logic
Calculate area using current pointers, update max_area if larger, then move the pointer at the shorter height inward to explore new containers.
State & Boundaries
The loop continues while left pointer is less than right pointer, ensuring valid container width.
Common Pitfalls & Bugs
Moving the pointer at the taller line instead of the shorter line can miss the optimal solution.
Complexity
Each pointer moves inward at most n times, resulting in O(n) time complexity.
Return the Maximum Area Found
| 15 | return max_area |
Objective
To return the maximum container area found after all pointer movements are complete.
Key Insight
After the pointers meet, all possible containers have been considered under the greedy strategy, so max_area holds the optimal solution.
Interview Quick-Check
Core Logic
Returning max_area after the loop ensures the final answer reflects the largest container found.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
l += 1Move the left pointer inward if its line is shorter.
This is the critical greedy step: moving the pointer at the shorter line is the only move that can potentially increase the container area because the area is limited by the shorter line; moving the taller line's pointer cannot increase area as width decreases without increasing height.
else:Move the right pointer inward if its line is shorter or equal.
Moving the right pointer inward when its height is less than or equal to the left pointer maintains the greedy strategy of discarding the limiting factor, enabling exploration of potentially taller lines and larger areas.
l, r = 0, len(height) - 1Initialize left and right pointers at the start and end of the array.
Setting pointers at the boundaries allows the algorithm to consider the widest possible container first, establishing a baseline for comparison.
if height[l] < height[r]:Compare the heights at the left and right pointers.
Determining which pointer to move depends on which line is shorter, as moving the shorter line's pointer may increase the area.
return max_areaReturn the maximum area found after all iterations.
After the pointers meet, max_area holds the largest container area found, which is the correct solution.
area = (r - l) * min(height[l], height[r])Calculate the area formed by the lines at the current pointers.
Area is width (distance between pointers) times the height of the shorter line, which limits the container's height.
max_area = max(max_area, area)Update max_area if the current area is larger.
Maintaining the maximum area found so far ensures the algorithm returns the optimal solution after all iterations.
while l < r:Loop while the left pointer is less than the right pointer.
The condition ensures that the pointers represent a valid container with positive width; when they meet, all pairs have been considered.
max_area = 0Initialize max_area to zero to track the largest container area found.
Starting with zero ensures that any valid container area will update this value, including cases where all heights are zero.
r -= 1End of the while loop iteration.
Completes one iteration of area calculation and pointer movement, progressing the search for the maximum container area.
Test Your Understanding
Why is it always optimal to move the pointer at the shorter line inward?
Because the area is limited by the shorter line, moving the taller line inward cannot increase area since width decreases and height remains limited by the shorter line; moving the shorter line inward is the only move that can potentially find a taller line and increase area.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Container With Most Water from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Container With Most Water drill