Problem Statement:
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.
Examples:
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
Approach
- Initialize two pointers
i = 0andj = arr.length - 1. - Calculate the area between the two lines at i and j:
area = min(arr[i], arr[j]) * (j - i) - Track the maximum area found so far.
- Move the pointer pointing to the shorter line inward (to potentially find a taller line and maximize area).
- Repeat until
i < j
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(1)
Dry Run
Input: arr = [1, 8, 6, 2, 5, 4, 8, 3, 7]
i = 0, j = 8 → height = min(1, 7) = 1 → width = 8 → area = 8 → maxWater = 8 arr[i] < arr[j] → i++ i = 1, j = 8 → height = min(8, 7) = 7 → width = 7 → area = 49 → maxWater = 49 arr[i] > arr[j] → j-- i = 1, j = 7 → height = min(8, 3) = 3 → width = 6 → area = 18 → maxWater = 49 arr[i] > arr[j] → j-- i = 1, j = 6 → height = min(8, 8) = 8 → width = 5 → area = 40 → maxWater = 49 arr[i] <= arr[j] → i++ i = 2, j = 6 → height = min(6, 8) = 6 → width = 4 → area = 24 → maxWater = 49 arr[i] < arr[j] → i++ i = 3, j = 6 → height = min(2, 8) = 2 → width = 3 → area = 6 → maxWater = 49 arr[i] < arr[j] → i++ i = 4, j = 6 → height = min(5, 8) = 5 → width = 2 → area = 10 → maxWater = 49 arr[i] < arr[j] → i++ i = 5, j = 6 → height = min(4, 8) = 4 → width = 1 → area = 4 → maxWater = 49 arr[i] < arr[j] → i++ i = 6, j = 6 → loop ends
Output: Result: 49
var maxArea = function(arr) {
let i = 0;
let j = arr.length - 1;
let maxWater = 0;
while(i < j){
let area = Math.min(arr[i], arr[j]) * (j-i);
maxWater = Math.max(maxWater, area);
if(arr[i] > arr[j]) {
--j;
} else {
++i;
}
}
return maxWater;
};
def maxArea(height):
i, j = 0, len(height) - 1
max_water = 0
while i < j:
area = min(height[i], height[j]) * (j - i)
max_water = max(max_water, area)
if height[i] > height[j]:
j -= 1
else:
i += 1
return max_water
public int maxArea(int[] height) {
int i = 0, j = height.length - 1;
int maxWater = 0;
while (i < j) {
int area = Math.min(height[i], height[j]) * (j - i);
maxWater = Math.max(maxWater, area);
if (height[i] > height[j]) {
j--;
} else {
i++;
}
}
return maxWater;
}
int maxArea(vector& height) {
int i = 0, j = height.size() - 1;
int maxWater = 0;
while (i < j) {
int area = min(height[i], height[j]) * (j - i);
maxWater = max(maxWater, area);
if (height[i] > height[j]) {
j--;
} else {
i++;
}
}
return maxWater;
}
int maxArea(int* height, int heightSize) {
int i = 0, j = heightSize - 1;
int maxWater = 0;
while (i < j) {
int h = height[i] < height[j] ? height[i] : height[j];
int area = h * (j - i);
if (area > maxWater) maxWater = area;
if (height[i] > height[j]) {
j--;
} else {
i++;
}
}
return maxWater;
}
public int MaxArea(int[] height) {
int i = 0, j = height.Length - 1;
int maxWater = 0;
while (i < j) {
int area = Math.Min(height[i], height[j]) * (j - i);
maxWater = Math.Max(maxWater, area);
if (height[i] > height[j]) {
j--;
} else {
i++;
}
}
return maxWater;
}
