Container With Most Water: definition
Two vertical lines form the sides of a container. Its width is the distance between their indices, and its water level is limited by the shorter line.
Task example: Container With Most Water
Given non-negative integer heights, choose two different indices and return the maximum container area. Area = (right - left) × min(height[left], height[right]). Keep the original order; do not sort the heights.
Indices 1 and 8 give width 7 and limiting height 7: area 49. Intermediate lines do not reduce this area. This is not the Trapping Rain Water problem.
Brute force: video explanation
height = [1, 8, 6, 2, 5, 4, 8, 3, 7] → 49
Prefer reading? Follow the steps below.
- Start best at 0. Choose each left wall i, then every right wall j after it. This checks each distinct pair once.
- For each pair, multiply j - i by the smaller height. Update best if this area is larger.
- At indices 1 and 6, area is 5 × 8 = 40. At indices 1 and 8, area is 7 × 7 = 49. Keep checking all remaining pairs, then return best.
Time complexity · O(n²)
There are n(n - 1) / 2 pairs, with constant work per pair. Time complexity is O(n²).
Space complexity · O(1)
Only indices, area, and best are stored. Extra space is O(1); the input is not copied.
Two pointers: video explanation
height = [1, 8, 6, 2, 5, 4, 8, 3, 7] → 49
Prefer reading? Follow the steps below.
- Start left at index 0 and right at the last index. Compute the current area and update best before moving either pointer.
- Move the pointer at the shorter wall inward. If the heights are equal, either side is safe; this code moves right.
- The first pair gives area 8. Move left to index 1: the next pair gives 49. Later pairs give 18, 40, 16, 15, 4, and 6. When the pointers meet, return 49.
Why it works: keeping the shorter wall while narrowing the width cannot improve the current area. Discard that wall after recording its area. This avoids checking every pair without missing the maximum.
Time complexity · O(n)
One pointer moves inward per iteration. At most n - 1 pairs are checked, so time complexity improves from O(n²) to O(n).
Space complexity · O(1)
Two pointers, area, and best use O(1) extra space. Both approaches use constant space; the improvement is in time.