Container With Most Water

Mediumtwo-pointersarraygreedy
Category: Two Pointers
Companies that ask this question:
AmazonFacebookBloombergGoogle
LeetCode →NeetCode →

Approach

Container With Most Water

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.

Note: You may not slant the container.

Examples

Example 1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The vertical lines are at positions 0-8. The max area is between
lines at indices 1 and 8: min(8,7) * (8-1) = 7 * 7 = 49.

Example 2

Input: height = [1,1]
Output: 1

Intuition

The water contained between two lines is determined by:

  • Width: Distance between the two lines
  • Height: The shorter of the two lines (water spills over the shorter line)

Formula: area = min(height[left], height[right]) * (right - left)

The key insight is that we start with maximum width and greedily move the pointer at the shorter line inward, hoping to find a taller line that increases the area despite losing width.

Pattern Recognition

This is a Two Pointers pattern with Greedy strategy:

  • Start with widest container (maximum width)
  • Always move the pointer at the shorter line
  • This greedy choice is optimal because moving the taller line can only decrease area

Approach

  1. Initialize Pointers: left = 0, right = n - 1 (widest possible container)
  2. Track Maximum: Keep track of maxArea
  3. Calculate Area: area = min(height[left], height[right]) * (right - left)
  4. Update Maximum: maxArea = max(maxArea, area)
  5. Move Pointer:
    • If height[left] < height[right]: move left++
    • Else: move right--
  6. Repeat: Until left >= right

Why This Works:

  • Moving the shorter line might find a taller line
  • Moving the taller line will definitely result in a shorter or equal height
  • Width decreases with each move, so we need height to increase

Edge Cases

  • Array with only 2 elements (minimum case)
  • All lines have the same height
  • Lines in ascending or descending order
  • Very tall line at one end

Complexity Analysis

  • Time Complexity: O(n) where n is the length of height array
    • Single pass with two pointers
    • Each pointer moves at most n times
  • Space Complexity: O(1)
    • Only using a few variables for tracking

Solution

java
1class Solution {
2    public int maxArea(int[] height) {
3        int maxArea = 0;
4        int left = 0;
5        int right = height.length - 1;
6
7        while (left < right) {
8            // Calculate area with current pointers
9            int width = right - left;
10            int currentHeight = Math.min(height[left], height[right]);
11            int area = width * currentHeight;
12
13            // Update maximum area
14            maxArea = Math.max(maxArea, area);
15
16            // Move pointer at shorter line (greedy choice)
17            if (height[left] < height[right]) {
18                left++;
19            } else {
20                right--;
21            }
22        }
23
24        return maxArea;
25    }
26}
27
Loading visualizer...