Container With Most Water

Q: How do you solve Container With Most Water?

Use two pointers at the start and end of the array. Calculate area, update max area, then move the pointer at the shorter line inward. Repeat until pointers meet. This guarantees O(n) time and O(1) space.

Q: What is the time complexity of Container With Most Water?

O(n). Each pointer moves inward at most n times, resulting in a single pass through the array.

Q: What pattern does Container With Most Water use?

The Pattern: Two Pointers (Greedy Contraction) The Heuristic: The logic of any optimal Two Pointers solution lies in finding the condition that allows you to permanently discard one end of the search space by moving the pointer that is the current 'limiting factor' to the solution.

Medium Two Pointers

Problem

Given an array of integers height representing vertical lines, return the maximum amount of water a container can store formed between two lines and the x-axis.

2 ≤ height.length ≤ 10⁵
0 ≤ height[i] ≤ 10⁴

Example

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

Output: 49

Starting with pointers at the outermost lines (indices 0 and 8), the container width is 8 and the limiting height is min(1,7) = 1, so area = 8 * 1 = 8. Since height[0] < height[8], move left pointer inward to index 1. Now width is 7, limiting height min(8,7) = 7, area = 49, which is larger. Continue moving pointers inward, always moving the pointer at the shorter line, updating the max area. The maximum area found is 49.

Approach

Straightforward Solution

A brute-force approach checks all pairs of lines, calculating area for each, resulting in O(n^2) time complexity, which is too slow for large inputs.

Core Observation

The container's area is determined by the width between two lines and the height of the shorter line. Maximizing area requires balancing these two factors.

Path to Optimal

Preview

Starting with the widest container (outermost lines), the key insight is that moving the pointer at the taller line inward cannot increase area because width decreases and height is limited by the shorter line…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers at the start and end of the array. Calculate area, update max area, then move the pointer at the shorter line inward…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each pointer moves inward at most n times, resulting in a single pass through the array.

Space

O(1)

Only a fixed number of variables are used regardless of input size.

Pattern Spotlight

Two Pointers (Greedy Contraction)

The logic of any optimal Two Pointers solution lies in finding the condition that allows you to permanently discard one end of the search space by moving the pointer that is the current 'limiting factor' to the solution.

Solution

Python

1class Solution:
  def maxArea(self, height: list[int]) -> int:
      l, r = 0, len(height) - 1
      max_area = 0
5
      while l < r:
          area = (r - l) * min(height[l], height[r])
          max_area = max(max_area, area)
9
          if height[l] < height[r]:
              l += 1
          else:
              r -= 1
      
      return max_area

Step-by-Step Solution

Initialize Two Pointers and Maximum Area

3l, r = 0, len(height) - 1
4max_area = 0

Objective

To set up pointers at both ends of the array and initialize the variable to track the maximum area found.

Key Insight

Starting with pointers at the extreme ends ensures the widest possible container, providing a baseline for comparison. Initializing max_area to zero prepares to track the best solution found during iteration.

Interview Quick-Check

Core Logic

Pointers at indices 0 and len(height) - 1 represent the widest container possible at the start.

State & Boundaries

Initialize max_area to zero to correctly handle cases where all heights might be zero.

Iteratively Calculate Area and Move Limiting Pointer

To calculate the container area at the current pointers, update the maximum area, and move the pointer at the shorter line inward to explore potentially larger areas.

Return the Maximum Area Found

To return the maximum container area found after all pointer movements are complete.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 11 Critical

l += 1

Move the left pointer inward if its line is shorter.

This is the critical greedy step: moving the pointer at the shorter line is the only move that can potentially increase the container area because the area is limited by the shorter line; moving the taller line's pointer cannot increase area as width decreases without increasing height.

Line 12 Critical

else:

Move the right pointer inward if its line is shorter or equal.

Moving the right pointer inward when its height is less than or equal to the left pointer maintains the greedy strategy of discarding the limiting factor, enabling exploration of potentially taller lines and larger areas.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

Why is it always optimal to move the pointer at the shorter line inward?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Container With Most Water from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Container With Most Water drill

or drill a free problem

1	`class Solution:`
2	`def maxArea(self, height: list[int]) -> int:`
3	`l, r = 0, len(height) - 1`
4	`max_area = 0`
5
6	`while l < r:`
7	`area = (r - l) * min(height[l], height[r])`
8	`max_area = max(max_area, area)`
9
10	`if height[l] < height[r]:`
11	`l += 1`
12	`else:`
13	`r -= 1`
14
15	`return max_area`