two-pointers · Problem 3 of 4
Container With Most Water
hard
Amazon
Google
AmazonGoogleEach element of heights is a vertical line. Return the largest area of water two lines can hold between them.
maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) -> 49Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Running is free — Submit is what records it. Or press ⌘↩
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| maxArea([1,8,6,2,5,4,8,3,7]) | classic | 49 | — |
| maxArea([1,1]) | two lines | 1 | — |
| maxArea([1,2,3,4,5]) | increasing | 6 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n)
- target space
- O(1)
The brute force over every pair is O(n^2). The invariant — moving the taller line can never help — is what makes one pass sufficient.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left