# LeetCode 11: Container With Most Water

## Problem Restatement

We are given an integer array `height`.

There are `n` vertical lines.

The `i`th line has endpoints:

```text
(i, 0)
(i, height[i])
```

Choose two lines. Together with the x-axis, they form a container.

The amount of water the container can hold depends on:

1. the distance between the two lines
2. the shorter of the two heights

The goal is to return the maximum amount of water any pair of lines can hold.

The container cannot be slanted. The LeetCode statement defines the area using two vertical lines and the x-axis.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `height` |
| Output | The maximum water area |
| Width | Distance between two indices |
| Height | The smaller of the two chosen line heights |
| Constraint | Choose exactly two lines |

Example function shape:

```python
def maxArea(height: list[int]) -> int:
    ...
```

## Examples

Example 1:

```text
height = [1,8,6,2,5,4,8,3,7]
```

The best pair is:

```text
index 1, height 8
index 8, height 7
```

Width:

```text
8 - 1 = 7
```

Container height:

```text
min(8, 7) = 7
```

Area:

```text
7 * 7 = 49
```

Output:

```text
49
```

Example 2:

```text
height = [1,1]
```

There are only two lines.

Width:

```text
1
```

Height:

```text
1
```

Area:

```text
1
```

Output:

```text
1
```

## First Thought: Try Every Pair

The most direct solution is to check every pair of lines.

For each pair `(i, j)`:

```text
i < j
```

Compute:

```text
area = (j - i) * min(height[i], height[j])
```

Keep the largest area.

Code:

```python
class Solution:
    def maxArea(self, height: list[int]) -> int:
        best = 0
        n = len(height)

        for i in range(n):
            for j in range(i + 1, n):
                width = j - i
                h = min(height[i], height[j])
                best = max(best, width * h)

        return best
```

This is easy to understand and correct, but it checks too many pairs.

## Problem With Brute Force

There are `O(n^2)` pairs of lines.

For large input, this is too slow.

| Metric | Value |
|---|---|
| Time | `O(n^2)` |
| Space | `O(1)` |

We need a linear-time method.

## Key Insight

The area is:

```text
width * min(left_height, right_height)
```

Start with the widest possible container:

```text
left = 0
right = n - 1
```

This gives the maximum possible width.

Now we decide which pointer to move.

If:

```text
height[left] < height[right]
```

then the left line is the limiting height.

Moving the right pointer inward makes the width smaller, while the limiting left height stays the same or lower. So keeping the same left line cannot produce a better area by moving only the right pointer.

Therefore, we should move the shorter side.

The only chance to improve the area after width shrinks is to find a taller limiting line.

## Why Move the Shorter Line

Suppose:

```text
height[left] <= height[right]
```

The current area is:

```text
(right - left) * height[left]
```

Now consider any container using the same `left` and a smaller right index `k`, where:

```text
left < k < right
```

Its width is smaller:

```text
k - left < right - left
```

Its height is at most:

```text
height[left]
```

because the shorter side cannot exceed `height[left]`.

So its area cannot exceed the current area.

That means after checking `(left, right)`, no better answer can be found using the current `left`.

So we safely move `left` forward.

The same reasoning applies symmetrically when `height[right] < height[left]`.

## Visual Walkthrough

Use:

```text
height = [1,8,6,2,5,4,8,3,7]
```

Start:

```text
left = 0
right = 8
```

Area:

```text
width = 8
height = min(1, 7) = 1
area = 8
```

The left side is shorter, so move `left`.

Now:

```text
left = 1
right = 8
```

Area:

```text
width = 7
height = min(8, 7) = 7
area = 49
```

This becomes the best answer.

Now the right side is shorter, so move `right`.

The scan continues until the two pointers meet.

The largest area found is:

```text
49
```

## Algorithm

1. Set `left = 0`.
2. Set `right = len(height) - 1`.
3. Set `best = 0`.
4. While `left < right`:
   - compute the current width
   - compute the current height using the shorter line
   - update `best`
   - move the pointer at the shorter line
5. Return `best`.

## Correctness

At every step, the algorithm checks the container formed by `left` and `right`.

If `height[left] <= height[right]`, then `height[left]` limits the current container.

Any container that keeps the same `left` but moves `right` inward has smaller width and height no greater than `height[left]`. Therefore, it cannot have a larger area than the current container.

So after checking the current pair, the algorithm can discard `left`.

If `height[right] < height[left]`, the symmetric argument shows that the algorithm can discard `right`.

Each step discards only a line that cannot participate in a better unseen container.

Since the algorithm keeps the best area among all checked containers and safely removes impossible boundary lines, it returns the maximum possible area.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each pointer moves inward at most `n` times total |
| Space | `O(1)` | Only a few variables are stored |

## Implementation

```python
class Solution:
    def maxArea(self, height: list[int]) -> int:
        left = 0
        right = len(height) - 1
        best = 0

        while left < right:
            width = right - left
            h = min(height[left], height[right])

            best = max(best, width * h)

            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1

        return best
```

## Code Explanation

Initialize the two pointers at both ends:

```python
left = 0
right = len(height) - 1
```

This starts with the widest possible container.

Compute the current width:

```python
width = right - left
```

Compute the limiting height:

```python
h = min(height[left], height[right])
```

Update the best area:

```python
best = max(best, width * h)
```

Then move the shorter side:

```python
if height[left] <= height[right]:
    left += 1
else:
    right -= 1
```

Finally:

```python
return best
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxArea([1,8,6,2,5,4,8,3,7]) == 49
    assert s.maxArea([1,1]) == 1
    assert s.maxArea([4,3,2,1,4]) == 16
    assert s.maxArea([1,2,1]) == 2
    assert s.maxArea([2,3,4,5,18,17,6]) == 17
    assert s.maxArea([1,2,4,3]) == 4

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1,8,6,2,5,4,8,3,7]` | Standard example |
| `[1,1]` | Smallest useful case |
| `[4,3,2,1,4]` | Best pair uses both ends |
| `[1,2,1]` | Middle height does not always matter |
| `[2,3,4,5,18,17,6]` | Tallest line alone is not enough |
| `[1,2,4,3]` | Checks pointer movement logic |