Container With Most Water
You get a list of non-negative integers. Each number is the height of a vertical wall, and the walls stand one unit apart in a row.
Pick any two walls. Together with the floor they form a container. The water it holds is the distance between the walls times the height of the shorter wall.
Return the largest amount of water any pair of walls can hold.
Examples
Input height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output 49
Walls at positions 1 and 8: height 7, width 7.
Input height = [1, 1]
Output 1
Input height = [4, 3, 2, 1, 4]
Output 16
The two 4 walls, width 4.
Constraints
- 2 <= height.length <= 100,000
- 0 <= height[i] <= 10,000
Stuck? Take one hint at a time
Common mistakes
- Moving the taller wall, which can skip the best answer.
- Using the larger height instead of the smaller one when computing the area.
- Measuring the width as right - left + 1.
- Trying every pair, which is too slow for 100,000 walls.
Questions an interviewer may ask next
- Return the two positions, not just the area.
- Walls can have different widths. What changes?
- Count the water trapped between walls instead of the biggest container. (A different and harder problem.)
- Prove why discarding the shorter wall is safe.
How often this is reported
Commonly reported across 16 of 25 tracked companies
16/25
Grade B: Reported in more than one source. This reflects what candidates report, not a guarantee of what any company will ask.
height
[1,8,6,2,5,4,8,3,7]
Expected output
49
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.