```
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; }