Container With Most Water

Number of Islands

Longest Substring Without Repeating Characters

Find two lines that together with the x-axis hold the most water.

You are given an integer array `height` of length `n`. There are `n` vertical lines drawn such that the two endpoints of the ith line are `(i, 0)` and `(i, height[i])`.

Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store.

Notice that you may not slant the container.

## Example
```
Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
```

**Constraints**
- `2 <= height.length <= 10^5`
- `0 <= height[i] <= 10^4`

**Follow-up**
Can you prove why moving the pointer at the shorter line is always safe, and why moving the taller line can never improve the answer?

- Choose two vertical lines at indices `left` and `right`.
- The width is `right - left`.
- The height of the water is limited by the shorter line.
- Area is `(right - left) * min(height[left], height[right])`.

Understand the Area Formula

- Check every pair of lines and compute its area.
- Keep the maximum area found.
- This is simple but O(n²), which is too slow for large arrays.

Brute Force Idea

- Start with the widest possible container: first and last lines.
- Compute the area, then move one pointer inward.
- Moving the taller line cannot help because the shorter line still limits the height while width shrinks.
- Therefore, always move the pointer at the shorter line.

Use Two Pointers

- At each step, calculate the current area.
- Update `best` if this area is larger.
- Move `left` when the left line is shorter, otherwise move `right`.

Update the Best Area While Moving

- The two pointers scan inward in one pass.
- Every possible useful candidate is considered without checking all pairs.
- Time complexity is O(n).
- Space complexity is O(1).