How do you approach Container With Most Water?

Use two pointers, one at each end of the array.

What is the time complexity of Container With Most Water?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on Container With Most Water?

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample. Moving both pointers on a match when only one should move, which steps over valid pairs. Choosing left < right where left <= right is meant. The first never examines the middle element.

gitGood.dev

← Back to problems

Container With Most Water

MediumAlgorithms

Description

You are given an integer array `height` of length `n`. There are `n` vertical lines drawn such that the two endpoints of the `i`th 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. **Note:** You may not slant the container.

Example 1

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

Output: 49

Explanation: The max area is between lines at index 1 and 8, with area = min(8,7) * (8-1) = 49.

Example 2

Input: height = [1,1]

Output: 1

Constraints

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

Container With Most Water: approach, complexity and pitfalls

A medium two pointers problem, graded against 6 test cases (3 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

More Two Pointersproblems →

If you are stuck

Show the 3-step hint ladder

Use two pointers, one at each end of the array.
Calculate the area between the two pointers.
Move the pointer with the smaller height inward (to potentially find a taller line).

The optimal approach

Show the approach: Two Pointers

Start with pointers at both ends. The area is limited by the shorter line, so move the shorter one inward to potentially find a better solution.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.