11.Container With Most Water

Find two lines, which, together with the x-axis forms a container, such that the container contains the most water

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.

Solution I : (Brute force, Find all possible area and check for max)

class Solution
{
public:
    int maxArea(vector<int> &height)
    {

        int maxArea = INT_MIN;
        for (int i = 0; i < height.size(); i++)
        {

            for (int j = i + 1; j < height.size(); j++)
            {

                int area = (j - i) * min(height[i], height[j]);
                if (area > maxArea)
                {
                    maxArea = area;
                }
            }
        }

        return maxArea;
    }
};

Time Complexity: O(n^2)

Solution II: (Using 2 pointer)

To maximize the area, we need to consider the area between the lines of larger lengths. If we try to move the pointer at the longer line inwards, we won't gain any increase in area, since it is limited by the shorter line. But moving the shorter line's pointer we can have an increase in area.

class Solution
{
public:
    int maxArea(vector<int> &height)
    {

        int maxArea = INT_MIN;

        int start = 0;
        int end = height.size() - 1;

        while (start < end)
        {

            int area = (end - start) * min(height[start], height[end]);
            if (area > maxArea)
            {
                maxArea = area;
            }

            if (height[start] < height[end])
            {
                start++;
            }
            else
            {
                end--;
            }
        }

        return maxArea;
    }
};

Time complexity : O(n)