11. Container With Most Water

← All Problems
medium Arrays & Two Pointers
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container that holds the most water. Return the maximum amount of water the container can store. You may not slant the container.

Example

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

Output: 49

The lines at index 1 (height 8) and index 8 (height 7) form the largest container. The water height is limited by the shorter line (7), and the width is 8 - 1 = 7, giving area 7 * 7 = 49.

Place two pointers at the far left and far right of the array. The area of water is limited by the shorter line, so calculate the area and then move the shorter pointer inward — moving the taller one could never help since the height is already bottlenecked by the shorter side. This greedy choice guarantees you never miss the optimal pair.

Why this works

Area = min(height[left], height[right]) * width. Starting with maximum width (pointers at both ends), you greedily move the shorter pointer inward. Moving the taller pointer can never increase the area because the bottleneck is the shorter side and the width is shrinking.

Step by step

  1. Start wide — place pointers at the leftmost and rightmost lines for maximum width.
  2. Calculate area — use the shorter line as the height, multiplied by the distance between pointers.
  3. Move the shorter pointer — the shorter line limits the area, so move it inward hoping to find a taller one.
  4. Repeat until pointers meet — track the maximum area seen across all iterations.
Time: O(n) Space: O(1) 
class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        while (left < right) {
            int area = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, area);
            if (height[left] < height[right]) {
                left++;   // move shorter side inward to try for a taller line
            } else {
                right--;  // move shorter side inward to try for a taller line
            }
        }
        return maxArea;
    }
}

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int maxArea = 0;
        while (left < right) {
            int area = min(height[left], height[right]) * (right - left);
            maxArea = max(maxArea, area);
            if (height[left] < height[right]) {
                left++;   // move shorter side inward to try for a taller line
            } else {
                right--;  // move shorter side inward to try for a taller line
            }
        }
        return maxArea;
    }
};

def maxArea(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    max_area = 0
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)
        if height[left] < height[right]:
            left += 1   # move shorter side inward to try for a taller line
        else:
            right -= 1  # move shorter side inward to try for a taller line
    return max_area