Skip to main content

11. Container With Most Water

medium

Given heights along a number line, pick two lines so the rectangle between them holds the most water. The canonical two-pointer-with-greedy-shrink problem.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container.

Constraints

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

Examples

Example 1

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

Explanation: The lines at indices 1 and 8 (heights 8 and 7) form the container with the most water: 7 * 7 = 49.

Example 2

Input
height = [1,1]
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force is every pair: O(n^2). For 10^5 that's 10^10 ops — way too slow.

Hint 2

Place two pointers at the ends. The width is largest possible. The height is bounded by min(left, right).

Hint 3

Move the shorter side inward. The wider container shrinks, but only the shorter line had a chance to ever increase the area — moving the taller side can never help unless the height grows.

Solution approach

Reveal approach

Two pointers, one at index 0 and one at index n-1. Compute the current area = (right - left) * min(height[left], height[right]) and track the max. Then move the pointer pointing at the SHORTER line inward by one. The reasoning: the width strictly decreases with every move, so the only way to find a larger area is to find a taller minimum height — and moving the taller side can only ever match or reduce the bounding min, while moving the shorter side at least has a chance to find something taller. Continue until the pointers meet.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • two-pointers

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Microsoft
  • Bloomberg

More Arrays practice problems

See all Arrays problems →