Container With Most Water

medium array two pointers greedy

Problem

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water. Notice that you may not slant the container.

Inputheights = [3, 1, 4, 6, 2, 5]

Output15

Lines at indices 2 and 5 give width 3 × min(4, 5) = 12. Lines at 0 and 5 give 5 × 3 = 15, the best.

heights (comma-separated, non-negative)

def max_area(h):
    l, r = 0, len(h) - 1
    best = 0
    while l < r:
        area = (r - l) * min(h[l], h[r])
        if area > best:
            best = area
        if h[l] < h[r]:
            l += 1
        else:
            r -= 1
    return best

function maxArea(h) {
  let l = 0, r = h.length - 1;
  let best = 0;
  while (l < r) {
    const area = (r - l) * Math.min(h[l], h[r]);
    if (area > best) best = area;
    if (h[l] < h[r]) l++; else r--;
  }
  return best;
}

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

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

Explanation

The water a container holds is width × height, where the width is the distance between two walls and the height is the shorter of the two walls. Checking every pair of walls works but is slow, so this solution uses two pointers closing in from both ends.

Start with l at the far left and r at the far right. That gives the widest possible container. At each step compute the area (r - l) * min(h[l], h[r]) and keep the largest seen in best.

The key move: always step the pointer at the shorter wall inward. Moving the taller wall can never help, because the height is capped by the short wall and the width only shrinks. Only the short wall has any chance of being replaced by something taller.

Example: heights = [3, 1, 4, 6, 2, 5]. At first l=0 (height 3), r=5 (height 5): area = 5 * 3 = 15. Since the left wall is shorter, move l right. We keep shrinking the width but searching for taller short-walls, and 15 turns out to be the best.

Because each step moves one pointer inward, we scan the array a single time, giving fast O(n) performance.

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