Container with Most Water
Container with Most Water – Hard Level Problem
You are given an array heights, where each element heights[i] represents the height of a vertical bar at position i. Your task is to select any two bars to form a container, with the width of the container being the distance between the two bars.
The goal is to find the maximum amount of water that this container can hold. Return the largest possible value of water that can be stored.
Output: 36
Output: 4
Constraints:
- 2 <= height.length <= 1000
- 0 <= height[i] <= 1000
Container with Most Water Solution
Recommendation for Time and Space Complexity –You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A brute force solution would be to try all pairs of bars in the array, compute the water for each pair, and return the maximum water among all pairs. This would be an O(n^2) solution. Can you think of a better way?
Hint 2 :
Can you think of an algorithm that runs in linear time and is commonly used in problems that deal with pairs of numbers? Find a formula to calculate the amount of water when we fix two heights.
Hint 3 :
We can use the two pointer algorithm. One pointer is at the start and the other at the end. At each step, we calculate the amount of water using the formula (j – i) * min(heights[i], heights[j]). Then, we move the pointer that has the smaller height value. Can you think why we only move the pointer at smaller height?
Hint 4 :
In the formula, the amount of water depends only on the minimum height. Therefore, it is appropriate to replace the smaller height value.
There are mainly 2 approach to solve this problem-
- Brute Force Method
- Two Pointers Method
1. Brute Force Method
This approach involves checking the amount of water that can be stored between every possible pair of bars using nested loops. It has a time complexity of O(n²) and is simple but inefficient.
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
class Solution {
public:
int maxArea(vector& heights) {
int res = 0;
for (int i = 0; i < heights.size(); i++) {
for (int j = i + 1; j < heights.size(); j++) {
res = max(res, min(heights[i], heights[j]) * (j - i));
}
}
return res;
}
};
public class Solution {
public int maxArea(int[] heights) {
int res = 0;
for (int i = 0; i < heights.length; i++) {
for (int j = i + 1; j < heights.length; j++) {
res = Math.max(res, Math.min(heights[i], heights[j]) * (j - i));
}
}
return res;
}
}
class Solution:
def maxArea(self, heights: List[int]) -> int:
res = 0
for i in range(len(heights)):
for j in range(i + 1, len(heights)):
res = max(res, min(heights[i], heights[j]) * (j - i))
return res
class Solution {
/**
* @param {number[]} heights
* @return {number}
*/
maxArea(heights) {
let res = 0;
for (let i = 0; i < heights.length; i++) {
for (let j = i + 1; j < heights.length; j++) {
res = Math.max(res, Math.min(heights[i], heights[j]) * (j - i));
}
}
return res;
}
}
2. Two Pointers Method
In this approach, two pointers are placed at the beginning and end of the array, and the water capacity is calculated while moving the pointers inward based on the smaller height. This method is more efficient with a time complexity of O(n).
- Time complexity: O(n)
- Space complexity: O(1)
Code
class Solution {
public:
int maxArea(vector& heights) {
int l = 0;
int r = heights.size() - 1;
int res = 0;
while (l < r) {
int area = min(heights[l], heights[r]) * (r - l);
res = max(res, area);
if (heights[l] <= heights[r]) {
l++;
} else {
r--;
}
}
return res;
}
};
public class Solution {
public int maxArea(int[] heights) {
int l = 0;
int r = heights.length - 1;
int res = 0;
while (l < r) {
int area = Math.min(heights[l], heights[r]) * (r - l);
res = Math.max(res, area);
if (heights[l] <= heights[r]) {
l++;
} else {
r--;
}
}
return res;
}
}
class Solution:
def maxArea(self, heights: List[int]) -> int:
l, r = 0, len(heights) - 1
res = 0
while l < r:
area = min(heights[l], heights[r]) * (r - l)
res = max(res, area)
if heights[l] <= heights[r]:
l += 1
else:
r -= 1
return res
class Solution {
/**
* @param {number[]} heights
* @return {number}
*/
maxArea(heights) {
let l = 0;
let r = heights.length - 1;
let res = 0;
while (l < r) {
const area = Math.min(heights[l], heights[r]) * (r - l);
res = Math.max(res, area);
if (heights[l] <= heights[r]) {
l++;
} else {
r--;
}
}
return res;
}
}
More Articles
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