Given an array of positive integers representing a height of a container we want to find the largest area of with most water.
Example:
A= {5,3,6,4,2} Ans = 12
Solution
As it is indicated in the above picture, the largest area that can be constructed with the given heights is 12 (see yellow highlighted rectangle)
We can use a brute force approach first.
We will need a nested loop wit i and j. We will go one by one and compute the area of each rectangle that can be constructed with i and j.
Area = min height of i and j times the horizontal distance covered by i and j
We take the minimum because we cannot draw a rectangle if we take the longest height.
public int MaxAreaBruteForce(int[] height)
{
int maxarea = 0;
int min = 0;
//brute force
for (int i = 0; i < height.Length; i++)
{
for (int j = i + 1; j < height.Length; j++)
{
min = Math.Min(height[i], height[j]);
maxarea = Math.Max(maxarea, min * (j - i));
}
}
return maxarea;
}
The optimal approach will be based on two pointers.
Instead of checking areas n*n times where n is the length of the given array, we can optimize that by passing through the array only one times using two pointers.
We will have i going forward starting from index 1 and j coming backwards staring from n and we basically do what we did in the body of the inner loop in the brute force solution. The only thing we check is we need to increment i or decrement j based on who will give us the biggest area.
public static int MaxAreaOofNWorks(int[] height)
{
int maxarea = 0;
int min = 0;
int i = 0;
int j = height.Length - 1;
while (i < j)
{
min = Math.Min(height[i], height[j]);
maxarea = Math.Max(maxarea, min * (j - i));
if (height[i] < height[j])
i++;
else
j--;
}
return maxarea;
}