Container with Most Water [Medium] — Greedy Two Pointers

Problem Statement

Given n non-negative integers representing heights of walls, find two walls that together with the x-axis can contain the most water.

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

Intuition

Two pointers from ends. Water = min(h[l],h[r]) × (r-l). Moving the taller wall inward can only decrease width without increasing height — so always move the shorter wall.

Solutions

C++

int maxArea(vector<int>& height) {
    int l=0, r=height.size()-1, ans=0;
    while(l<r){
        ans=max(ans,min(height[l],height[r])*(r-l));
        height[l]<height[r]?l++:r--;
    }
    return ans;
}

Java

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

JavaScript

var maxArea = function(height) {
    let l=0, r=height.length-1, ans=0;
    while(l<r){
        ans=Math.max(ans,Math.min(height[l],height[r])*(r-l));
        if(height[l]<height[r]) l++; else r--;
    }
    return ans;
};

Python

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

Complexity

Time: O(n)
Space: O(1)