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 above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1] Output: 1
Constraints:
n == height.length2 <= n <= 1050 <= height[i] <= 104Problem Overview: You get an array height where each value represents the height of a vertical line. Pick two lines that, together with the x-axis, form a container holding the maximum possible water. The container area is determined by the shorter line and the distance between the two indices.
Approach 1: Brute Force (O(n2) time, O(1) space)
The straightforward approach checks every pair of lines. For each pair (i, j), compute the container area using min(height[i], height[j]) * (j - i). Iterate with two nested loops and keep track of the maximum area seen so far. This works because it evaluates all possible containers, guaranteeing the correct result. The downside is the quadratic runtime since there are n(n-1)/2 pairs to examine. This approach mainly helps build intuition for the problem before applying optimizations with techniques like two pointers.
Approach 2: Two Pointers Technique (O(n) time, O(1) space)
The optimal solution uses two pointers starting at opposite ends of the array. One pointer begins at index 0 and the other at n-1. At each step, compute the current area using the width between the pointers and the smaller height. The key insight: the container height is limited by the shorter line, so moving the taller pointer cannot increase the area. Move the pointer pointing to the shorter line inward and recompute the area. This greedy decision removes impossible candidates while still exploring all potentially better containers.
This method works because reducing width is unavoidable when moving pointers, so the only chance to increase area is by finding a taller boundary. By always discarding the shorter wall, the algorithm systematically searches for a better height while keeping the widest possible distance early in the process. The result is a single linear scan of the array using the classic array traversal pattern combined with a greedy elimination strategy.
Recommended for interviews: Interviewers expect the Two Pointers solution. The brute force method shows you understand how the area formula works and can reason about all possibilities. The optimized approach demonstrates pattern recognition and algorithmic efficiency by reducing the search from O(n2) to O(n). Many array optimization problems follow the same pattern of shrinking the search space from both ends.
The two pointers approach efficiently searches for the maximum area by starting with the widest possible container and gradually narrowing it:
This approach works due to the observation that the area is limited by the shorter line, so the only way to get a larger area is to find a taller line.
This C implementation defines a function maxArea which takes an array of heights and iteratively calculates the maximum water that can be contained using a two-pointer approach. The output is printed after calling the function.
Time Complexity: O(n), where n is the number of elements in the height array, due to the single traversal of the array.
Space Complexity: O(1) as only a few extra variables are used.
Although not optimal for large inputs, the brute force approach explores every possible pair of lines to find the maximum container area:
However, the complexity of this approach makes it unsuitable for large datasets due to its quadratic time complexity.
This brute force C implementation explores every pair of lines to find the maximum container area by calculating the area for all possible pairs.
Time Complexity: O(n^2), where n is the number of elements as each pair is checked.
Space Complexity: O(1) due to a linear amount of extra space.
We use two pointers l and r to point to the left and right ends of the array, respectively, i.e., l = 0 and r = n - 1, where n is the length of the array.
Next, we use a variable ans to record the maximum capacity of the container, initially set to 0.
Then, we start a loop. In each iteration, we calculate the current capacity of the container, i.e., min(height[l], height[r]) times (r - l), and compare it with ans, assigning the larger value to ans. Then, we compare the values of height[l] and height[r]. If height[l] < height[r], moving the r pointer will not improve the result because the height of the container is determined by the shorter vertical line, so we move the l pointer. Otherwise, we move the r pointer.
After the iteration, we return ans.
The time complexity is O(n), where n is the length of the array height. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
C
| Approach | Complexity |
|---|---|
| Approach 1: Two Pointers Technique | Time Complexity: O(n), where n is the number of elements in the height array, due to the single traversal of the array. |
| Approach 2: Brute Force | Time Complexity: O(n^2), where n is the number of elements as each pair is checked. |
| Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Useful for understanding the area calculation and verifying logic on small inputs |
| Two Pointers Technique | O(n) | O(1) | Optimal solution for large arrays; standard interview approach for this problem |
Container with Most Water - Leetcode 11 - Python • NeetCode • 526,764 views views
Watch 9 more video solutions →Practice Container With Most Water with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor