container-with-most-water

Difficulty: Medium  ·  Topic: Two Pointers  ·  Practice it on parikshan: /practice/container-with-most-water/start

The story

AWS S3 stores a daily timeseries of free capacity per rack in a region. The capacity planning team wants to find the widest pair of racks that, treated as the two walls of a virtual buffer, hold the most "spillover" capacity between them at the height of the shorter wall. The team will run this query against arrays of tens of thousands of racks. Quadratic time would dominate the daily ETL window, so they need linear.

That is container-with-most-water. The problem is asking for the maximum-area rectangle that fits between two indices of a histogram, where width is the index gap and height is the shorter of the two pillars. It looks geometric, but the underlying pattern is a beautiful two-pointer greedy.

What's actually being asked

Given non-negative integers h_0, h_1, ..., h_{n-1} representing line segments at unit-spaced x-coordinates, return the maximum value of (j - i) * min(h_i, h_j) over all i < j.

The naive approach

Try every pair: O(n²). For n = 5 * 10^4 that is 2.5 billion comparisons. Python will not survive that inside the 2-second window. Even in C++ you would feel it.

The key insight

Start with the widest possible container: the two ends. Width is the only term you cannot regrow once you walk inward, so any future better answer has to come from a taller min(...). Now ask: which side, if you move it inward, could possibly produce a better answer?

If h[l] < h[r], the shorter side is l. Every pair (l, k) with k < r has strictly smaller width and the height is still capped at h[l] because h[l] is what made the min. So no pair starting at l and ending before r can beat the area we just measured. l is exhausted; we can safely advance it.

Symmetric when h[r] < h[l]: r is exhausted, decrement it.

If they tie, either move works, pick one and continue. The proof generalises.

That argument is the entire algorithm. One pass, linear time, O(1) memory.

Step-by-step approach

1. Initialise l = 0, r = n - 1, best = 0.
2. While l < r:
   • Compute area = (r - l) * min(h[l], h[r]). Update best if larger.
   • If h[l] < h[r], increment l. Else decrement r.
3. Print best.

Worked example

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

Loop exits. Output: 49. (The optimal container is the pair at indices 1 and 8.)

Complexity

• Time: O(n). Each iteration moves exactly one pointer.
• Space: O(1).

Compare to brute force at O(n²). The two-pointer move rule is what unlocks the linear answer.

Common pitfalls

• Moving both pointers every iteration. That breaks the proof; you can miss the optimal answer in cases like [1, 9, 1, 1, 1, 9, 1].
• Using the taller side as the "exhausted" side. Backwards; you keep the taller side and walk the shorter one in. The shorter side caps the height; only by replacing it can min(...) grow.
• Computing area as (r - l + 1) * min(...). Width is the index gap, not the count of indices. Off-by-one.
• Returning early on a "good enough" area. No monotonicity in area itself; you must finish the scan.
• Ignoring zeros. A zero on either side caps area at zero for that step. Don't special-case; the formula already handles it.

Where this shows up in the enterprise

• AWS S3 capacity planning: max-spread pair of racks bracketing usable buffer.
• Bloomberg historical volatility: the widest pair of low-vol days bracketing a smooth interval is the largest "calm window" you can stretch around an event.
• YouTube ad pacing: the widest pair of impression slots bracketing a target spend without ever exceeding a per-day cap (the cap is the min).
• Twilio rate-limit planning: the longest interval between two timestamps bracketed by a peak rate that all intermediate buckets stayed under.
• Datadog SLO error budgets: the longest window bracketed by two days at or above a budget burn threshold.
• Spotify playlist generation: two anchor songs at distinct tempos bracketing a transition zone where intermediate songs must satisfy a tempo min.
• Akamai cache region selection: two PoPs bracketing the widest geography under a latency cap.

The pattern is "two boundaries times a cap"; whenever the answer is a product of width and a min (or max), the move-the-binding-side rule applies.

Variants you'll see elsewhere

• trapping-rain-water: same skeleton (two pointers, move the shorter side) but the question is total trapped water rather than the single best rectangle.
• largest-rectangle-in-histogram: similar shape but rectangle height is the minimum over a contiguous range, solved with a monotonic stack not pointers.
• maximum-water-bottle: small constant-factor variation on the same area formula.
• the-skyline-problem: distant cousin; geometric but pointer-free.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

1. The editor runs your code against public tests for instant feedback and against per-session dynamic private tests (generated freshly per session). Synthetic cases include monotonic-increase and monotonic-decrease inputs (where the answer is in the centre), all-zeros, two-element arrays, and tall walls on the ends.
2. Hints are graduated. Level 1 prompts you to think about width monotonicity. Level 4 gives you the full move-the-shorter-side rule. Each level docks integrity.
3. The AI training assistant in exam mode offers Explain, Review, Find Bugs, Add Comments, Optimise, each costs integrity. In practice mode chat is free.
4. The dispute flow runs after the verdict. The most common dispute here is "my brute force is correct but too slow"; the judge is enforcing the time limit, not the algorithm.

Read this concept first, attempt the problem in practice mode, take a hint only when you actually need one, then redo it in exam mode with no help. When you can write the move-the-shorter-side proof on a whiteboard in two minutes, the pattern is in your fingers.

In the AI-integrated workspace

In your future job, the agent writes the code. Your job is to:

1. Recognise that any "max product of width and a min cap" question has two pointers as its native algorithm. The recognition is the entire skill.
2. Tell the agent precisely: "two pointers, converging, move the shorter side". Not "find the best rectangle", that invites a brute force.
3. Read the generated code and verify: width is the index gap (not gap + 1), exactly one pointer moves per iteration, the tie-break is correct (either side, but only one).
4. Push the edge cases the agent will miss: ties between heights, all zeros, n = 2, monotone arrays where the optimum is at the boundary.

Candidates who can name "this is move-the-shorter-side" within five seconds are the ones who turn AI into leverage. Candidates who can't end up approving a quadratic solution that passes the public tests and times out on a hidden case. parikshan is built to train the first kind.