Container With Most Water — Editorial

Opening the reading…

Intuitionwhy the shorter line controls every container

A container using indices left and right has width right - left. Its water level cannot rise above the shorter line, so its area is min(height[left], height[right]) x (right - left). The widest possible container is therefore the natural place to begin, but every move inward loses width and must be justified by a possible gain in height.

Suppose height[left] is shorter than height[right]. Any container that keeps left and moves the other endpoint inward has a smaller width, while its water level is still limited by height[left]. It cannot beat the current pair. The only endpoint that might reveal a taller limiting line is left, so discard left and move it inward. The same argument applies symmetrically when the right line is shorter; when they are equal, either endpoint can be discarded.

Approach

Set left to the first index and right to the last index, because this pair has the greatest possible width and gives the scan its complete starting boundary.

Compute the current area as min(height[left], height[right]) x (right - left), because the shorter line limits the water and the distance between indices is the container width.

Update the answer with the larger of the current maximum and this area, because a pair is useful only if it stores more water than every pair checked before it.

If height[left] is less than height[right], increment left, because every pair keeping the shorter left line has less width and cannot improve on the current pair.

Otherwise decrement right, including the equal-height case, because the current right line can be discarded without losing a possible improvement; an equal-height left line can take its place only after the right endpoint moves.

Repeat while left is less than right, because equal pointers no longer define two distinct lines and every valid pair has already either been checked or proved unable to improve the result.

Return the stored maximum, because each surviving pair is evaluated before one endpoint is discarded and no discarded pair could have produced a larger area.

Complexitythe shrinking interval gives a linear scan

MEASURE	BOUND	WHY
Time	O(n)	Each iteration moves exactly one pointer inward, so the distance between the pointers decreases by one or more and there are at most n - 1 iterations. The elimination argument lets those skipped pairs remain unchecked without losing an optimum.
Space	O(1) extra	Only two indices, the current area, and the best area are stored; the returned integer is output rather than working memory. The bound stays O(1) even for the worst-shaped input, including a monotone array or an array with all equal heights.

Here n is the number of lines in height.

Annotated solutionC++ · two pointers · complete judge-ready implementation

CPPEvaluate the current container, then discard its shorter endpoint.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = static_cast<int>(height.size()) - 1;
        int best = 0;

        while (left < right) {
            int width = right - left;
            int waterLevel = min(height[left], height[right]);
            int area = waterLevel * width;
            best = max(best, area);

            if (height[left] < height[right]) {
                ++left;
            } else {
                --right;
            }
        }

        return best;
    }
};

The order inside the loop matters: calculate and record the current pair before moving a pointer, because the pair at the current boundaries is a valid candidate. The branch then applies the proof directly. The else case includes equal heights deliberately; either side is safe to discard, and choosing right keeps the update rule to one unconditional pointer move.