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]);
}

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