Container With Most Water
Question
You are given an integer array height of length n. There are n vertical lines are drawn such that the two endpoints of the ith line is (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.
Solution
The question is asking us to find the maximum area between two containers whose height is given.
Brute force solution will be we iterate through the array and calculate the area by width * height formula.
var maxArea = function (height) {
let length = 0;
for (let x= 0; x< height.length; x++) {
for (let y = 0; y < *height*.length; y++) {
if (*height*\[x\] <= *height*\[y\]) {
let sum = *height*\[x\] \* (y-x);
if (sum > length) {
length = sum;
}
} else {
let sum2 = height[y] * (y-x);
if (sum2 > length) {
length = sum2;
}
}
}
}
return length;
};
This solution works perfectly fine as we iterate through the containers and evaluate the area between two containers as the the product of width between two containers and the height of the shortest container.
Now we can go for a much better solution
If we are considering the left most and right most containers, we can calculate the area between LM(leftmost) and RM(rightmost) as the product of the Minimum height of LM, RM, and the width between them ie., say RM-LM
Area = Math.min(Height(LM),Height(RM)* (RM-LM))
Now we have to increment or decrement LM or RM respectively. If the rightmost element is smaller we decrement RM else if the LM element is the smallest we will increment LM.
We do this because if any of the end containers is smaller than the other it will not have a further good area than the current one.
These Visual images will help you out:
Here the rightmost element will never have an area better than the current so we decrement the rightmost element.
In this scenario, the left-most element is having a smaller length and it won't have any better area because length may vary but width always decreases on the next iteration.
source(https://dev.to/seanpgallivan/solution-container-with-most-water-1907)
Implementation:
var maxArea = (height) => {
let ans = 0;
i = 0;
j = height.length - 1;
while (i < j) {
ans = Math.max(ans, Math.min(height[i], height[j]) * (j - i));
height[i] <= height[j] ? i++ : j--;
}
return ans;
};
Conclusion.
We have solved the Container with the most water problems in JavaScript. Follow me on Twitter and Medium.