[leetcode] 11. Container With Most Water

Table of Contents

Description

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the line $i^{th}$ are $(i, 0)$ and $(i, \text{height}[i])$.

Find two lines, which, together with the $x$-axis, forms a container, such that the container contains the most water.

Return the maximum area of the container.

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 == \text{height.length}$
• $2 \leq n \leq 10^5$
• $0 \leq \text{height}[i] \leq 10^4$

Approach

We can start with two pointers, one at the beginning and the other at the end of the array. We then calculate the area between the two pointers and update the maximum area if the current area is greater than the maximum area. Finally, we move the pointer with the smaller height towards the other pointer and repeat the process until the two pointers meet.

Solution

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let maxArea = 0;

  // Use two pointers, one starting from the beginning (left) and one from the end (right) of the array.
  for (let left = 0, right = height.length - 1; left < right; ) {
    // Calculate the width between the two lines.
    let w = right - left;
    // Determine the height by finding the smaller of the two heights at the current pointers.
    let h = Math.min(height[left], height[right]);
    let area = w * h;

    if (area > maxArea) maxArea = area;

    // Move the pointer pointing to the shorter line inward, as this may increase the area.
    if (height[left] > height[right]) {
      right--;
    } else {
      left++;
    }
  }

  return maxArea;
};

Complexity Analysis

Time Complexity

The time complexity is $O(n)$, where $n$ is the length of the height array. We only iterate through the array once.

Space Complexity

The space complexity is $O(1)$ since we only use a constant amount of space.