Container With Most Water

You are given an array of n non-negative integers where each value height[i] represents the height of a vertical line drawn at position i on the x-axis. Choose two of these lines that, together with the x-axis, form a container, and find the maximum amount of water the container can hold. The container cannot be tilted, so the amount of water held is limited by the shorter of the two chosen lines, and the width is the distance between their positions.

Input: The first line contains the integer n. The second line contains n space-separated non-negative integers representing height. Output: Print a single integer: the maximum amount of water that can be contained.

2 <= n <= 10^5 0 <= height[i] <= 10^9

This is a classic example of GREEDY two-pointer elimination - at every step, one specific choice (move the shorter line) is proven to never be worse than any alternative, letting the search safely skip over all the other, provably-inferior candidates.

Choose two vertical lines that, together with the x-axis, hold the most water. Brute force: Check every possible pair of lines directly, computing the area for each - this costs O(n²), too slow for large arrays. Optimised: Starting from the WIDEST possible container and always moving the pointer at the SHORTER line is provably safe: keeping the taller line and moving the shorter one is the only way width-loss could POSSIBLY be compensated by a taller replacement, while moving the taller line would strictly decrease the area (since the shorter line still bounds the height, and the width only shrinks). This greedy elimination explores every USEFUL candidate in a single linear pass.

1. Start with the WIDEST possible container: one pointer at the very FIRST line, one at the very LAST. 2. At each step, compute the area, then move INWARD the pointer at the SHORTER line - moving the taller one can never increase the area, since width only shrinks either way. 3. Keep track of the best area seen across all steps until the two pointers meet.

Time: O(n) - the two pointers together traverse the array once, moving inward until they meet. Space: O(1) - just two pointers and a running best-area variable.

Handle n = 2 (only one possible pair) and cases where the tallest lines are buried in the middle rather than at the ends; use the two-pointer technique to stay within O(n) at n = 10^5.

Be ready to prove WHY moving the taller line's pointer is never beneficial - this is the entire justification for the greedy two-pointer approach, and articulating it clearly (not just applying the rule) is what interviewers listen for.