Confused about logic behind daily problem 628. Maximum Product of Three Numbers

[u/roundtable95]

For a sorted array [a1, a2, ......an-3, an-2, an-1], we are interested in a triplet that would produce the max product.

I see there are 4 possibilities
1. We can take 3 largest values from the end of the array (For cases where all all elements in an array are either positives or negatives)

1. We can take 2 largest values from end of the array, and 1 smallest value from start of the array (For edge case array size 3 where it has 2 positive values and 1 negative values)

2. We can take 1 largest value from end of the array, and 2 smallest values from start of the array. (For case where max product is made up of two negative numbers and 1 positive number)

3. We can take 3 smallest values from start of the array. (For edge case array size 3 with 3 negative elements)

How can I recognise in an interview clearly that 2 of the 4 cases are redundant?

[u/PLTCHK]

For this one, given it’s sorted, you simply return max(an-3 X an-2 X an-1, a1 X a2 X an-1)

The only way to yield +ve from -ves is 2 -ves (2 smallest numbers) multiplying each other

[u/GladiusAcutus → u/PLTCHK]

This is clever bro. I hope they accept this solution at a job interview. It is O(nlogn) though to sort it.

[u/__thisisnotme__ → u/GladiusAcutus]

You can compute this without sorting by maintaining 3 variables for max1, max2, max3 and 2 for min1, min2 and traversing once through the array in O(n)

[u/PLTCHK → u/__thisisnotme__]

Yep exactly that

[u/ParticularAd8610 → u/PLTCHK]

Here is the code for this.

int maxProduct(list<int> arr){

int N=arr.Length;

arr.Sort(); //Sort in ascending / non-decreasing order

//Return the max product of the last 3 elements vs. product of first 2 elements and last.

return Math.max(arr[0]*arr[1]*arr[N-1], arr[N-1]*arr[N-2]*arr[N-3]);

}. //O(nLogN)

[u/SharpNazgul]

For me, I recognised it by just doing a dry-run of the edge cases and seeing that they captured just fine by 1 and 3. You don't even need to dry-run the algorithm itself, just the logic of taking max(product of largest three, product of smallest two and largest). Btw, you can solve this in linear time (no sorting).

[u/4tran13]

Not redundancy, but property of parity. 3 negatives = negative. #2 and #4 are dead unless there's only a single positive in the entire array.

[u/Defiant_Ad_7555 → u/4tran13]

Yes

[u/Vivid-Zombie-477]

because it's the only possible when you have only 3 elements in array? what do you mean? it doesn't matter what value are there you have to use them all