Container With Most Water
MedPrompt
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] <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward solution is to consider every possible pair of vertical lines and calculate the area of the container they form. We can then keep track of the maximum area found among all pairs.
Algorithm
- Initialize a variable
maxAreato 0. - Use a for loop to iterate from the first line
i = 0to the second to last linen-2. - Inside this loop, use another for loop to iterate from
j = i + 1to the last linen-1. - For each pair of lines
(i, j), calculate the area:area = Math.min(height[i], height[j]) * (j - i). - Compare this
areawithmaxAreaand updatemaxAreaif the currentareais larger:maxArea = Math.max(maxArea, area). - After the loops complete, return
maxArea.
Walkthrough
This method involves using two nested loops to iterate through all possible pairs of lines. The outer loop selects the first line (i), and the inner loop selects the second line (j), where j is always to the right of i. For each pair (i, j), the area is calculated as the product of the distance between the lines (j - i) and the height of the shorter line (min(height[i], height[j])). We maintain a variable, maxArea, which is updated whenever a larger area is found. After checking all pairs, maxArea will hold the result.
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 currentHeight = Math.min(height[i], height[j]); int currentWidth = j - i; int currentArea = currentHeight * currentWidth; maxArea = Math.max(maxArea, currentArea); } } return maxArea; }}Complexity
Time
O(n^2)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to find the correct answer as it checks every possibility.
Cons
Very inefficient due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for large input sizes.
A more efficient solution uses the two-pointer technique. We start with the widest possible container, using pointers at the very beginning and very end of the array. Then, we iteratively narrow the container by moving one of the pointers, always aiming to find a taller bounding line to compensate for the reduced width.
Algorithm
- Initialize
maxArea = 0,left = 0, andright = n - 1. - Loop as long as
left < right. - Calculate the current area:
area = Math.min(height[left], height[right]) * (right - left). - Update
maxArea:maxArea = Math.max(maxArea, area). - If
height[left]is less thanheight[right], incrementleft. - Otherwise, decrement
right. - After the loop finishes, return
maxArea.
Walkthrough
We initialize two pointers, left at index 0 and right at the last index n-1. These two pointers represent the boundaries of the container. In each step, we calculate the area formed by the lines at left and right. The area is min(height[left], height[right]) * (right - left). We update our maximum area found so far.
The key insight is how to move the pointers. The width (right - left) will always decrease. To have a chance of finding a larger area, we must increase the height of the container, which is limited by the shorter of the two lines. Therefore, it's always optimal to move the pointer corresponding to the shorter line inward. If height[left] < height[right], we move left one step to the right. Otherwise, we move right one step to the left. This process continues until the pointers meet or cross (left >= right). This strategy works because we are systematically eliminating the shorter line, which cannot be part of a better container with any line within the current left and right boundaries.
class Solution { public int maxArea(int[] height) { int maxArea = 0; int left = 0; int right = height.length - 1; while (left < right) { int currentHeight = Math.min(height[left], height[right]); int currentWidth = right - left; int currentArea = currentHeight * currentWidth; maxArea = Math.max(maxArea, currentArea); if (height[left] < height[right]) { left++; } else { right--; } } return maxArea; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Highly efficient with a linear time complexity.
Uses constant extra space.
Optimal solution for this problem.
Cons
The logic for moving the pointers might be slightly less intuitive to grasp initially compared to the brute-force method.
Solutions
Solution
public class Solution { public int MaxArea(int[] height) { int i = 0, j = height.Length - 1; int ans = 0; while (i < j) { int t = Math.Min(height[i], height[j]) * (j - i); ans = Math.Max(ans, t); if (height[i] < height[j]) { ++i; } else { --j; } } return ans; }}class Solution {public int maxArea(int[] height) { int i = 0, j = height.length - 1; int ans = 0; while (i < j) { int t = Math.min(height[i], height[j]) * (j - i); ans = Math.max(ans, t); if (height[i] < height[j]) { ++i; } else { --j; } } return ans; }}/** * @param {number[]} height * @return {number} */ var maxArea = function ( height,) { let i = 0; let j = height.length - 1; let ans = 0; while (i < j) { const t = Math.min(height[i], height[j]) * (j - i); ans = Math.max(ans, t); if (height[i] < height[j]) { ++i; } else { --j; } } return ans;};class Solution {public: int maxArea(vector<int> &height) { int i = 0, j = height.size() - 1; int ans = 0; while (i < j) { int t = min(height[i], height[j]) * (j - i); ans = max(ans, t); if (height[i] < height[j]) { ++i; } else { --j; } } return ans; }};class Solution: def maxArea(self, height: List[int]) -> int: i, j = 0, len(height) - 1 ans = 0 while i < j: t = (j - i) * min(height[i], height[j]) ans = max(ans, t) if height[i] < height[j]: i += 1 else: j -= 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.