Container With Most Water Problem and Solution

1. Introduction

The "Container With Most Water" problem involves finding two lines that, together with the x-axis, form a container, such that the container contains the most water. The goal is to maximize the area of water it can hold. The height of each line is determined by an array of integers, where each element represents the height at that point.

2. Solution in C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxArea(vector<int>& height) {
    int water = 0, i = 0, j = height.size() - 1;
    while (i < j) {
        int h = min(height[i], height[j]);
        water = max(water, h * (j - i));
        if (height[i] < height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return water;
}

// Example usage
int main() {
    vector<int> height = {1,8,6,2,5,4,8,3,7};
    cout << "Max Area: " << maxArea(height) << endl;
    return 0;
}

Output:

Max Area: 49

Explanation:

1. maxArea uses a two-pointer approach, starting from both ends of the array.

2. It calculates the area at each step and keeps track of the maximum area found so far.

3. The pointers move towards each other, always moving the pointer at the shorter line.

4. This approach ensures that every potential max area is checked.

3. Solution in Java

public class ContainerWithMostWater {
    public static int maxArea(int[] height) {
        int water = 0, i = 0, j = height.length - 1;
        while (i < j) {
            int h = Math.min(height[i], height[j]);
            water = Math.max(water, h * (j - i));
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return water;
    }

    // Example usage
    public static void main(String[] args) {
        int[] height = {1,8,6,2,5,4,8,3,7};
        System.out.println("Max Area: " + maxArea(height));
    }
}

Output:

Max Area: 49

Explanation:

1. The Java solution is similar to the C++ solution, using a two-pointer approach.

2. It calculates the area between the two pointers and updates the max area.

3. Moves the pointer at the shorter line inwards to check for potential larger areas.

4. The loop continues until the two pointers meet.

4. Solution in Python

def max_area(height):
    water, i, j = 0, 0, len(height) - 1
    while i < j:
        h = min(height[i], height[j])
        water = max(water, h * (j - i))
        if height[i] < height[j]:
            i += 1
        else:
            j -= 1
    return water

# Example usage
height = [1,8,6,2,5,4,8,3,7]
print("Max Area:", max_area(height))

Output:

Max Area: 49

Explanation:

1. In Python, max_area also implements the two-pointer approach.

2. It iteratively computes the area and keeps track of the maximum.

3. The pointer at the shorter line moves inwards.

4. The function returns the maximum area found.