11. Container With Most Water

[songyy5517]

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

Intuition This problem is to find two lines with the most water in the container. From the description, for two lines h[i] and h[j], we can infer that area_water = min(h[i], h[j]) * |i - j|. Therefore, we can use two (collision) pointers left and right first pointing at the left and the right side of the array respectively. In this way, |i - j| can be the maximum. Next, what we need to do is to move the two pointers towards each other when scanning the entire array, and find the pair that minimizes the water area. Throughout the scan, |i - j| would be descending. Therefore, to find the maximum value of area_water, we should exclude the cases where both min(h[i], h[j]) and |i - j| decreases. So for each step, we have two lines height[left] and height[right], we move the smaller one to the next position and calculate the area.

[songyy5517]

Approach: Two Pointers & Greedy

1. Exception handling;
2. Define variables
   • Two collision pointers left and right pointing at the left and the right side of the array at the beginning;
   • max_area : a global variable to record the maximum area.
3. When two pointers don't across: （1）Calculate the current area of two lines, and update the global variables; （2）Move the pointer with smaller value to the next position. (Greeady)
4. Return the global vairble max_area.

Complexity Analysis

• Time complexity: $O(N)$ , using two pointers to scan the entire array takes $O(N)$ time;
• Space complexity: $O(1)$ , additionally define constant-level variables.

[songyy5517]

class Solution {
    public int maxArea(int[] height) {
        // Intuition: Two Pointers (Collision Pointers) & Array travarsal. 
        // 1. Exception handling
        if (height == null || height.length < 2)
            return 0;

        // 2. Define two collision pointers
        int left = 0, right = height.length - 1;
        int max_area = 0;

        // 3. Loop through the array
        while (left < right) {
            // Calculate the area
            int h = Math.min(height[left], height[right]);
            max_area = Math.max(max_area, (right - left) * h);

            // Update the smaller pointer (Greedy)
            if (height[left] < height[right])
                left ++;
            else 
                right --;
        }

        return max_area;
    }
}

[songyy5517]

2024/5/11