Container With Most Water: Two-Pointer From Ends

• Container With Most Water – given heights as vertical lines, find two lines forming the container holding the most water.
• Area formula – min(h[left], h[right]) * (right - left); water is limited by the shorter wall.
• Move-the-shorter-wall rule – always advance the pointer at the shorter line; moving the taller line cannot increase area.
• Complexity – O(n) time, O(1) space, versus O(n squared) brute force.

What is the Container With Most Water problem?

Given an array of heights representing vertical lines on the x-axis, find two lines that, together with the x-axis, form a container that holds the most water. The area between two lines is min(h[left], h[right]) * (right - left). The goal is to maximise this area.

package com.bank.dsa;

public class ContainerSolver {
    public int maxArea(int[] height) {
        // implementation below
        return 0;
    }
}

How does the two-pointer approach work?

Place a left pointer at index 0 and a right pointer at index n-1. Compute the area. Record it as the best so far. Then move the pointer at the shorter line inward. Repeat until the pointers meet.

package com.bank.dsa;

public class BalanceBandAnalyser {
    public static int maxArea(int[] heights) {
        int left = 0, right = heights.length - 1;
        int best = 0;
        while (left < right) {
            int width = right - left;
            int minHeight = Math.min(heights[left], heights[right]);
            int area = minHeight * width;
            best = Math.max(best, area);

            if (heights[left] < heights[right]) {
                left++;
            } else {
                right--;
            }
        }
        return best;
    }

    public static void main(String[] args) {
        int[] heights = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println("Max area: " + maxArea(heights));
    }
}

Max area: 49

Why move the shorter side?

The area is capped by the shorter of the two walls. If you moved the taller wall inward, the width would shrink while the height is still capped by the same shorter wall, so the area could never grow. Moving the shorter wall gives up some width but is the only chance to find a taller limiting wall that might more than compensate for the lost width.

heights[left] = 3,  heights[right] = 8
Area = min(3, 8) * width = 3 * width

Move right (taller): width shrinks, height still <= 3 --> area decreases
Move left (shorter): width shrinks, but height might be > 3 --> area MIGHT increase

Why does this not miss the optimal pair?

When you discard the shorter line by moving its pointer, every pair that still includes that shorter line as the limiting wall would have a width no larger than the current one (because we started at the maximum width). Since the height is capped by that same shorter line and the width can only be smaller, none of those pairs can beat the area we just computed. So discarding them is safe.

Correctness argument:
  Shorter wall = h[left]
  Any pair (left, j) where j < right:
    width = j - left < right - left
    height <= h[left]  (limited by shorter)
    area < current area
  So all skipped pairs are dominated by the current one.

What happens when both heights are equal?

When heights[left] == heights[right], moving either pointer is fine. Any pair between them with one of these walls is limited by the same height with a smaller width, so the area cannot improve. Some implementations move both pointers inward when they are equal, but moving just one side is also correct.

// Both correct when heights are equal:
if (heights[left] <= heights[right]) left++;
// or
if (heights[left] < heights[right]) left++; else right--;

How does this compare to brute force?

The brute force checks every pair of lines, computing each area, which is O(n squared). The two-pointer approach produces the same answer in O(n) time with O(1) extra space.

| Approach | Time | Space |
|---|---|---|
| Brute force | O(n squared) | O(1) |
| Two pointers | O(n) | O(1) |

// Brute force: O(n^2)
int best = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        int area = Math.min(h[i], h[j]) * (j - i);
        best = Math.max(best, area);
    }
}

What about using BigDecimal for financial heights?

When heights represent monetary amounts, use BigDecimal for exact arithmetic. The limiting height is determined with compareTo, and the area is computed with multiply.

package com.bank.dsa;

import java.math.BigDecimal;

public class BigDecimalContainer {
    public static BigDecimal maxArea(BigDecimal[] heights) {
        int left = 0, right = heights.length - 1;
        BigDecimal best = BigDecimal.ZERO;
        while (left < right) {
            BigDecimal h = heights[left].min(heights[right]);
            BigDecimal area = h.multiply(BigDecimal.valueOf(right - left));
            if (area.compareTo(best) > 0) best = area;
            if (heights[left].compareTo(heights[right]) < 0) left++;
            else right--;
        }
        return best;
    }
}

What are edge cases?

Edge cases include fewer than two lines (return 0), all lines of equal height (area = height * (n-1)), and a descending or ascending array (optimal pair is at the ends).

maxArea(new int[]{});          // 0
maxArea(new int[]{5});         // 0
maxArea(new int[]{5, 5, 5});   // 10 (5 * 2)
maxArea(new int[]{1, 2, 3});   // 2 (min(1,3) * 2)

What should a senior engineer know?

A senior engineer explains the correctness proof (discarding the shorter line never misses a better answer), not just the mechanics. They handle the tie case, mention the brute-force comparison, and can code it from memory. They know this is a canonical example of the greedy two-pointer pattern on unsorted data.