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

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

twoSum(arr); // 35

This question is an instance of the maximum subarray problem.

Brute Force

A naive approach is to use two loops to iterate through arr and multiply every integer by every other integer and then check for the maximum.

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

Note that for each iteration j is equal to i+1.

This solution works but at O(n^2) time complexity we can do much better.

Sorting

A better approach is to sort the array and then simply multiply the highest two integers which will be in the last and next-to-last position.

Use the built-in sort() array method has a time complexity of roughly O(n log n) (the actual speed depends on the browser-specific implementation).

// O(n log n) time
const twoSum = (arr) => {
  let sortedArr = arr.sort();
  return sortedArr[arr.length - 1] * sortedArr[arr.length - 2];
}

This is good but we can do even better. Note that we are first iterating the array O(n) and then sorting it O(log n). Why not do both at the same time?

Greedy

The best solution is to use a greedy approach where we track the highest and next-highest integers at each point in the array. This has a time complexity of O(n) since we only walk through the array once.

// O(n) time
const twoSum = (arr) => {
  let highestInt = 0;
  let nextHighestInt = 0;
  for (let i=0; i<arr.length; i++) {
    if (arr[i] > highestInt) {
      nextHighestInt = highestInt;
      highestInt = arr[i];
    } else if (arr[i] > nextHighestInt) {
      nextHighestInt = arr[i];
    } else {
      continue;
    }
  }
  return highestInt * nextHighestInt;
}

Conclusion

It’s very common in questions of this type to work through the optimal solutions in this manner. First find a brute-force approach, then see if sorting would improve things, and finally always consider a greedy approach which uses either an array or a hash map to store values. Chances are the greedy approach is the best one.



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