Container With The Most Water

Finding the max area of water the container can contain.

Problem Statement

 

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.

 

 

 

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. 

 

Note

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

 

Solution

 

The simplest and most convenient approach to this problem is using a nested loop over the given array, meaning starting from the first element loop of the entire array to find whether the previously stored area is more than the current area. And we can find the area by taking the difference of the array indexes, which represent the x-axis, and multiplying it with the minimum of the two values at that index, representing the y-axis. Given below is a code sample illustrating this algorithm in C#, 

class Program
{
    static void Main(string[] args)
    {
        int[] containerCoordinates = new int[] { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
        int maxWaterArea = MaxArea(containerCoordinates);
    }
    public static int MaxArea(int[] height)
    {
        int maxArea = 0;
        for(int i = 0; i < height.Length; i++)
        {
             for (int j = 0; j < height.Length; j++)
                maxArea = Math.Max(maxArea, Math.Abs(i - j) * Math.Min(height[i], height[j]));
        }
        return maxArea;
    }
}