Container With Most Water

Problem

You are given an integer array height of length n. There are n vertical lines drawn such that 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, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Constraints:

n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴

Solution

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let left = 0;
    let right = height.length - 1;
    let area = 0;
    while (left !== right) {
        const hr = height[right]
        const hl = height[left]
        area = Math.max(area, (right - left) * Math.min(hl, hr))
        if (hl < hr) {
            left++;
        } else {
            right--;
        }
    }
    return area;
};

We will implement a two pointers solution. We start off with using the left-most and right-most lines since it provides the greatest width. Observe that the area is constrained by the line with the smaller height, and so we want to shift that line by one. Thus, we keep on adjusting the left and right boundaries until they meet while keeping track of the largest area so far.

Problem​

Solution​

Problem

Solution