11 Container With Most Water

Given n non-negative integers a1,a2, ...,an, where each represents a point at coordinate (i,ai). n vertical lines are drawn such that the two endpoints of line i is at (i,ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The Idea: Apply a greedy approach. Being with the widest lines (start and end) to first optimize the width. Then move leftor rightiterators, depending on whether or not it supports a height greater than the previous. In other words, ignore smaller heights until a larger one is found. An otherwise smaller height would be that the supported area will be smaller than the previous.

Complexity: O(n) time and O(1) space

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

    while (left < right) {
        int h = min(heights[left], heights[right]);
        max_water = max(max_water, h * (right - left));
        while (heights[left] <= h && left < right) 
            left++;
        while (heights[right] <= h && left < right) 
            right--;
    }

    return max_water;
}