The problem
You are given n vertical lines; line i has height height[i] and stands at position i. Choose two lines that, with the ground, form a container.
Return the most water such a container can hold: the distance between the two lines times the height of the shorter one.
Examples
- Input
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
- Output
49
- Input
height = [1, 1]
- Output
1
Constraints
- 2 ≤ n ≤ 10⁵
- 0 ≤ height[i] ≤ 10⁴
The idea
Start with the widest container, the two outermost lines. Any other container is narrower, so to hold more it needs a taller shorter wall.
The shorter wall is the limit. Moving the taller wall inward can only make things worse — narrower, and still capped by the same short wall. So always move the shorter one inward, recording the area at every step. Each step discards a line that can never be part of a better answer.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def maxArea(self, height: List[int]) -> int: l, r = 0, len(height) - 1 best = 0 while l < r: best = max(best, (r - l) * min(height[l], height[r])) # The shorter wall limits the water; moving the taller one in can only lose. if height[l] < height[r]: l += 1 else: r -= 1 return best