Container With Most Water medium

Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith 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

Steps to Solve:

1. Initialization: Initialize two pointers, left and right, pointing to the beginning and end of the height array, respectively. Initialize a variable maxArea to 0 to store the maximum area found so far.

2. Iteration: While left is less than right, perform the following steps:

   • Calculate the area of the container formed by the lines at left and right: area = min(height[left], height[right]) * (right - left).
   • Update maxArea if area is greater than maxArea.
   • Move the pointer with the smaller height inward. This is because moving the taller bar will necessarily reduce the height of the container, while moving the shorter bar might increase the width and potentially the overall area. If height[left] < height[right], increment left; otherwise, decrement right.

3. Return: After the loop completes, return maxArea.

Explanation:

The key insight is that the area of a container is determined by both its height (the minimum of the two heights) and its width (the distance between the two lines). To maximize the area, we need to consider a balance between height and width. By moving the pointer with the smaller height inward, we attempt to increase the height (potentially) while sacrificing a small amount of width. This approach is more efficient than brute-forcing all possible pairs of lines.

Code (Typescript):

function maxArea(height: number[]): number {
    let left = 0;
    let right = height.length - 1;
    let maxArea = 0;

    while (left < right) {
        const area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);

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

    return maxArea;
};

Complexity:

• Time Complexity: O(n), where n is the length of the height array. We iterate through the array at most once using the two pointers.
• Space Complexity: O(1). We use only a constant amount of extra space to store variables.