Container With Most Water

Problem: 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.

Example:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

Approach: We can use two pointers approach. One from the beginning and one from the end. The intuition here is the max area will always be limited by the shorter height vertical line so if we are taking a line from end and one line from the beginning, it is guaranteed that the area covered by these two vertical line will be 

Min(start_height, end_height) * (end - start). 

Now we can have a loop till start is less than end and in the loop we can calculate the current area using the above formula and update the max area if current area is greater. Now we need to decide which pointer we should move. Obviously we don't want to lose the greater height as it will always help to get us the max area so we will move the pointer whichever have the lesser height.

That's all!

Implementation in C#:

        public int MaxArea(int[] height)

    {

        int length = height?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        int low = 0, high = length - 1, maxArea = 0;

        while (low < high)

        {

            maxArea = Math.Max(Math.Min(height[low], height[high]) * (high - low), maxArea);

            if (height[low] <= height[high])

            {

                ++low;

            }

            else

            {

                --high;

            }

        }

        return maxArea;

    }

Complexity: O(n)