Container With Most Water

MediumTwo Pointers

Given heights of vertical lines, pick two lines that with the x-axis form a container holding the most water. Return that maximum area.

Open problem

Constraints

2 <= height.length <= 10^5
0 <= height[i] <= 10^4

Two pointers inward

Time O(n)Space O(1)

Start with the widest container using the outermost lines. The area is limited by the shorter line, so move the shorter pointer inward hoping for a taller line; moving the taller one could never increase the area.

#include <bits/stdc++.h>
using namespace std;

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