Widest Water Tank

Problem Statement

You're given the heights of a row of vertical support beams, evenly spaced one unit apart. You want to pick exactly two of these beams to serve as the two walls of a rectangular water tank; the ground between them is the floor, and the water can rise no higher than the shorter of the two chosen beams (any higher and it would simply spill over that side). The tank's capacity is therefore the shorter beam's height times the distance between the two beams. Find the maximum capacity achievable by any choice of two beams.

Input Format

The input is exactly one line: the beam heights, as space-separated non-negative integers, from left to right. There are at least 2 heights.

Output Format

Print a single integer: the maximum capacity, min(heights[i], heights[j]) * (j - i), over every pair of positions i < j.

Example Walkthrough

Take the second sample, 1 1. There's only one possible pair here — the beam at position 0 and the beam at position 1 — so the answer has to come from that single pair: min(1, 1) * (1 - 0) = 1.

Now consider a two-pointer trace on the first sample, 1 8 6 2 5 4 8 3 7 (positions 0-8). Start with left = 0 (height 1) and right = 8 (height 7). The capacity between them is min(1, 7) * 8 = 8, so the best so far is 8. Height 1 is the shorter of the two, so move left inward to position 1 (height 8). Now the capacity is min(8, 7) * 7 = 49, which beats the previous best, so the best becomes 49. This time height 7 (at right) is the shorter one, so move right inward instead. The pointers keep moving inward, and every capacity checked after this point uses a width of 6 or less — even paired with the tallest remaining beam, no later pair can reach 49 again, since the width alone is already too small. By the time the pointers meet, the best capacity recorded is 49, matching the expected output.

Approach

Checking every pair of beams directly works, but it's O(n²): for each of the n beams, you'd compare it against up to n-1 others. That's wasteful for a large row of beams.

The two-pointer approach starts from the widest possible pair — the leftmost and rightmost beams — and narrows in from there, doing only O(n) work total. At each step, compute the capacity for the current pair and update the best seen so far. Then move the pointer that's on the shorter of the two beams one step inward (moving either pointer when they're equal). The reasoning behind always moving the shorter one is what makes this correct: keeping the current pair's width and instead moving the taller beam's pointer inward could only ever shrink the width while the water level stays capped by the same beam (the shorter one didn't move) — that can never produce more water than the current pair already did. So there's no need to ever check that option; the only way to possibly do better is to move the shorter beam's pointer inward, hoping to find a taller replacement, even though the width shrinks by one either way.

Because each step moves one of the two pointers strictly inward and they start n-1 apart, the pointers meet after at most n-1 steps, giving O(n) time using only a constant amount of extra memory.

Common Mistakes

• Moving the pointer at the taller beam instead of the shorter one. It's tempting to think you should "get rid of" whichever beam looks less promising, but the correct move is always to advance the pointer sitting on the shorter beam — moving the taller one's pointer can only ever make things worse or equal, never better, as explained above.
• Recomputing the maximum with a nested loop "just to be safe." Once the two-pointer scan is written correctly, no second pass or extra checking is needed — adding a nested loop on top reintroduces the O(n²) cost the two-pointer technique was meant to avoid, for no benefit in correctness.
• Forgetting that height 0 is a valid, meaningful height. A beam of height 0 can still be part of the widest pair by width, but any tank that uses it as one of its two walls holds exactly 0 water (since the water level is capped at 0) — that pair should still be considered when scanning, just correctly contributes 0 rather than being skipped over or treated as invalid input.