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 receive an array height where each element represents a vertical line on the x-axis. Pick two lines that, together with the x-axis, form a container that holds the maximum possible water. The area depends on the distance between the lines and the smaller of the two heights.
Approach 1: Brute Force (O(n2) time, O(1) space)
The straightforward strategy checks every possible pair of lines. Use two nested loops: the first pointer i selects the left boundary, and the second pointer j selects the right boundary. For each pair, compute the container area using min(height[i], height[j]) * (j - i). Track the maximum area seen so far while iterating. This approach directly follows the problem definition and helps verify correctness during early implementation. The downside is performance: evaluating all pairs leads to quadratic time complexity O(n2) while still using constant extra space O(1). Works for small arrays but becomes slow when n grows.
Approach 2: Two Pointers Technique (O(n) time, O(1) space)
The optimal solution relies on a greedy observation. Start with two pointers at the extreme ends of the array: left = 0 and right = n - 1. This pair gives the maximum possible width. Compute the area formed by these two lines. Then move the pointer pointing to the shorter line inward. The reasoning: the container height is limited by the shorter wall, so moving the taller wall cannot increase area while the width shrinks. Only moving the shorter wall might reveal a taller boundary that increases the area despite reduced width. Continue this process until the pointers meet. Each step performs constant work, so the entire scan runs in O(n) time with O(1) extra space.
This pattern appears frequently in Array problems where two indices converge while preserving an optimal candidate. The decision rule for pointer movement makes the solution greedy, and the structure fits the classic Two Pointers technique. The insight that the shorter boundary limits the area is the key greedy property, making the approach closely related to Greedy reasoning.
Recommended for interviews: Interviewers expect the two-pointer solution. The brute force approach shows you understand the problem definition and area calculation, but the O(n) two-pointer scan demonstrates algorithmic reasoning and optimization. Explaining why the shorter line must move is the critical insight they look for.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n²) | O(1) | Useful for understanding the problem or verifying correctness with small inputs |
| Two Pointers Technique | O(n) | O(1) | Optimal approach for interviews and large inputs; scans array once while greedily updating boundaries |
Container with Most Water - Leetcode 11 - Python • NeetCode • 417,556 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