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 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

Steps to Solve

The problem can be solved using a two-pointer approach. We initialize two pointers, left and right, pointing to the beginning and end of the height array, respectively.

1. Calculate the area: The area of the container formed by the lines at left and right is given by min(height[left], height[right]) * (right - left).

2. Update the maximum area: Keep track of the maximum area encountered so far.

3. Move the pointers: Move the pointer that points to the shorter line inwards. This is because moving the taller line inwards will not increase the area, as the limiting factor is the shorter line. If height[left] < height[right], move left one step to the right; otherwise, move right one step to the left.

4. Repeat: Repeat steps 1-3 until the left and right pointers cross.

Explanation

The key insight is that the area of the container is limited by the shorter of the two lines. Therefore, moving the taller line inwards won't increase the area. By moving the shorter line inwards, we have a chance to find a taller line that might increase the area. This approach efficiently explores all possible container pairs without brute-force checking every combination.

Code (Java)

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

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

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

        return maxArea;
    }
}

Complexity Analysis

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