# JavaScript Two Sum: Find the Highest Product of Two Numbers

**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.

A related version of 2Sum is Find All Pairs That Sum to a Target Value.

## 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.