Largest Container

The Problem

You are given an array heights where heights[i] represents the height of a wall at position i. Find two walls that, together with the x-axis, form a container holding the maximum amount of water, and return that area.

Area = min(heights[i], heights[j]) × (j − i)

The container’s height is limited by the shorter of the two walls. Its width is the distance between them.

Input:  heights = [2, 4, 3, 3, 5, 2, 4, 3, 2]
Output: 20

Examples

Example 1

Input:  heights = [2, 4, 3, 3, 5, 2, 4, 3, 2]
Output: 20
Explanation: walls at index 1 (height 4) and index 6 (height 4)
             area = min(4,4) × (6-1) = 4 × 5 = 20

Example 2

Input:  heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: walls at index 1 (height 8) and index 8 (height 7)
             area = min(8,7) × (8-1) = 7 × 7 = 49

Example 3

Input:  heights = [1, 1]
Output: 1
Explanation: Only two walls — area = min(1,1) × 1 = 1

Visualising the Container

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph WALLS["heights = [2, 4, 3, 3, 5, 2, 4, 3, 2]"]
    direction LR
    W0["h=2\npos 0"] --- W1["h=4\npos 1"] --- W2["h=3\npos 2"] --- W3["h=3\npos 3"] --- W4["h=5\npos 4"] --- W5["h=2\npos 5"] --- W6["h=4\npos 6"] --- W7["h=3\npos 7"] --- W8["h=2\npos 8"]
  end
  BEST["Best container:\nwalls at pos 1 (h=4) and pos 6 (h=4)\nwidth  = 6 − 1 = 5\nheight = min(4, 4) = 4\narea   = 4 × 5 = 20"]
  W1 & W6 -.->|"optimal pair"| BEST

The largest container uses walls at positions 1 and 6 — both height 4, width 5, area 20. All taller walls (h=5 at pos 4) have a narrower span.

Applying the Diagnostic Questions

Run the same four questions from the identifying lesson against this problem.

Q1 — Why “order matters here” — and why that blocks sorting

WHAT: The width in the formula is j − i, the literal distance between indices. Positions are baked into the formula itself.

WHY it matters: Sorting rearranges elements to new positions, which changes every j − i value. Walls that were far apart become adjacent. Walls that were adjacent get pulled apart. The formula gives completely different — and meaningless — results on a sorted array.

Concrete check: heights = [2, 4, 3, 3, 5, 2, 4, 3, 2]. The optimal pair is index 1 (h=4) and index 6 (h=4) — width = 5, area = 20. After sorting to [2, 2, 2, 3, 3, 3, 4, 4, 5], those same two walls (h=4, h=4) end up at indices 6 and 7 — width = 1, area = 4. The formula produces a completely wrong answer.

What this means for the pattern: Unlike Two Sum, sorting is forbidden here. But this problem still belongs in the two-pointer reduction category — it just reaches the decisive direction through a different mechanism.

Key contrast with Two Sum:

• Two Sum: Q1 = No → sorting is free → sorting creates the decisive direction.
• Largest Container: Q1 = Yes → sorting is forbidden → the area formula creates the decisive direction.

Q2 — Why “we always need two items simultaneously”

Same reasoning as Two Sum. The area formula min(h[i], h[j]) × (j − i) requires two wall positions at once — there is no way to evaluate it with a single pointer. Q2 is always the easy yes for pair-based problems.

Q3 — Why traversing from both ends is already “special” here

WHAT: Starting with left = 0 and right = n-1 gives the maximum possible width for any container. Every other starting pair has a strictly smaller span.

WHY it matters: Width only ever shrinks as pointers move inward. Starting at maximum width means you begin at the point where the width advantage is at its peak — the only question is whether the heights are tall enough to make it count.

Concrete check: heights = [2, 4, 3, 3, 5, 2, 4, 3, 2], n=9. Starting width = 8. Every other pair has width ≤ 8. If the answer were a very wide, short container, starting from both ends finds it immediately at step 1.

What breaks without this? If you started two pointers somewhere in the middle, you’d skip all wide containers without ever checking them. The “start at max width” invariant is what allows you to shrink the search space one pointer move at a time without missing the answer.

Q4 — How the area formula creates decisive direction without sorting

This is the core insight that makes Largest Container a two-pointer reduction problem despite sorting being forbidden.

In Two Sum, sorting created a guarantee: arr[left] is always the minimum of remaining elements, arr[right] is always the maximum. That guarantee made every pointer move decisive — moving left right always increases the sum, moving right left always decreases it.

Here, sorting is forbidden — but the area formula creates an equivalent guarantee through a different mechanism.

The decisive guarantee — worked out concretely:

Suppose at some step h[left] < h[right]. The current area is:

area = h[left] × (right - left)

The height is capped at h[left] because the shorter wall is the bottleneck. Now ask: what happens if we move right inward?

