Problem Description#
Given an integer array height of length n, there are n vertical lines. The two endpoints of the i-th line are (i, 0) and (i, height[i]).
Find two lines that, together with the x-axis, form a container that can hold the maximum amount of water.
Return the maximum amount of water the container can hold.
Note: You cannot tilt the container.
Example 1:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The vertical lines in the image represent the input array [1,8,6,2,5,4,8,3,7]. In this case, the container can hold the maximum amount of water (represented by the blue area), which is 49.
Example 2:
Input: height = [1,1]
Output: 1
Constraints:
n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4
Approach#
- Traverse from both ends of the array towards the middle. The upper limit of the water container is determined by the shorter side. Multiply the distance between the two pointers by this value to get the amount of water stored.
- Compare the current amount of water stored with the maximum amount of water stored (initially set to 0) and take the maximum value.
- Move only one pointer at a time, towards the middle, on the shorter side, as the shorter side affects the amount of water stored.
Solution#
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
let l = 0, r = height.length - 1;
let ans = 0, max = 0;
while (l < r) {
let h = height[l] < height[r] ? height[l] : height[r];
max = (r - l) * h;
height[l] < height[r] ? l++ : r--;
ans = max > ans ? max : ans;
}
return ans;
};