Container With Most Water medium

Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th 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

Steps and Explanation

The problem asks us to find the maximum area that can be formed by two vertical lines and the x-axis. The area of a container is determined by the shorter of the two lines (the height) and the distance between them (the width).

A brute-force approach would be to check all possible pairs of lines, calculating the area for each pair and keeping track of the maximum. However, this would have a time complexity of O(n²).

A more efficient approach uses the two-pointer technique. We initialize two pointers, left and right, to the beginning and end of the height array, respectively. We then iterate, moving the pointer that points to the shorter line inward. This is because:

• If we move the taller line inward, the width decreases, and the height might or might not increase. The area could potentially increase or decrease.
• If we move the shorter line inward, the width decreases, but we might find a taller line that increases the height, leading to a larger area.

We continue this process until the pointers cross. At each step, we update the maximum area if we find a larger one.

Code (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    while (left < right) {
        int h = min(height[left], height[right]);
        int w = right - left;
        int area = h * w;
        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; // Output: 49

    vector<int> height2 = {1,1};
    cout << "Max Area: " << maxArea(height2) << endl; // Output: 1

    return 0;
}

Complexity

• Time Complexity: O(n), where n is the length of the height array. We iterate through the array at most once using the two-pointer technique.
• Space Complexity: O(1). We only use a few integer variables to store the pointers and the maximum area. The space used is constant regardless of the input size.