Coding Interview Question – Maximum Product of Three Numbers

Here is the Most Frequently Asked coding interview question by Big tech companies.

Question: Given an integer array nums, find three numbers whose product is maximum and return the maximum product.

Sample data:

Input:
nums = [1,2,3,4]
Output: 24

Input:
nums = [12,2,-4,5,6,0,-9,4]
Output: 432

Let’s talk about the solution. First we need to create different products.

In first sample Input, we can have 4 different combinantions.

Input : [1,2,3,4]

With first element 1, we can have,

1 x 2 x 3, 1 x 2 x 4, 1 x 3 x 4, 2 x 3 x 4

So Now if we compare

1 x 2 x 3 = 6,

1 x 2 x 4 = 8,

1 x 3 x 4 = 12,

2 x 3 x 4 = 24

We can easily say 24 is the answer. So we can use brute force solution to add this logic in action. We can use for loops and create all these combination and compare them and return the maximum.

const prodTest = (arr) => {
  
  let maxp = 0;
  
  for (let i = 0; i < arr.length; i++) {
    
    for (let j = i+1; j < arr.length; j++) {
      
      for (let k = j+1; k < arr.length; k++) {
        let product = arr[i] * arr[j] * arr[k];
        if (product > maxp) {
          maxp = product;
        }
        
      }
    }
  }
  return maxp;
}
console.log(prodTest([1,2,3]))

As we are using three for loops, time complexity would be O(N^3) which is not efficient programming. So we have to figure out the way where we can create those combinations by using just one for loop to achive O(N) Time complexity.

So to do that, we will create the highest , lowest point and then highest product of 2, lowest of product of 2 and current Max product of 3. And we can keep checking Max from either product3, current X highest product2, current X lowest product2.

With mathematical calculation we can easily check which combination will be maximum without checking all combinations.

Now let’s add that logic into action for working solution.

const productOfThree = (arr) => {
  if (arrayOfInts.length < 3) {
      throw new Error('Less than 3 items!');
    }
  
    // We're going to start at the 3rd item (at index 2)
    // So pre-populate highests and lowests based on the first 2 items
    // We could also start these as null and check below if they're set
    // but this is arguably cleaner
    
    let highest = Math.max(arr[0], arr[1]);
    let lowest = Math.min(arr[0], arr[1]);
    let highest2 = arr[0] * arr[1];
    let lowest2 = arr[0] * arr[1];
    
    // Except this one--we pre-populate it for the first *3* items
    // This means in our first pass it'll check against itself, which is fine
  
    let product3 = arr[0] * arr[1] * arr[2];
    
    // Walk through items, starting at index 2

  for (let i = 2; i < arr.length; i++) {
    const current = arr[i];
      // Do we have a new highest product of 3?
      // It's either the current highest
      // or the current times the highest product of two
      // or the current times the lowest product of two
    
     product3 = Math.max(product3, highest2 * current, lowest2 * current);
      
     // Do we have a new highest product of two?

    highest2 = Math.max(highest2, highest * current, lowest * current);
      
    // Do we have a new lowest product of two?

    lowest2 = Math.min(lowest2, highest * current, lowest * current);
      // Do we have a new highest?
    
highest =  Math.max(highest, arr[i]);
      // Do we have a new lowest?

    lowest = Math.min(lowest, arr[i]);
  }
  return product3;
}
console.log(productOfThree([12,2,-4,5,6,0,-9,4]));