new area = min(h[left], h[right-1]) × (right - left - 1)
         ≤ h[left]                  × (right - left - 1)    ← height still capped by h[left], or even lower
         < h[left]                  × (right - left)         ← width strictly decreased by 1
         = current area

Moving right inward is provably useless: width shrinks by 1, and the height is still capped by h[left] (the bottleneck hasn’t changed). Area can only get smaller.

Moving left inward might find a taller wall — raising the height cap enough to compensate for the lost width. It’s not guaranteed to improve things, but it’s the only move that can possibly improve the area.

What breaks if you move the taller pointer anyway? You’d miss optimal pairs. On heights = [2, 4, 3, 3, 5, 2, 4, 3, 2], at step 3 you have left=1 (h=4) and right=7 (h=3). Moving right to index 6 is the only hope of improvement — if you moved left instead (the taller wall), you’d skip the optimal pair (1, 6) where area = 20.

The parallel with Two Sum:

Both use the same proof structure: at every step, one element has already seen its best possible result. Discarding it cannot miss the optimal answer. The only difference is what creates the guarantee — sorted order for Two Sum, the structure of the formula for Largest Container.

How to identify this type of problem

Two-pointer reduction via greedy formula has a specific fingerprint:

1. O(n²) brute force exists — you’re searching over all pairs of positions
2. Order matters — you cannot sort (positions are part of the formula)
3. Starting from both ends maximises something — maximum width here, maximum span in other problems
4. One element is provably useless at each step — not “might not help”, but “mathematically cannot help”

The last point is the decisive test. Ask yourself: “If I hold left fixed and move right inward, can the result ever improve? If I hold right fixed and move left inward, can the result ever improve?”

If one of those answers is provably No at every step, you have a greedy decisive direction — and two pointers apply without sorting.

Intuition: The Greedy Choice

Start with the widest possible container: left = 0, right = n−1. This gives maximum width. Now, how do we decide which pointer to move inward?

Key insight: the area is bounded by min(heights[left], heights[right]). Moving the taller wall inward can only decrease or maintain the height limit — the shorter wall still caps us. It cannot improve the area.

Moving the shorter wall inward might find a taller wall, potentially increasing the height limit enough to compensate for the width loss.

Greedy rule: always move the pointer sitting on the shorter wall.

This replaces sorting as the source of decisive direction. Sorting gave Two Sum a structural guarantee about min and max. Here the area formula gives Largest Container a structural guarantee about which wall is the bottleneck — and moving the non-bottleneck wall can only make things worse.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Init["left = 0<br/>right = n−1<br/>max_area = 0"]
  Loop{"left < right?"}
  Calc["Compute area:<br/>min(h[L], h[R]) × (R − L)<br/>Update max_area"]
  Which{"h[L] < h[R]?"}
  MoveL["left++<br/>(left is shorter)"]
  MoveR["right--<br/>(right is shorter or equal)"]
  Done(["return max_area"])

  Init --> Loop
  Loop -->|"yes"| Calc --> Which
  Which -->|"yes"| MoveL --> Loop
  Which -->|"no"| MoveR --> Loop
  Loop -->|"no"| Done

Largest Container algorithm — compute area at each step, then move the shorter wall's pointer inward.

Solution

from typing import List

class Solution:
    def largest_container(self, heights: List[int]) -> int:
        # Initialize left pointer at the first wall
        left     = 0
        # Initialize right pointer at the last wall
        right    = len(heights) - 1
        max_area = 0

        # Run while there is a valid container between the two pointers
        while left < right:
            # Compute the area of the current container
            width  = right - left
            height = min(heights[left], heights[right])
            area   = width * height
            # Update maximum area if current container is larger
            max_area = max(max_area, area)

            # Move the shorter wall inward — it is the only pointer that can improve the area
            if heights[left] < heights[right]:
                left += 1
            else:
                right -= 1

        return max_area


# --- Test ---
sol = Solution()
print(sol.largest_container([2, 4, 3, 3, 5, 2, 4, 3, 2]))   # 20
print(sol.largest_container([1, 8, 6, 2, 5, 4, 8, 3, 7]))   # 49
print(sol.largest_container([1, 1]))                          # 1
print(sol.largest_container([4, 3, 2, 1, 4]))                 # 16

Dry Run — Example 1

heights = [2, 4, 3, 3, 5, 2, 4, 3, 2], n=9

Return 20 ✓

Why Not Just Move Either Pointer?

The claim: when h[left] ≤ h[right], we can permanently discard left and move left++ without missing the optimal answer.

Why this is true — one wall at a time:

When we’re at (left, right) and h[left] ≤ h[right], ask: is there any other container using left as one wall that could beat the current area?

The only possible partners for left are positions j where left < j < right — everything outside the current window has already been discarded. For any such j:

area(left, j) = min(h[left], h[j]) × (j − left)
              ≤ h[left]             × (j − left)    ← height capped by h[left] regardless of h[j]
              < h[left]             × (right − left) ← width is strictly smaller (j < right)
              = area(left, right)                    ← the current area

