Problem Description#
Given an integer array height of length n, where each element represents the height of a vertical line at position i (0-indexed), find two lines that together with the x-axis forms a container that can hold the maximum amount of water.
Return the maximum amount of water that can be held by the container.
Note: You may not slant 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 (blue area), which is 49.
Example 2:
Input: height = [1,1]
Output: 1
Constraints:
n == height.length
2 <= n <= 10^50 <= height[i] <= 10^4
Approach#
- Traverse from both ends of the array towards the middle. The upper limit of water held by the container is determined by the shorter line. Multiply the distance between the two pointers by this value to get the amount of water held.
- Compare the current amount of water held with the maximum amount of water held (initially set to 0) and take the maximum value.
- Only move one pointer at a time. Move the pointer on the shorter side towards the middle, as the shorter side affects the amount of water held.
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;
};