Back to DSA
Container With Most Water
mediumConsider a set of vertical barriers plotted on a number line, where the height of the barrier at position i is given by the array entry at index i. Pick any two barriers to form a container. The container's water capacity equals the shorter barrier's height multiplied by the horizontal distance between them. Find the pair that yields the maximum capacity.
Examples
Example 1:
Input:
heights = [3,9,2,5,8,4,7]Output:
35Explanation: Barriers at index 1 (height 9) and index 6 (height 7) form the largest container: min(9,7) * (6-1) = 35.
Example 2:
Input:
heights = [4,4]Output:
4Explanation: The only pair of barriers forms a container of area min(4,4) * 1 = 4.
Hints
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
int area = Math.min(height[left], height[right]) * (right - left);
maxArea = Math.max(maxArea, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}Time complexity
O(n)Space complexity
O(1)