Every possible partner for left — every j between the two pointers — produces an area that is strictly smaller than what we just computed. Width shrinks because j is closer than right. Height cannot grow above h[left] because left is the shorter wall and it caps every container it forms.

So area(left, right) is already the best container that left can ever be part of. There is no reason to keep left in consideration — discard it.

What breaks if you always move left instead:

Let’s run both strategies on heights = [2, 4, 3, 3, 5, 2, 4, 3, 2] and watch them diverge.

Correct — move the shorter wall:

Wrong — always left++:

The pair (1, 6) — h=4, h=4, area=20 — is never checked. right is stuck at index 8 the entire time. Index 6 is never the right pointer, so that container simply does not exist in the wrong run.

Divergence tree:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  S["Step 1<br/>l=0 h=2,  r=8 h=2<br/>area = 16<br/>h[l] == h[r]"]

  S -->|"Correct: move shorter → right--"| C1
  S -->|"Wrong: always left++"| W1

  C1["l=0 h=2,  r=7 h=3<br/>area = 14<br/>h[l] &lt; h[r] → left++"]
  C1 --> C2

  C2["l=1 h=4,  r=7 h=3<br/>area = 18<br/>h[l] &gt; h[r] → right--"]
  C2 --> C3

  C3["l=1 h=4,  r=6 h=4<br/>area = 20  ✓ OPTIMAL<br/>pair (1, 6) found"]

  W1["l=1 h=4,  r=8 h=2<br/>area = 14<br/>index 0 gone — always left++"]
  W1 --> W2

  W2["l=2 h=3,  r=8 h=2<br/>area = 12<br/>index 1 gone — always left++"]
  W2 --> W3

  W3["l=3..7,  r=8 stuck<br/>right never moves<br/>pair (1, 6) never seen"]
  W3 --> W4

  W4["Returns 16  ✗<br/>missed optimal by 4"]

Correct rule reaches pair (1, 6) in 4 steps. Wrong rule locks right at index 8 permanently — the optimal pair is never reachable.

The root of the failure: at step 1, h[left] = h[right] = 2. Both walls are equally short. The correct rule says “move the shorter (or equal) wall” — that’s right. The wrong rule blindly moves left, which advances past index 0 and locks right at index 8 for the rest of the run. Once left is at index 1 with right stuck at 8, index 1 gets discarded at step 2 — and the pair (1, 6) becomes unreachable forever.

Dry Run — Example 2

heights = [1, 8, 6, 2, 5, 4, 8, 3, 7], n=9

Return 49 ✓

Using Example 2 to understand “move the shorter wall”

Step 2 is the critical moment. left=1 (h=8), right=8 (h=7). h[right] < h[left] — so the right wall is shorter and the rule says right--.

Why is it safe to discard right=8 here?

right=8 (h=7) is the bottleneck. Any future partner j for index 8 must lie between the two pointers, i.e. 1 < j < 8. For any such j:

area(j, 8) = min(h[j], 7) × (8 − j)
           ≤ 7             × (8 − j)    ← height capped at 7 (h[right]) no matter how tall h[j] is
           < 7             × 7          ← width shrinks because j > 1, so (8 − j) < (8 − 1) = 7
           = 49                         ← the area we already recorded at step 2

The current container (1, 8) with area 49 is already the best result that index 8 (h=7) can ever produce. Width is at its maximum for this right wall right now — every future partner is closer, so width only shrinks. Height is capped at 7 regardless of what partner we pick. Nothing can beat 49. Discard right.

What breaks if you move left at step 2 instead:

Suppose at step 2 you incorrectly move left++ (advancing the taller wall):

In this case the answer happens to be 49 anyway — but only by accident, because step 2 still computed area 49 before moving the wrong pointer. The real danger is what you miss in the steps that follow.

Consider a slight variation: heights = [1, 8, 6, 2, 5, 4, 8, 10, 7] (changed index 7 from 3 to 10).

The correct algorithm would find the pair (7, 8): min(10, 7) × 1 = 7 — not useful. But (1, 7): min(8, 10) × 6 = 48 is a strong candidate. And (1, 8): min(8, 7) × 7 = 49 is still the winner.

Now if at step 2 we moved left instead of right:

• left advances past index 1 forever
• The pair (1, 7) with area 48 is never checked
• We might still get 49, but only because of this specific input — the algorithm’s correctness guarantee is broken

The rule is not “we might get lucky” — it is “we provably never skip a better answer.” Moving the taller pointer breaks that proof.

Complexity Analysis

Largest Container is the only problem in this section that doesn’t require sorting — the greedy pointer-movement rule replaces the need for sorted order.

Edge Cases

Key Takeaway

Largest Container teaches a different flavour of the two-pointer reduction: instead of sorting to establish order, the greedy rule “always move the shorter wall” gives the pointer direction at each step. The reasoning is: the current container is the best we can do with the shorter wall, so the shorter wall can be safely advanced. This greedy argument replaces the sorted-array invariant from Two Sum.