Container With Most Water
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.
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.length
● 2 <= n <= 105
● 0 <= height[i] <= 104
Step 1 : – Template Implementation
There are two types of two pointer templates.
1). Opposite direction two pointer template
2). Same direction two pointer template
Based on our analysis of the Container With Most Water problem statement, we will use here modified opposite-direction pointer template.
In the opposite-direction pointer template, we typically consider three scenarios based on how the current sum compares to the target value. However, for the maximum area (Container With Most Water) problem, the target-equality scenario does not apply as the target is not given.
Instead, the only task is to compute the container area formed by the two heights at the current pointers. After calculating the area, we move only one pointer at a time—either the left or the right—based solely on which height is smaller.
Additionally, there is no need to sort the array, because sorting would change the original positions of the heights, and the area depends directly on the distance between the original indices.
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
//code
if (param1 < param2) {
left++;
} else {
right--;
}
}
return maxArea;
}
}Step 2 : – Dynamic parameters of the template.
Since this is not a target-based problem, our goal is simply to compute the maximum possible area. After calculating the current area, we move only one pointer at a time—either the left pointer or the right pointer—based entirely on which height is smaller.
In this approach:
-
Param1 corresponds to
height[left] -
Param2 corresponds to
height[right]
This ensures that we always shift the pointer at the shorter line, which is the only way to potentially find a larger area.
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
// Move the pointer pointing to the shorter line
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}Step 3: – Output/return parameter.
To compute the area, we use the formula area = height × width. For each pair of lines, we calculate the area using this formula and compare it with the previously computed maximum. If the current area is larger, we update the maximum area accordingly.
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
int h = Math.min(height[left], height[right]);
int w = right - left;
int area = h * w;
maxArea = Math.max(maxArea, area);
// Move the pointer pointing to the shorter line
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}Final Code : –
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
int h = Math.min(height[left], height[right]);
int w = right - left;
int area = h * w;
maxArea = Math.max(maxArea, area);
// Move the pointer pointing to the shorter line
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}