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. Notice that you may not slant the container.

Key formulas to remember

• Area = min(height[left], height[right]) × (right - left)
• The minimum height is the bottleneck — water can only be as tall as the shorter wall
• Key greedy insight: if we move the taller pointer inward, width decreases AND the height stays the same or worse → always move the shorter pointer

Examples

Input	Output
[1,8,6,2,5,4,8,3,7]	49 (between index 1 and 8: min(8,7)*7=49)
[1,1]	1

Constraints

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

Real-World Applications

Where this pattern appears

• Water reservoir design — choose two dam heights to maximize water storage
• Histogram max rectangle — similar greedy reasoning (see #84)
• Antenna placement — maximize signal reception area between two towers
• Profit optimization — maximize revenue = min(supply, demand) × time_gap

Complexity Comparison

Approach	Time	Space	Best When
Two Pointers	O(n)	O(1)	Always — this is the optimal solution
Brute Force	O(n²)	O(1)	Understanding only

Approach 1: Two Pointers (Recommended)

★ Recommended

⏱ Time O(n) 💾 Space O(1)

Start with the widest possible container — left pointer at index 0, right pointer at index n-1. At each step, compute the current area. Then move the pointer pointing to the shorter wall inward; keeping the taller pointer would only decrease width without any chance of a taller container.

Greedy proof: Suppose height[left] < height[right]. Moving right inward:

• Width decreases by 1
• New height = min(height[left], height[new_right]) ≤ height[left] — the left wall still caps the height
• So area can only decrease or stay the same → moving the taller pointer is never optimal
• Therefore, always move the SHORTER pointer

Step-by-step Example

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

step	left	h[l]	right	h[r]	width	area	max	move
1	0	1	8	7	8	8	8	left++ (shorter)
2	1	8	8	7	7	49	49	right—
3	1	8	7	3	6	18	49	right—
4	1	8	6	8	5	40	49	left++ (tie)
…	…	…	…	…	…	…	…	…

Animated walkthrough

Two-pointer walk — tracking max area

Use Next or Autoplay to watch the left and right pointers converge, and see how the max area is updated.

Back Autoplay Next Reset

Step 1 of 4

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function maxArea(height):
    left, right = 0, len(height) - 1
    max_water = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        max_water = max(max_water, water)
        if height[left] <= height[right]:
            left++
        else:
            right--
    return max_water

Solution Code

Python

container_with_most_water_two_pointer.py

"""
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.

Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The vertical lines are drawn at the above positions. The maximum area is
obtained between index 1 and index 8: min(8,7) * (8-1) = 49.

Example 2:
Input: height = [1,1]
Output: 1
"""


# Approach: Two Pointers
# Place one pointer at the start and one at the end. The area is min(height[left], height[right]) * (right - left).
# Always move the pointer with the shorter height inward — the shorter wall is the bottleneck,
# so moving the taller pointer can only decrease or maintain the area.

# Time Complexity: O(n) — single pass
# Space Complexity: O(1)

from typing import List


def max_area(height: List[int]) -> int:
    left, right = 0, len(height) - 1
    max_water = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        max_water = max(max_water, water)
        if height[left] <= height[right]:
            left += 1
        else:
            right -= 1
    return max_water


print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
print(max_area([1, 1]))                         # 1

C++

container_with_most_water_two_pointer.cpp

#include <iostream>
#include <vector>
#include <algorithm>

// Approach: Two Pointers
// Place one pointer at the start and one at the end.
// Area = min(height[left], height[right]) * (right - left).
// Move the pointer with the shorter height inward — the shorter wall is the bottleneck.
//
// Time Complexity: O(n)
// Space Complexity: O(1)

int maxArea(std::vector<int>& height) {
    int left = 0;
    int right = static_cast<int>(height.size()) - 1;
    int maxWater = 0;
    while (left < right) {
        int water = std::min(height[left], height[right]) * (right - left);
        maxWater = std::max(maxWater, water);
        if (height[left] <= height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}

int main() {
    std::vector<int> height1 = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    std::cout << maxArea(height1) << std::endl; // 49

    std::vector<int> height2 = {1, 1};
    std::cout << maxArea(height2) << std::endl; // 1

    return 0;
}

Java

container_with_most_water_two_pointer.java

// Approach: Two Pointers
// Place one pointer at the start and one at the end.
// Area = min(height[left], height[right]) * (right - left).
// Move the pointer with the shorter height inward — the shorter wall is the bottleneck.
//
// Time Complexity: O(n)
// Space Complexity: O(1)

public class Main {
    public static int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxWater = 0;
        while (left < right) {
            int water = Math.min(height[left], height[right]) * (right - left);
            maxWater = Math.max(maxWater, water);
            if (height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxWater;
    }

    public static void main(String[] args) {
        System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // 49
        System.out.println(maxArea(new int[]{1, 1}));                       // 1
    }
}

JavaScript

container_with_most_water_two_pointer.js

// Approach: Two Pointers
// Place one pointer at the start and one at the end.
// Area = Math.min(height[left], height[right]) * (right - left).
// Move the pointer with the shorter height inward — the shorter wall is the bottleneck.
//
// Time Complexity: O(n)
// Space Complexity: O(1)

function maxArea(height) {
    let left = 0;
    let right = height.length - 1;
    let maxWater = 0;
    while (left < right) {
        const water = Math.min(height[left], height[right]) * (right - left);
        maxWater = Math.max(maxWater, water);
        if (height[left] <= height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49
console.log(maxArea([1, 1]));                        // 1

Rust

container_with_most_water_two_pointer.rs

// Approach: Two Pointers
// Place one pointer at the start and one at the end.
// Area = min(height[left], height[right]) * (right - left).
// Move the pointer with the shorter height inward — the shorter wall is the bottleneck.
//
// Time Complexity: O(n)
// Space Complexity: O(1)

fn max_area(height: &[i32]) -> i32 {
    let mut left = 0usize;
    let mut right = height.len() - 1;
    let mut max_water = 0i32;
    while left < right {
        let water = height[left].min(height[right]) * (right - left) as i32;
        max_water = max_water.max(water);
        if height[left] <= height[right] {
            left += 1;
        } else {
            right -= 1;
        }
    }
    max_water
}

fn main() {
    println!("{}", max_area(&[1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49
    println!("{}", max_area(&[1, 1]));                        // 1
}

Go

container_with_most_water_two_pointer.go

package main

import "fmt"

// Approach: Two Pointers
// Place one pointer at the start and one at the end.
// Area = min(height[left], height[right]) * (right - left).
// Move the pointer with the shorter height inward — the shorter wall is the bottleneck.
//
// Time Complexity: O(n)
// Space Complexity: O(1)

func maxArea(height []int) int {
    left := 0
    right := len(height) - 1
    maxWater := 0
    for left < right {
        h := height[left]
        if height[right] < h {
            h = height[right]
        }
        water := h * (right - left)
        if water > maxWater {
            maxWater = water
        }
        if height[left] <= height[right] {
            left++
        } else {
            right--
        }
    }
    return maxWater
}

func main() {
    fmt.Println(maxArea([]int{1, 8, 6, 2, 5, 4, 8, 3, 7})) // 49
    fmt.Println(maxArea([]int{1, 1}))                        // 1
}

Approach 2: Brute Force

✓ Simple

⏱ Time O(n²) 💾 Space O(1)

Check every possible pair of lines using two nested loops. For each pair (i, j), compute area = min(height[i], height[j]) * (j - i) and track the maximum. Simple to understand but too slow for large inputs.

Step-by-step Example

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

i	j	h[i]	h[j]	width	area	max
0	1	1	8	1	1	1
0	2	1	6	2	2	2
…	…	…	…	…	…	…
1	8	8	7	7	49	49
…	…	…	…	…	…	…

Pseudocode

function maxAreaBruteForce(height):
    n = len(height)
    max_water = 0
    for i in range(n):
        for j in range(i + 1, n):
            water = min(height[i], height[j]) * (j - i)
            max_water = max(max_water, water)
    return max_water

Solution Code

Python

container_with_most_water_brute_force.py

"""
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.

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

Example 2:
Input: height = [1,1]
Output: 1
"""


# Approach: Brute Force
# Try every pair (i, j). Area = min(height[i], height[j]) * (j - i). Track the maximum.

# Time Complexity: O(n^2)
# Space Complexity: O(1)

from typing import List


def max_area_brute_force(height: List[int]) -> int:
    n = len(height)
    max_water = 0
    for i in range(n):
        for j in range(i + 1, n):
            water = min(height[i], height[j]) * (j - i)
            max_water = max(max_water, water)
    return max_water


print(max_area_brute_force([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
print(max_area_brute_force([1, 1]))                         # 1

C++

container_with_most_water_brute_force.cpp

#include <iostream>
#include <vector>
#include <algorithm>

// Approach: Brute Force
// Try every pair (i, j). Area = min(height[i], height[j]) * (j - i). Track the maximum.
//
// Time Complexity: O(n^2)
// Space Complexity: O(1)

int maxAreaBruteForce(std::vector<int>& height) {
    int n = static_cast<int>(height.size());
    int maxWater = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int water = std::min(height[i], height[j]) * (j - i);
            maxWater = std::max(maxWater, water);
        }
    }
    return maxWater;
}

int main() {
    std::vector<int> height1 = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    std::cout << maxAreaBruteForce(height1) << std::endl; // 49

    std::vector<int> height2 = {1, 1};
    std::cout << maxAreaBruteForce(height2) << std::endl; // 1

    return 0;
}

Java

container_with_most_water_brute_force.java

// Approach: Brute Force
// Try every pair (i, j). Area = min(height[i], height[j]) * (j - i). Track the maximum.
//
// Time Complexity: O(n^2)
// Space Complexity: O(1)

public class Main {
    public static int maxAreaBruteForce(int[] height) {
        int n = height.length;
        int maxWater = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int water = Math.min(height[i], height[j]) * (j - i);
                maxWater = Math.max(maxWater, water);
            }
        }
        return maxWater;
    }

    public static void main(String[] args) {
        System.out.println(maxAreaBruteForce(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // 49
        System.out.println(maxAreaBruteForce(new int[]{1, 1}));                       // 1
    }
}

JavaScript

container_with_most_water_brute_force.js

// Approach: Brute Force
// Try every pair (i, j). Area = Math.min(height[i], height[j]) * (j - i). Track the maximum.
//
// Time Complexity: O(n^2)
// Space Complexity: O(1)

function maxAreaBruteForce(height) {
    const n = height.length;
    let maxWater = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const water = Math.min(height[i], height[j]) * (j - i);
            maxWater = Math.max(maxWater, water);
        }
    }
    return maxWater;
}

console.log(maxAreaBruteForce([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49
console.log(maxAreaBruteForce([1, 1]));                        // 1

Rust

container_with_most_water_brute_force.rs

// Approach: Brute Force
// Try every pair (i, j). Area = min(height[i], height[j]) * (j - i). Track the maximum.
//
// Time Complexity: O(n^2)
// Space Complexity: O(1)

fn max_area_brute_force(height: &[i32]) -> i32 {
    let n = height.len();
    let mut max_water = 0i32;
    for i in 0..n {
        for j in (i + 1)..n {
            let water = height[i].min(height[j]) * (j - i) as i32;
            max_water = max_water.max(water);
        }
    }
    max_water
}

fn main() {
    println!("{}", max_area_brute_force(&[1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49
    println!("{}", max_area_brute_force(&[1, 1]));                        // 1
}

Go

container_with_most_water_brute_force.go

package main

import "fmt"

// Approach: Brute Force
// Try every pair (i, j). Area = min(height[i], height[j]) * (j - i). Track the maximum.
//
// Time Complexity: O(n^2)
// Space Complexity: O(1)

func maxAreaBruteForce(height []int) int {
    n := len(height)
    maxWater := 0
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            h := height[i]
            if height[j] < h {
                h = height[j]
            }
            water := h * (j - i)
            if water > maxWater {
                maxWater = water
            }
        }
    }
    return maxWater
}

func main() {
    fmt.Println(maxAreaBruteForce([]int{1, 8, 6, 2, 5, 4, 8, 3, 7})) // 49
    fmt.Println(maxAreaBruteForce([]int{1, 1}))                        // 1
}

Approach 3: Optimized Two-Pointer

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

container_with_most_water_optimized.py

"""
Solution for Container With Most Water
"""

def solve():
    """Implementation for approach 3 of Container With Most Water"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

container_with_most_water_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Container With Most Water
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

ContainerWithMostWaterOptimized.java

/**
 * Solution for Container With Most Water
 * Approach 3
 */
public class ContainerWithMostWaterOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

container_with_most_water_optimized.js

/**
 * Solution for Container With Most Water
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

container_with_most_water_optimized.rs

/// Solution for Container With Most Water
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

container_with_most_water_optimized.go

package main

import "fmt"

// Solution for Container With Most Water
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Moving the wrong pointer — always move the pointer with the shorter height, not the taller one
• Using (j - i) as the height instead of min(height[i], height[j]) — the width is j - i, not the height
• Forgetting that water height is limited by the SHORTER of the two walls

Related Problems

• Trapping Rain Water ↗ Hard #42
• 3Sum ↗ Medium #15
• Largest Rectangle in Histogram ↗ Hard #84

Interview Tips

Key points to discuss

• State the greedy proof immediately: “Moving the taller pointer can never improve the area — the shorter wall is always the bottleneck”
• This is O(n) which is optimal — any algorithm must consider each line at least once
• Common follow-up: “Can you prove the two-pointer never misses the optimal pair?” → yes, because we only discard pairs that are guaranteed suboptimal (any pair involving the shorter pointer with anything between the pointers produces a smaller area)

← Previous
#9 Palindrome Number Next
#15 3Sum →