11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/description/

Optimal Space & Time Complexity

- Time complexity: O(n)
- Space complexity: O(1)

---

Solutions

東

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

Hao

YC

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

        if(height[left] < height[right]) left++;
        else right--;
    } 
    return maxArea;
};

SOL

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let leftPointer= 0;
    let rightPointer = height.length - 1
    let result = 0;
    while(leftPointer < rightPointer){
        const width = rightPointer-leftPointer;
        const y =  Math.min(height[leftPointer] , height[rightPointer]);
        const water = y * width;
        if( water > result) result =  water;
        y === height[rightPointer] ? rightPointer--:leftPointer++;
    }
    return result;
};

---

Supplement / Discussion

東

White board explanation

Hao

https://leetcode.com/problems/container-with-most-water/solutions/3493276/c-java-python-javascript-optimized-code-easy-to-understand-100-solution-explained/

1. Because line (the width) consists two points, that is a scenario suitalbe with two pointers (left, right).
2. The key to update iteration is if (height[left] < height[right]) left += 1; else right -= 1;. Though we take Math.min(height[left], height[right]) to calculate the area of rectangle, if we update the smaller height, the chance is it might be greater then the greater height in the last iteration, which brings a greater Math.min(height[left], height[right]).

YC

• implement a left-right pointer
• move the pointer having a smaller value

SOL

https://medium.com/@kaokaolin456/leetcode-container-with-most-water-f463692e4533

---

Live Coding Space

var maxArea = function(height) {
    let left = 0;
    let right = height.length - 1;
    let max = Math.min(height[left], height[right]) * (right - left);
    
    while (right > left) {
        const currArea = Math.min(height[left], height[right]) * (right - left);
        if(currArea > max) max = currArea;
        if(height[left + 1] > height[right]) left++;
        else right--;
    }
    return max;
};