Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water. Note: You may not slant the container.
Use the controls to visualize the two-pointer technique
This interactive visualization demonstrates how the two-pointer algorithm finds the maximum area that can be contained between any two vertical lines (represented by array values).
Each bar represents a height from the input array. The blue highlighted bars are the current left and right pointers. The blue area between them represents the water container formed.
Use the controls below to step through the algorithm or play it automatically. Observe how the pointers move inward strategically to find the optimal container.
Current Array: [1, 8, 6, 2, 5, 4, 8, 3, 7]
Step 1: Start with pointers at both ends and calculate initial area
Step: 1 of 8
Left pointer: 0 (height: 1)
Right pointer: 8 (height: 7)
Current area: 8
Max area so far: 8
Water level: min(1, 7) = 1
Current Area
8
Example 1
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The container with most water is formed by the lines at index 1 and 8 with a height of 8 and a width of 7, giving an area of 8*7 = 56. Since the height is determined by the shorter line (the line at index 1 is shorter), the actual height is 7, so the area is 7*7 = 49.
Example 2
Input: height = [1,1]
Output: 1
Explanation: The width of the container is 1, and the height is also 1, so the area is 1*1 = 1.
Example 3
Input: height = [4,3,2,1,4]
Output: 16
Explanation: The container with most water is formed by the lines at index 0 and 4 with a height of 4, giving an area of 4*4 = 16.
Algorithm Implementation
Step 1 of 19
Line 2
Water stored between lines = min(height[left, height[right]) * (right - left)
= min(1, 7) * (8 - 0)
right = len(height) - 1 = 9 - 1 = 8
left, right = 0, len(height) - 1Initialize two pointers at the start and end.
1def maxArea(height: List[int]) -> int:
2 left, right = 0, len(height) - 1
3 maxArea = 0
4
5 while left < right:
6 width = right - left
7 h = min(height[left], height[right])
8 area = width * h
9 maxArea = max(maxArea, area)
10
11 if height[left] < height[right]:
12 left += 1
13 else:
14 right -= 1
15
16 return maxArea
Algorithm Implementation
1def maxArea(height: List[int]) -> int:
2 # Initialize two pointers at the start and end of array
3 left, right = 0, len(height) - 1
4
5 # Keep track of the maximum area found so far
6 maxArea = 0
7
8 # Continue until pointers meet
9 while left < right:
10 # Calculate width between current pointers
11 width = right - left
12
13 # Height is limited by the shorter line
14 h = min(height[left], height[right])
15
16 # Calculate current area
17 area = width * h
18
19 # Update maxArea if current area is larger
20 maxArea = max(maxArea, area)
21
22 # Move the pointer pointing to the shorter line
23 if height[left] < height[right]:
24 left += 1
25 else:
26 right -= 1
27
28 # Return the maximum area found
29 return maxAreaComplexity Analysis
Understanding the time and space complexity helps evaluate the efficiency of our algorithm
Brute Force Approach
The brute force approach checks all possible pairs of lines, leading to a quadratic time complexity.
Time Complexity
The algorithm makes a single pass through the array with the two pointers, performing constant-time operations at each step.
Why it's efficient
The two-pointer approach allows us to avoid checking all n² combinations of lines, instead finding the optimal solution in a single pass through the array.
Detailed Breakdown
- Initialize pointers: O(1)
- Single iteration through array: O(n)
- Area calculations: O(1) per step
- Comparing heights: O(1) per step
- Overall complexity: O(n)
Space Complexity
Only a constant amount of extra space is used, regardless of input size - just the variables for pointers and areas.
Memory efficiency
This algorithm is memory-efficient as we only need to store a few variables regardless of the input size. No additional data structures are needed.
Memory Usage
- Input array: O(n) - already given, not counted
- Left pointer: O(1)
- Right pointer: O(1)
- Current area: O(1)
- Maximum area: O(1)
- Overall auxiliary space: O(1)
Comparing with Other Approaches
| Approach | Time | Space | Trade-offs |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Simple but inefficient for large inputs |
| Two Pointers | O(n) | O(1) | Optimal balance of simplicity and efficiency |
| Dynamic Programming | O(n²) | O(n²) | Unnecessary complexity for this problem |
Two-Pointer Method Explained
This algorithm efficiently finds the maximum area container by examining potential containers in a single pass, using O(n) time complexity.