Container With Most Water — Greedy Two Pointer O(n) [Google, Meta]

Problem Statement

Given n non-negative integers representing heights, find two that together with the x-axis form a container with the most water.

Input: [1,8,6,2,5,4,8,3,7] → 49

Intuition
C++ Solution
Java Solution
Python Solution
JavaScript Solution
Complexity: O(n) time, O(1) space

Intuition

Start with widest container (l=0, r=n-1). Area = min(h[l],h[r]) * (r-l). Moving the taller pointer inward can only decrease width without gaining height → never optimal. Always move the shorter pointer.

C++ Solution

class Solution {
public:
    int maxArea(vector<int>& h) {
        int l=0, r=(int)h.size()-1, best=0;
        while (l < r) {
            best = max(best, min(h[l],h[r]) * (r-l));
            if (h[l] < h[r]) l++;
            else r--;
        }
        return best;
    }
};

Java Solution

class Solution {
    public int maxArea(int[] h) {
        int l=0, r=h.length-1, best=0;
        while (l < r) {
            best = Math.max(best, Math.min(h[l],h[r])*(r-l));
            if (h[l] < h[r]) l++;
            else r--;
        }
        return best;
    }
}

Python Solution

def maxArea(height):
    l, r, best = 0, len(height)-1, 0
    while l < r:
        best = max(best, min(height[l],height[r]) * (r-l))
        if height[l] < height[r]: l += 1
        else: r -= 1
    return best

JavaScript Solution

function maxArea(h) {
    let l=0, r=h.length-1, best=0;
    while (l < r) {
        best = Math.max(best, Math.min(h[l],h[r])*(r-l));
        h[l] < h[r] ? l++ : r--;
    }
    return best;
}

Complexity: O(n) time, O(1) space

Proof of greedy: When h[l] < h[r], any pair (l, x) where x < r has area ≤ h[l] * (x-l) < h[l] * (r-l) (already computed). So we can safely discard line l and move inward.