Container With Most Water Leetcode Solution
Container With Most Water Leetcode Problem :
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.
Container With Most Water Leetcode Solution :
Constraints :
- n == height.length
- 2 <= n <= 105
- 0 <= height[i] <= 104
Example 1:
- Input: height = [1,1]
- Output: 1
Intuition :
The two-pointer technique starts with the widest container and moves the pointers inward based on the comparison of heights.
Increasing the width of the container can only lead to a larger area if the height of the new boundary is greater. By moving the pointers towards the center, we explore containers with the potential for greater areas.
- Initialize the variables:
- left to represent the left pointer, starting at the beginning of the container (index 0).
- right to represent the right pointer, starting at the end of the container (index height.size() – 1).
- maxArea to keep track of the maximum area found, initially set to 0.
- Enter a loop using the condition left < right, which means the pointers have not crossed each other yet.
- Calculate the current area:
- Use the min function to find the minimum height between the left and right pointers.
- Multiply the minimum height by the width, which is the difference between the indices of the pointers: (right – left).
- Store this value in the currentArea variable.
- Update the maximum area:
- Use the max function to compare the currentArea with the maxArea.
- If the currentArea is greater than the maxArea, update maxArea with the currentArea.
- Move the pointers inward: (Explained in detail below)
- Check if the height at the left pointer is smaller than the height at the right pointer.
- If so, increment the left pointer, moving it towards the center of the container.
- Otherwise, decrement the right pointer, also moving it towards the center.
- Repeat steps 3 to 5 until the pointers meet (left >= right), indicating that all possible containers have been explored.
- Return the maxArea, which represents the maximum area encountered among all the containers.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int maxArea(vector< int>& height) {
int left = 0;
int right = height.size() - 1;
int maxArea = 0;
while (left < right) {
int currentArea = min(height[left], height[right]) * (right - left);
maxArea = max(maxArea, currentArea);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
};
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
int currentArea = Math.min(height[left], height[right]) * (right - left);
maxArea = Math.max(maxArea, currentArea);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height) - 1
maxArea = 0
while left < right:
currentArea = min(height[left], height[right]) * (right - left)
maxArea = max(maxArea, currentArea)
if height[left] < height[right]:
left += 1
else:
right -= 1
return maxArea
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment