MediumBlind75ArrayTwo Pointers
Container With Most Water
Find two lines that together with the x-axis form a container that holds the most water.
Examples
Input
height = [1,8,6,2,5,4,8,3,7]
Output
49
Maximum area is formed between indices 1 and 8: min(8,7) * (8-1) = 49.
Constraints
- •
n == height.length - •
2 <= n <= 10^5 - •
0 <= height[i] <= 10^4
Approaches
Check all pairs of lines and compute the area for each.
CodeT: O(n^2) | S: O(1)
def max_area(height):
max_water = 0
for i in range(len(height)):
for j in range(i + 1, len(height)):
area = min(height[i], height[j]) * (j - i)
max_water = max(max_water, area)
return max_waterStart with the widest container. Move the pointer with the smaller height.
CodeT: O(n) | S: O(1)
def max_area(height):
left, right = 0, len(height) - 1
max_water = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
max_water = max(max_water, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_waterSame as above but skip pointers when the new height is not greater.
Diagram
height=[1,8,6,2,5,4,8,3,7]
left=0,right=8: area=min(1,7)*8=8, left++
left=1,right=8: area=min(8,7)*7=49, right--
...max=49
CodeT: O(n) | S: O(1)
def max_area(height):
left, right = 0, len(height) - 1
max_water = 0
while left < right:
h = min(height[left], height[right])
max_water = max(max_water, h * (right - left))
while left < right and height[left] <= h:
left += 1
while left < right and height[right] <= h:
right -= 1
return max_waterComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Check all pairs of lines and compute the area for each. |
| Two Pointers - Shrink from Ends | O(n) | O(1) | Start with the widest container. Move the pointer with the smaller height. |
| Two Pointers with Skip | O(n) | O(1) | Same as above but skip pointers when the new height is not greater. |
Brute Force
T: O(n^2)S: O(1)
Check all pairs of lines and compute the area for each.
Two Pointers - Shrink from Ends
T: O(n)S: O(1)
Start with the widest container. Move the pointer with the smaller height.
Two Pointers with Skip
T: O(n)S: O(1)
Same as above but skip pointers when the new height is not greater.
Common Mistakes
Moving both pointers at the same time
Not understanding why moving the smaller pointer is optimal
Computing area using height instead of min(height[left], height[right])