Language C#
Sample Input [1,2,3,4]
Sample output = 24.
We should also think about negative numbers also.
Approaches
- One solution would be using three nested loops and find the highest product of 3 , which will give the runtime complexity of O(n3).
- Another solution would sort the array and find the highest product of 3, which will give run time complexity of O(nlogn).
But we can definitely think about something better solution.Let’s see if we can solve it using O(n)
Consider the array [-2, -3 , 4 , 6 ]
What you think which will be the three numbers which gave highest product of 3?
-2 * 4 * 6 = 24 ?
No. Because we have to think about two negative numbers -3 and -2, which will result a positive value and the expected output will be
-3 * -2 * 6 = 36.
Let’s analyze the logic of solution that we are going to implement. Later when you look at the final source code , you will get more clarity. Because this solution is little bit tricky.
Let’s find highestProductOf3 by hand from the same array.From the initial array , we will take first two values as highestProductOf2.Current value will be the third value. So our formula will be
highestProductOf3 = current * highestProductof2 ;
highgestProductOf3 = 4 * (-2 * -3) || 6 * (-2 * -3)
here 4 and 6 are current values while iterate through code.
And also -2 * -3 are the two numbers which will give highest product of 2 . On each iteration we need to track the maximum product of 2.
Let’s do it in the code.
public static int HighestProductOf3Redefined(int[] arrayOfInts)
{
int highestProductOf2 = arrayOfInts[0] * arrayOfInts[1]; //initializing
int highestProductOf3 = arrayOfInts[0] * arrayOfInts[1] * arrayOfInts[2];//initializing
//starting from thrid value
for (int product = 2; product < arrayOfInts.Length; product++)
{
var current = arrayOfInts[product];
highestProductOf3 = Math.Max(highestProductOf3, current * highestProductOf2);
}
return highestProductOf3;
}
Output will be : 36
How about this array [-2, -3 ,-4, 4, 6] ? Can I get highest product of 2 , which will be -4 * -3 =12?. No. Because we have to iterate and find the next highest product of 2. So let’s do that.
After the first iteration our current value is -4 .
Let’s do it by hand first
from the three values we can mark like below
-2 = lowestValue
-3 = highestValue
-4 = current
So next highestProductOf2 is either the current highestProductOf2 || current * highestValue || current * lowestValue. We can take the max value from it.
In the code I have initialized highest and lowestValue as first two items from the array.
public static int HighestProductOf3(int[] arrayOfInts)
{
int highestProductOf2 = arrayOfInts[0] * arrayOfInts[1];
int highestProductOf3 = arrayOfInts[0] * arrayOfInts[1] * arrayOfInts[2];
int highest = Math.Max(arrayOfInts[0] , arrayOfInts[1]);
int lowest = Math.Min(arrayOfInts[0], arrayOfInts[1]);
for (int product = 2; product < arrayOfInts.Length; product++)
{
var current = arrayOfInts[product];
highestProductOf3 = Math.Max(highestProductOf3, current * highestProductOf2);
highestProductOf2 = Math.Max(Math.Max(highestProductOf2, current * highest), current * lowest);
}
return highestProductOf3;
}
We are not done yet. To continue the iteration, we need the next highestValue and lowest value. It’s very simple
-2 = lowestValue
-3 = highestValue
-4 = current
highestValue = Math.Max(current,highestValue); = -3 lowestValue = Math.Min(current,lowestValue); = -4
public static int HighestProductOf3(int[] arrayOfInts)
{
int highestProductOf2 = arrayOfInts[0] * arrayOfInts[1];
int highestProductOf3 = arrayOfInts[0] * arrayOfInts[1] * arrayOfInts[2];
int highest = Math.Max(arrayOfInts[0] , arrayOfInts[1]);
int lowest = Math.Min(arrayOfInts[0], arrayOfInts[1]);
for (int product = 2; product < arrayOfInts.Length; product++)
{
var current = arrayOfInts[product];
highestProductOf3 = Math.Max(highestProductOf3, current * highestProductOf2);
highestProductOf2 = Math.Max(Math.Max(highestProductOf2, current * highest), current * lowest);
highest = Math.Max(highest, current);
// Do we have a new lowest?
lowest = Math.Min(lowest, current);
}
return highestProductOf3;
}
How about this array [-10, 1, 3, 2, -10] ?
what will be the expected output? it’s 300. But our method will return 6. So we missed one more thing lowestProductOf2 , there could be a chance of -10 * -10 * some value will also give highestProductOf3. In the current array it will -10 * -10 * 3 = 300.
Let’s do that,which is similar to highestProductOf2 , instead of max we have to find the min value and also we have to check the maximum current* lowestProductof2 to find highestProductOf3.
Final Solution
public static int HighestProductOf3(int[] arrayOfInts)
{
if (arrayOfInts.Length < 3)
{
throw new ArgumentException("Array should contain atleast 3 numbers", nameof(arrayOfInts));
}
int highest = Math.Max(arrayOfInts[0], arrayOfInts[1]);
int lowest = Math.Min(arrayOfInts[0], arrayOfInts[1]);
int highestProductOf2 = arrayOfInts[0] * arrayOfInts[1];
int lowestProductOf2 = arrayOfInts[0] * arrayOfInts[1];
int highestProductOf3 = arrayOfInts[0] * arrayOfInts[1] * arrayOfInts[2];
for (int i = 2; i < arrayOfInts.Length; i++)
{
int current = arrayOfInts[i];
highestProductOf3 = Math.Max(Math.Max(
highestProductOf3,
current * highestProductOf2),
current * lowestProductOf2);
highestProductOf2 = Math.Max(Math.Max(
highestProductOf2,
current * highest),
current * lowest);
lowestProductOf2 = Math.Min(Math.Min(
lowestProductOf2,
current * highest),
current * lowest);
highest = Math.Max(highest, current);
lowest = Math.Min(lowest, current);
}
return highestProductOf3;
}
Mad Programmer 