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.