Container With Most Water
Explanation & Solution
Description
Given n non-negative integers height[0], height[1], ..., height[n-1], where each represents the height of a vertical line drawn at index i, find two lines that together with the x-axis form a container that holds the most water.
Return the maximum amount of water the container can store.
Note: You may not slant the container.
Output: 49
Explanation: The lines at index 1 (height 8) and index 8 (height 7) form a container of width 7 and height 7, giving area = 7 * 7 = 49.
Constraints
n == height.length2 <= n <= 10⁵0 <= height[i] <= 10⁴
Approach
Two Pointers pattern
1. Initialize Two Pointers
- Set
left = 0(start of array) - Set
right = height.length - 1(end of array) - Set
max = 0to track the maximum area found
2. Calculate Area at Current Pointers
- The width of the container is
right - left - The height is limited by the shorter line:
Math.min(height[left], height[right]) - The area is
width * height
3. Update Maximum Area
- Compare the current area with
max - Keep the larger value:
max = Math.max(max, width * h)
4. Move the Shorter Pointer Inward
- If
height[left] < height[right], moveleft++ - Otherwise, move
right-- - Why? Moving the shorter line inward is the only way to potentially find a taller line that could increase the area
5. Repeat Until Pointers Meet
- Continue the loop while
left < right - Each iteration eliminates one pointer position
- This guarantees O(n) time complexity
6. Return the Result
- After the loop,
maxholds the largest container area found - Return
max
Key Insight
Moving the pointer with the shorter height is always the correct greedy choice. Since the width is shrinking by 1 each step, the only way to find a larger area is to find a taller minimum height. Keeping the taller line and replacing the shorter one is the only move that has a chance of improving the result.
Visualization
Press ▶ or use ← → to step through