Find the largest product of an array

Question

This task is taken from www.interviewbit.com

Given an array of integers, return the highest product possible by multiplying 3 numbers from the array

Input:

array of integers e.g {1, 2, 3}

Example:

[0, -1, 3, 100, 70, 50]
=> 70*50*100 = 350000

NOTE: Solution will fit in a 32-bit signed integer

My approach: First sort the array, then return the maximum the following numbers: The product of the first two smallest numbers (because they could be negative) and the last number (largest) or the product of the three largest numbers.

My solution has a runtime of \$O(n \log n)\$ due to the sort and a space complexity of \$O(1)\$. I wonder whether there is a faster solution than \$O(n\log n)\$.

function highesProd(a) {
 a.sort((a,b) => a - b);
 return Math.max(a[0] * a[1] * a[a.length - 1], a[a.length - 3] * a[a.length - 2] * a[a.length - 1]);
}

• AJD: Can you explain your logic for your first check (The product of the first two smallest numbers and the last number)? Why not simply the product of the three largest numbers? And, depending on an assumption - why wouldn't the three smallest numbers still give the largest product?
• Roland Illig: Please add the test cases with which you tested your code. Please always do that when posting your code here.
• vnp: @AJD Because the two smallest numbers could be negative.
• greybeard: I wonder whether there is a faster solution than O(nlogn). Use an O(n) algorithm for k largest (smallest). As a matter of say what you mean (and don't repeat yourself), put * a[a.length - 1] outside the max().
• greybeard: (Check the spelling of your procedure's name.)

Answer 1

Yes you can do this in O(n) time. You just need to scan through the array 1 time and track the 3 largest numbers and 2 smallest numbers. At the end compare the product of the 2 smallest * the largest vs the product of the 3 largest. One of those will be the max product of three numbers.

You only have to track the 2 smallest because the product of 3 negative will be negative. I put in checks to ensure the neg1 an neg2 are negative numbers, but this isn't strictly necessary for just finding the max product. Just storing the 2 smallest numbers will still return the correct answer for this problem.

I think the purpose of this question in an interview setting may be to show that sometimes the a longer block of code may run faster that a one liner.

let arr = [-2, 7, 3, 4,4,4,2,-11];
console.log(maxProduct(arr));
function maxProduct(arr) {
 //special cases
 if (arr.length<3) return null;
 if (arr.length===3) return arr.reduce( (a,b) => a*b);
 if (arr.length===4) return arr.sort((a, b) => a - b).slice(1,4).reduce( (a,b) => a*b);
 //otherwise
 let seeds = arr.slice(0,5).sort((a, b) => a - b);
 let [min1, min2, max3, max2, max1] = seeds;
 for (let i = 5; i < arr.length; i++) {
 let cur = arr[i];
 if (cur >= max1) {
 max3 = max2;
 max2 = max1;
 max1 = cur;
 } else if (cur >= max2) {
 max3 = max2;
 max2 = cur;
 } else if (cur >= max3 ) {
 max3 = cur;
 } else if (cur <= min1) {
 min2 = min1;
 min1 = cur;
 } else if (cur <= min2) {
 min2 = cur
 }
 }
 return Math.max(min1 * min2 * max1, max1 * max2 * max3);
}

• VisualMelon: I don't think this is strictly correct, because if it is supplied with 3 numbers one of which one or three are negative, then it will return 0 (when presumably it should return the negative product of all three). You might consider Math.max(neg1 * neg2 * max1, max1 * max2 * max3) at the end, which is a little clearer and easier to maintain.
• Landon B: I added some check for special cases and changed the choice of seed values for the algorithm.