Container With Most Water

Given an array height of non-negative integers representing the heights of lines on a 2D plane, where the width of each line is 1, find two lines which, together with the x-axis, forms a container that holds the most water.

Return the maximum area of water that can be contained in the container.

Sample Input and Expected Output:

Input:

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

Output:

Maximum area of water: 49

Solution in C++:

The idea is to use a two-pointer approach to find the container with the most water. We start with the two pointers, left at the beginning of the array and right at the end of the array. We calculate the area between the lines at these pointers (height * width) and keep track of the maximum area found so far. Then, we move the pointer that corresponds to the shorter line inward, as moving the longer line inward will not improve the area, and we want to maximize the area.

#include <iostream>
#include <vector>

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

    while (left < right) {
        // Calculate the area between the lines at the current pointers.
        int area = std::min(height[left], height[right]) * (right - left);

        // Update the maximum area if needed.
        maxArea = std::max(maxArea, area);

        // Move the pointer that corresponds to the shorter line inward.
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxArea;
}

int main() {
    std::vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};

    int result = maxArea(height);

    std::cout << "Maximum area of water: " << result << std::endl;

    return 0;
}

Time Complexity and Space Complexity:

The time complexity of the solution is O(n), where n is the size of the height vector. This is because we use a two-pointer approach that scans the array from both ends and each element is visited at most once.

The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array.