Coding Challenge: Maximum Pairwise Product

The first week of the Coursera Algorithmic Toolbox course is all about the coding challenge: maximum pairwise product.

What is Maximum Pairwise Product?

Given an list of positive whole numbers, find the largest product of two different numbers in the list.

What's it for?

Now I'm not sure if the challenge has any practical application, but it does serve as a great introduction on testing and debuging algorithms.

The Naive Solution

Here is our array of numbers:

const numArray = [2, 4, 5, 3];

With the above, it's pretty easy to see that the maximum pairwise product will be 20 or 4 * 5.

One way to solve this is to multiply every number by every other number and see which one is the largest. This is considered the naive solution. It works but it's not efficient. For every number in the array you have to multiply it by every other number. As the array grows, the number of operations grows by a lot.

Heres some code that does that:

const maxPairwiseProduct = numArray => {
  const len = numArray.length;
  let result = 0;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (i !== j) {
        const product = numArray[i] * numArray[j];
        if (product > result) {
          result = product;
        }
      }
    }
  }
  return result;

The Faster Solution

Since we are looking for the max pairwise product, it's straitforward enough to see that we can look for the 2 biggest numbers in the array. That means a lot fewer operations per item in the array. We just need to look for the two largest number and multiply those together to get the answer.

Here it is:

const maxPairwiseProductFast = numArray => {
  const len = numArray.length;
  let x = 0;
  let y = 0;
  for (let i = 0; i < len; i++) {
    if (numArray[i] >= x) {
      y = x;
      x = numArray[i];
    }
  }
  return result;
};

Comparing the two

Theoretically the faster solution is much faster over a large array. In the code sandbox you can check out how much faster it is.

The actual execution time will vary a bit, but as you can see the fast solution is much faster. With 10,000 items in the array, the naive solution takes somewhere between 300 and 400 milliseconds. The fast solution takes between 0 and 2 milliseconds.

Takeaways

• It's amazing how much faster some solutions are over others
• With two or more solutions, comparison is much easier