Container With Most Water

Find the maximum water a pair of lines can hold using the two-pointer technique.

two-pointers array maximization

You are given an array `height` of non-negative integers, where each element represents the height of a vertical line at that index. You need to find the maximum amount of water that can be contained between two lines, along with the x-axis. The container's width is the distance between the two indices, and its height is the minimum of the two line heights. The area is computed as `min(height[i], height[j]) * (j - i)`.

Write a function `max_area(height)` that takes a list of non-negative integers and returns the maximum possible area as an integer.

Your solution must be efficient. A brute-force O(n^2) solution will not pass the time limit for large inputs. Use the two-pointer technique to achieve O(n) time.

Constraints

- `1 <= len(height) <= 10^5`
- `0 <= height[i] <= 10^4`
- The function must be called `max_area` and accept a single list argument.
- Time complexity must be O(n), space O(1).

Example

>>> max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])
49
>>> max_area([1, 1])
1
>>> max_area([4, 3, 2, 1, 4])
16
>>> max_area([1, 2, 1])
2

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Start with two pointers at the two ends of the array.

The area is limited by the shorter line; moving the taller line inward cannot increase the area.

Keep track of the maximum area seen so far while moving the pointers.

To maximize area, always move the pointer that points to the shorter line.

Continue until the two pointers meet.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.