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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Container With Most Water and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →