Container With Most Water Solution

Problem

You're given an array of integers where each value represents the height of a vertical bar. Pick two bars to form the sides of a container — the amount of water it holds equals the shorter bar's height multiplied by the horizontal distance between them. Find the pair of bars that maximizes the volume of water.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: Bars at index 1 (height 8) and index 8 (height 7) form a container holding min(8,7) × 7 = 49 units of water.

Intuition

Water can only fill up to the shorter of the two walls — a 100-meter wall is useless if the other side is 1 meter. The brute-force approach checks every pair, but there's a smarter observation: starting from the outermost bars gives the widest possible container. The only way to potentially find a larger container is to swap out the shorter bar for something taller, because keeping the shorter bar and narrowing the width can never increase the area. This "always move the shorter pointer" rule is greedy and provably safe — it never skips over a better answer.

Approach 1 — Brute Force

Try every possible pair of bars and track the maximum water volume seen.

Iterate over every pair of indices (left, right) where left < right.
Compute water as min(height[left], height[right]) * (right - left).
Update the running maximum.
Return the maximum after all pairs are checked.

1def maxArea(self, height: list[int]) -> int:
2    max_water = 0
3    n = len(height)
4
5    for left in range(n):
6        for right in range(left + 1, n):
7            # Water is capped by the shorter wall, spread across the gap
8            current_water = min(height[left], height[right]) * (right - left)
9            max_water = max(max_water, current_water)
10
11    return max_water

Time: O(n²) — we examine every pair of bars.
Space: O(1) — no extra storage needed.

Approach 2 — Two Pointers

Start at the widest possible container and converge inward, always discarding the shorter bar.

Initialize left = 0 and right = len(height) - 1.
Compute the water for the current pair and update the maximum.
Moving the taller bar inward shrinks the width while the effective height stays capped at the same shorter bar — area can only decrease. Moving the shorter bar inward at least gives a chance of finding a taller wall. So always advance the pointer at the shorter bar.
Repeat until the two pointers meet.

1def maxArea(self, height: list[int]) -> int:
2    left, right = 0, len(height) - 1
3    max_water = 0
4
5    while left < right:
6        # Water is capped by the shorter wall, spread across the gap
7        current_water = min(height[left], height[right]) * (right - left)
8        max_water = max(max_water, current_water)
9
10        # Moving the taller wall inward can't improve the result; eliminate the shorter one
11        if height[left] < height[right]:
12            left += 1
13        else:
14            right -= 1
15
16    return max_water

Time: O(n) — each pointer moves at most n steps total.
Space: O(1) — only two pointer variables.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Verifying correctness or when n is very small
Two Pointers	O(n)	O(1)	Always — the standard solution for this problem

Common Mistakes

Moving the taller pointer instead of the shorter one — if you move the taller pointer inward, you shrink the width while the height is still capped by the shorter bar. The area can only decrease. You must move the shorter bar's pointer to have any hope of improvement.
Computing area as height[left] * height[right] — water can only fill to the height of the shorter wall, and the width is the index gap, not related to the heights themselves.
Using left <= right as the loop condition — when left == right you're pointing at a single bar, which forms no container. Use left < right.
Second-guessing the equal-height case — when height[left] == height[right], both bars are the bottleneck and moving either pointer is safe. The else branch (decrement right) handles this correctly without a special case.
Confusing this problem with Trapping Rain Water — in that problem every bar traps water independently using left/right maximum arrays; here only the two chosen endpoint bars form the walls and the bars between them are irrelevant.

Container With Most Water — Solution