Coding problem · Medium · Two Pointers

Container With Most Water

Medium Algorithms & data structures Seen at Amazon, Google, Goldman Sachs

You are given an array height where height[i] is the height of a vertical line at position i. Find two lines that, together with the x-axis, form a container holding the most water, and return that maximum area.

Example 1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

Example 2

Input: height = [1,1]
Output: 1

Constraints

2 <= height.length <= 10^5

Hints

Hint 1

Start with the widest container (both ends).

Hint 2

Moving the taller line inward can never help — always move the shorter one.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1)

Area = width × min(left, right). Starting from the widest pair, the shorter side limits the area; moving the taller side inward only shrinks width without raising the limit, so move the shorter side. One pass, O(n).

Reference solution

function maxArea(height) {
  let i = 0, j = height.length - 1, best = 0;
  while (i < j) {
    best = Math.max(best, (j - i) * Math.min(height[i], height[j]));
    if (height[i] < height[j]) i++;
    else j--;
  }
  return best;
}

function maxArea(height: number[]): number {
  let i = 0, j = height.length - 1, best = 0;
  while (i < j) {
    best = Math.max(best, (j - i) * Math.min(height[i], height[j]));
    if (height[i] < height[j]) i++;
    else j--;
  }
  return best;
}

def max_area(height: list[int]) -> int:
    i, j, best = 0, len(height) - 1, 0
    while i < j:
        best = max(best, (j - i) * min(height[i], height[j]))
        if height[i] < height[j]:
            i += 1
        else:
            j -= 1
    return best

<?php

function maxArea(array $height): int
{
    [$i, $j, $best] = [0, count($height) - 1, 0];
    while ($i < $j) {
        $best = max($best, ($j - $i) * min($height[$i], $height[$j]));
        if ($height[$i] < $height[$j]) {
            $i++;
        } else {
            $j--;
        }
    }
    return $best;
}

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, best = 0;
        while (i < j) {
            best = Math.max(best, (j - i) * Math.min(height[i], height[j]));
            if (height[i] < height[j]) i++; else j--;
        }
        return best;
    }
}

Valid Palindrome · Easy
3Sum · Medium