Container With Most Water In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement: “Container With Most Water”

Description: Given an integer array height where each element height[i] represents the height of a vertical line drawn at the position i. You are tasked with finding the two lines that together form a container that holds the most water. The container’s capacity is determined by the shorter of the two lines, and the distance between the two lines.

Your objective is to determine the maximum amount of water a container can hold.

Constraints:

• 2 <= height.length <= 10^5
• 0 <= height[i] <= 10^4

Approach:

1. Two Pointer Approach:
   • Start with two pointers, one at the beginning (left) and one at the end (right) of the array height.
   • Compute the area between these two lines. The area is determined by the formula:
     area = min(height[left], height[right]) * (right - left)
   • Move the pointer that points to the shorter line, since the area is limited by the shorter line. This is because moving the taller line won’t help increase the area.
   • Repeat this process until the two pointers meet.
   • Keep track of the maximum area encountered.
2. Time Complexity:
   • The time complexity of this solution is O(n), where n is the number of elements in the input array height.
3. Space Complexity:
   • The space complexity is O(1) since we are only using two pointers and a few variables to keep track of the maximum area.

Example:

For input:

height = [1,8,6,2,5,4,8,3,7]

Output:

49

Explanation: The container that holds the most water is formed between the lines at index 1 and index 8, with a height of 7 and width of 7, so the area is 7 * 7 = 49.

Code Implementation in Different Languages:

---

C:

#include <stdio.h>

int maxArea(int* height, int heightSize) {
    int left = 0, right = heightSize - 1;
    int max_area = 0;

    while (left < right) {
        int min_height = height[left] < height[right] ? height[left] : height[right];
        int width = right - left;
        int area = min_height * width;
        if (area > max_area) {
            max_area = area;
        }
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max_area;
}

int main() {
    int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    int size = sizeof(height) / sizeof(height[0]);
    printf("Max area: %d\n", maxArea(height, size));
    return 0;
}

---

C++:

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

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int max_area = 0;

    while (left < right) {
        int min_height = min(height[left], height[right]);
        int width = right - left;
        int area = min_height * width;
        max_area = max(max_area, area);

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

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

---

Java:

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

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

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

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

---

Python:

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        min_height = min(height[left], height[right])
        width = right - left
        area = min_height * width
        max_area = max(max_area, area)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

# Example Usage
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(f"Max area: {maxArea(height)}")

---

JavaScript:

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

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

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

// Example Usage
let height = [1, 8, 6, 2, 5, 4, 8, 3, 7];
console.log("Max area:", maxArea(height));

---

C#:

using System;

class Program {
    public static int MaxArea(int[] height) {
        int left = 0, right = height.Length - 1;
        int maxArea = 0;

        while (left < right) {
            int minHeight = Math.Min(height[left], height[right]);
            int width = right - left;
            int area = minHeight * width;
            maxArea = Math.Max(maxArea, area);

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

    static void Main() {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        Console.WriteLine("Max area: " + MaxArea(height));
    }
}

---

Conclusion:

This problem utilizes the two-pointer technique to efficiently find the solution in O(n) time. By progressively narrowing the search space while tracking the maximum area encountered, we achieve optimal performance even for large inputs.