Container With Most Water

medium
Two PointersArrayTwo PointersGreedy

Given an integer array height of length n, find two lines that together with the x-axis form a container that holds the most water. Return the maximum amount of water a container can store.

You are given n vertical lines drawn at positions 1 through n where the ith line has a height of height[i]. Choose two lines such that the container they form holds the maximum area of water. Notice that you may not slant the container.

Examples

Example 1

  • Input: height = [1,8,6,2,5,4,8,3,7]
  • Output: 49
  • Explanation: The lines at index 1 (height 8) and index 8 (height 7) form a container with area min(8, 7) * (8 - 1) = 49.

Example 2

  • Input: height = [1,1]
  • Output: 1
  • Explanation: The two lines form a container with area min(1, 1) * (1 - 0) = 1.

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Brute Force

Intuition

The simplest approach is to consider every possible pair of lines and compute the area formed between them. For each pair (i, j), the width is j - i and the height is the minimum of the two line heights. We track the maximum area seen across all pairs. This guarantees we find the optimal answer but runs in quadratic time.

Algorithm

  1. Initialize a variable maxArea to 0.
  2. Use two nested loops to consider every pair of indices (i, j) where i < j.
  3. For each pair, calculate the area as min(height[i], height[j]) * (j - i).
  4. Update maxArea if the current area is larger.
  5. Return maxArea after checking all pairs.
TimeO(n^2)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int n = height.size();

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int area = min(height[i], height[j]) * (j - i);
                maxArea = max(maxArea, area);
            }
        }

        return maxArea;
    }
};
Java 21
class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int n = height.length;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int area = Math.min(height[i], height[j]) * (j - i);
                maxArea = Math.max(maxArea, area);
            }
        }

        return maxArea;
    }
}
Python 3.12
def maxArea(height: list[int]) -> int:
    max_area = 0
    n = len(height)

    for i in range(n):
        for j in range(i + 1, n):
            area = min(height[i], height[j]) * (j - i)
            max_area = max(max_area, area)

    return max_area
Go 1.26
func maxArea(height []int) int {
    maxArea := 0
    n := len(height)

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            h := min(height[i], height[j])
            area := h * (j - i)
            if area > maxArea {
                maxArea = area
            }
        }
    }

    return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
Approach 2

Two Pointers

Intuition

We can solve this in linear time using two pointers starting at both ends of the array. The key insight is that the area is limited by the shorter line. If we move the pointer at the taller line inward, the width decreases and the height cannot increase beyond the shorter line, so the area can only decrease or stay the same. Therefore, we should always move the pointer at the shorter line inward, hoping to find a taller line that could increase the area.

Algorithm

  1. Place a left pointer at index 0 and a right pointer at index n - 1.
  2. Calculate the area between the two pointers: min(height[left], height[right]) * (right - left).
  3. Update the maximum area if the current area is larger.
  4. Move the pointer pointing to the shorter line inward (if heights are equal, move either one).
  5. Repeat until the two pointers meet.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int left = 0, right = height.size() - 1;

        while (left < right) {
            int area = min(height[left], height[right]) * (right - left);
            maxArea = max(maxArea, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
};
Java 21
class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int left = 0, right = height.length - 1;

        while (left < right) {
            int area = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
}
Python 3.12
def maxArea(height: list[int]) -> int:
    max_area = 0
    left, right = 0, len(height) - 1

    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area
Go 1.26
func maxArea(height []int) int {
    maxArea := 0
    left, right := 0, len(height)-1

    for left < right {
        h := height[left]
        if height[right] < h {
            h = height[right]
        }
        area := h * (right - left)
        if area > maxArea {
            maxArea = area
        }

        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }

    return maxArea
}

Frequently asked questions

What is the optimal time complexity of Container With Most Water?

The most efficient approach in this guide ("Two Pointers") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Container With Most Water use?

Container With Most Water is a medium-level Two Pointers problem involving Array, Two Pointers, Greedy. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Container With Most Water be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
height=
[1,8,6,2,5,4,8,3,7]
Expected Output
49