Problem
Given n non-negative integers a₁, a₂, …, aₙ where each represents a vertical line height, find two lines that together with the x-axis form the container holding the most water.
Example
Input: [1,8,6,2,5,4,8,3,7]
Output: 49Solution
Two pointers from both ends. Always move the shorter line inward (moving the taller can’t increase area).
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))
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_waterfunction maxArea(height) {
let left = 0, right = height.length - 1, maxWater = 0;
while (left < right) {
const h = Math.min(height[left], height[right]);
maxWater = Math.max(maxWater, h * (right - left));
if (height[left] < height[right]) left++;
else right--;
}
return maxWater;
}int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1, maxWater = 0;
while (left < right) {
int h = min(height[left], height[right]);
maxWater = max(maxWater, h * (right - left));
if (height[left] < height[right]) left++;
else right--;
}
return maxWater;
}public int maxArea(int[] height) {
int left = 0, right = height.length - 1, maxWater = 0;
while (left < right) {
int h = Math.min(height[left], height[right]);
maxWater = Math.max(maxWater, h * (right - left));
if (height[left] < height[right]) left++;
else right--;
}
return maxWater;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
Width decreases as pointers move inward. The only way to potentially gain area is by finding a taller line, so move the shorter pointer.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?