Question: Given an array of integers, find the highest product you can get from three of the integers. Write a function threeSum that solves this.

const arr = [-1, 0, 2, 5, 3, -4];

threeSum(arr); // 30

Brute Force

We could use three loops to iterate through arr and create a maxProduct of each integer times each other integer and each other, other integer.

// O(n^3) time
const threeSum = (arr) => {
  let maxProduct = 0;
  for (let i=0; i<arr.length - 2; i++) {
    for (let j=i+1; j<arr.length - 1; j++) {
      for (let k=j+1; k<arr.length; k++) {
        let product = arr[i] * arr[j] * arr[k];
        if (product > maxProduct) {
          maxProduct = product;
        }
      }
    }
  }
  return maxProduct;
}

Sorting

If we sort the array–which we can do in O(n log n) time–then we can simply multiply the three largest integers at the end.

// O(n log n)
const threeSum = (arr) => {
  sortedArr = arr.sort((a, b) => a - b);
  let len = arr.length;
  let maxProduct = sortedArr[len-1] * sortedArr[len-2] * sortedArr[len-3];
  return maxProduct;
}

Greedy Approach

If we use a greedy approach we can obtain O(n) time. We need to track both the highestProductOf2 and lowestProductOf2 since there can be negative numbers in our array. We’ll also track the highestProductOf3 and the absolute highest and lowest.

const threeSum = (arr) => {

    let highest = Math.max(arr[0], arr[1]);
    let lowest  = Math.min(arr[0], arr[1]);
    let highestProductOf2 = arr[0] * arr[1];
    let lowestProductOf2  = arr[0] * arr[1];
    let highestProductOf3 = arr[0] * arr[1] * arr[2];

    for (let i=2; i<arr.length; i++) {
        let current = arr[i];

        highestProductOf3 = Math.max(
            highestProductOf3,
            current * highestProductOf2,
            current * lowestProductOf2
        );

        highestProductOf2 = Math.max(
            highestProductOf2,
            current * highest,
            current * lowest
        );

        lowestProductOf2 = Math.min(
            lowestProductOf2,
            current * highest,
            current * lowest
        );

        highest = Math.max(highest, current);

        lowest = Math.min(lowest, current);
    }

    return highestProductOf3;
}

Conclusion

This problem follows the classic brute force -> sorting -> greedy progression that you should look for in most interview questions. Try to solve it first using the simplest possible approach. Consider whether sorting or searching would improve the time complexity. And finally think about using a hash map and/or greedy approach.

Also note that the current solutions to not properly handle negative numbers. Always good to ask on the range for the initial array and handle appropriately as needed!



Want to improve your JavaScript? I have a list of recommended JavaScript books.