11. Container With Most Water

Intuition

The problem involves finding two vertical lines in an array that, together with the x-axis, form a container capable of holding the maximum amount of water. The height of the water container is determined by the shorter of the two lines, and the width is the distance between them. By leveraging the properties of the array and the two-pointer technique, we can efficiently find the optimal solution without needing to check all possible pairs.

Approach

1. Two-Pointer Technique: Initialize two pointers, left at the beginning of the array and right at the end.
2. Calculate Area: Compute the area formed by the lines at the left and right pointers, using the formula: \[ \text{area} = (\text{right} - \text{left}) \times \min(\text{height[left]}, \text{height[right]}) \]
3. Update Maximum Area: Keep track of the maximum area encountered during the iteration.
4. Move Pointers: Adjust the pointers to potentially find a larger area: - If the height at the left pointer is less than the height at the right pointer, increment the left pointer. - Otherwise, decrement the right pointer.
5. Terminate: Repeat steps 2-4 until the left pointer is no longer less than the right pointer.
6. Return Result: The maximum area found during the iteration is the answer.

Complexity

Time Complexity:

O(n), where n is the length of the array. Each element is processed at most once by the two pointers.

Space Complexity:

O(1), as the solution only uses a constant amount of extra space for the two pointers and variables.

Code

C++

#include 
#include 
using namespace std;
class Solution {
public:
    int maxArea(vector& height) {
        int left = 0;
        int right = height.size() - 1;
        int maxArea = 0;  // Initialize maxArea to 0 instead of -Infinity
        while (left < right) {
            int area = (right - left) * min(height[left], height[right]);
            maxArea = max(maxArea, area);
            if (height[left] < height[right]) {
                ++left;
            } else {
                --right;
            }}
        return maxArea;
    }};

Python

from typing import List
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_area = 0
        while left < right:
            area = (right - left) * min(height[left], height[right])
            max_area = max(max_area, area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

Java

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;  // Initialize maxArea to 0
        while (left < right) {
            int area = (right - left) * Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }}
        return maxArea;
    }}

JavaScript

var maxArea = function(heights) {
    let left=0;
        let right=heights.length-1
        let maxArea=-Infinity
            while(left