ToolMight LogoToolMight
MediumTwo PointersPattern: Two Pointers Inward ConvergencePattern: Greedy Area Maximization

Container With Most Water

Find two vertical lines that together with the x-axis form a container holding the maximum amount of water. The premier problem for learning two-pointer greedy bottleneck elimination.

Problem Statement

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.

Examples & Constraints

Example 1
Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: The vertical lines are at index 1 (height 8) and index 8 (height 7). Width is (8 - 1) = 7. Water capacity is min(8, 7) * 7 = 49.
Example 2
Input: height = [1, 1]
Output: 1
Explanation: Width is (1 - 0) = 1. Height is min(1, 1) = 1. Area is 1 * 1 = 1.
Constraints
  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

Two Pointers Greedy Inward Scan

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

Start with pointers at both extremes (maximum width). At each step, calculate area and move the pointer with the smaller height inward to potentially find a taller bottleneck in O(n) time.

Time ComplexityO(n)

Each iteration moves either the left or right pointer by one position inward. The loop runs at most N - 1 times.

Space ComplexityO(1)

Operates strictly in-place with two integer index variables and a running maximum variable.

Underlying algorithmic logic

The Mathematical Formula

The volume of water between two vertical lines at indices left and right is:
area = (right - left) * min(height[left], height[right])

Here, (right - left) is the width, and the shorter line is the limiting bottleneck.

The Greedy Choice: Why Discard the Shorter Line?

Suppose height[left] < height[right]:

  • If we keep left and move right inward to right - 1, the width will decrease by 1.
  • What about the height? The new height is bounded by min(height[left], height[right - 1]), which can never exceed height[left].
  • Decreased width equal or smaller height = strictly smaller area*!

Therefore, keeping the shorter line left while moving right inward can never yield a larger area than what we have already evaluated. We can safely discard left and advance left++!

By moving the pointer at the shorter line inward at every step:

  1. We start with the maximum possible width (left = 0, right = n - 1).
  2. We evaluate the current area and update maxArea.
  3. We advance the pointer with the smaller height.
  4. When left >= right, we have proven that no container can exceed maxArea.

Step-by-step execution walkthrough

1
Initial Boundaries

left = 0 (height 1), right = 8 (height 7). Width = 8. Area = min(1, 7) * 8 = 8. maxArea = 8.

left = 0 (1), right = 8 (7) -> area: 8
2
Discard Shorter (Left)

height[0] (1) < height[8] (7). Discard index 0. Advance left to 1 (height 8).

left = 1 (8), right = 8 (7)
3
New Maximum Candidate

Width = 8 - 1 = 7. Area = min(8, 7) * 7 = 49. New maxArea = 49!

maxArea updated to 49
4
Continue Inward

height[8] (7) < height[1] (8). Decrement right to 7 (height 3). Width continues shrinking.

right decrements to 7
Advantages
  • •Optimal O(n) single pass runtime
  • •O(1) auxiliary space without mutating the input
Trade-offs
  • •Greedy elimination proof can be unintuitive to prove during interview without width/height bounding logic

Code Implementations

Copy & paste production-ready solutions for Two Pointers Greedy Inward Scan in your language of choice

File: solution.py
Python
def max_area(height: list[int]) -> int:
    left = 0
    right = len(height) - 1
    max_water = 0
    while left < right:
        current_width = right - left
        current_height = min(height[left], height[right])
        current_water = current_width * current_height
        if current_water > max_water:
            max_water = current_water
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water
if __name__ == "__main__":
    test1 = [1, 8, 6, 2, 5, 4, 8, 3, 7]
    test2 = [1, 1]
    print("test1 max area:", max_area(test1))
    print("test2 max area:", max_area(test2))
Interactive visualizer available

Understand Array & Matrix Visually

Explore sequential element access, subsegment manipulations, insertion, deletion, and 2D grid matrix walks. Test live edge cases and watch memory state transitions step-by-step.

Launch Array & Matrix Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
MediumTwo Pointers
Visualizer

3Sum

Find all unique triplets in an array that sum up to zero. The premier problem for learning how to combine sorting with two-pointer inward scans to avoid cubic brute force.

1 approach(O(n²))
Learn logic
EasyTwo Pointers
Visualizer

Valid Palindrome

Determine if a string is a palindrome considering only alphanumeric characters and ignoring case. The canonical problem for learning the two-pointer inward convergence technique.

1 approach(O(n))
Learn logic
HardTwo Pointers
Visualizer

Trapping Rain Water

Given an elevation map where width of each bar is 1, compute how much water it can trap after raining. The classic masterclass in two-pointer bottleneck derivation.

1 approach(O(n))
Learn logic