DSA SheetMedium
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

Container With Most Water

MediumEditorial · 6 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

A sorted-by-position array of line heights with two pointers closing inwardAn array of vertical lines is shown from left to right, with a left pointer under the first line and a right pointer under the last line. The two endpoint lines form the current container, whose height is limited by the shorter endpoint. The left endpoint is shorter, so an inward arrow moves the left pointer right while the right pointer remains fixed. The key observation is that keeping the shorter endpoint while reducing width cannot improve the area; only replacing that endpoint can help.83546274width 4 × level 5 = area 20Move the shorter boundary inward: only that move can improve the water levelshorter boundary:min(5, 7) = level 5water level = 5left @ 2 →← right @ 6discarded outside pointers: a shorter endpoint cannot improve after the width shrinks

Approach

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(1) extraOnly 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.

Common mistakesspecific ways the elimination proof gets broken

Previous · Sort Colors