Efficient Solution for Finding Product of Largest Pair in Array

Question

Hello fellow developers,

I have written a function called max_product that aims to find the product of the largest two integers in a unique array of positive numbers. However, I believe there might be room for performance improvement in my current implementation. I would greatly appreciate your suggestions and feedback to help me optimize the code further.

Problem Statement: Rick wants a faster way to obtain the product of the largest pair in an array. The task is to create a performant solution that finds the product of the largest two integers in a unique array of positive numbers. For example, if given the array [2, 6, 3], the expected result should be 18, which is the product of [6, 3].

Code

def max_product(a):
 first_max = 0
 second_max = 0
 for x in a:
 if x > first_max:
 second_max = first_max
 first_max = x
 elif x > second_max:
 second_max = x
 return first_max * second_max

I look forward to your valuable insights and suggestions on how to improve the performance of this code, allowing it to efficiently find the product of the largest two integers in the array.

Thank you in advance for your help!

Answer 1

You can simplify your code by using heapq.nlargest. Since heapq is written in C, with a Python fallback, the code is likely faster than pure Python. The docs say which functions are likely to perform the best in different scenarios:

The latter two functions perform best for smaller values of n. For larger values, it is more efficient to use the sorted() function. Also, when n==1, it is more efficient to use the built-in min() and max() functions. If repeated usage of these functions is required, consider turning the iterable into an actual heap.

• qwr: Finding the k largest elements of an array is a classic application of "heapselect". You only need a min-heap of size 2 to find the two largest values afterwards. Since 2 is so small, maintaining a heap may not be worth it. Related stackoverflow.com/questions/42571302/…

Answer 2

You can almost halve the number of comparisons to expect for large uniform random input comparing to the runner-up first:

 if x > second_max:
 if x >= max_:
 second_max = max_
 max_ = x
 else:
 second_max = x

To keep with the definition of a product of a single factor, initialise both to 1 - positive should exclude 0.
I guess I'd initialise max_ = a[0] in a premature attempt to further improve run-time, needlessly excluding iterators as input.

• greybeard: (What? Not tagged algorithm any more? Bummer.)

Answer 3

If you sort the input, then the larger the item, the bigger the index of the item will be.

So the largest two items would simply be the last two items.

And you can simply access them by using indexing:

def largest_pair_product(arr):
 arr = sorted(arr)
 return arr[-2] * arr[-1]

For the product of the largest n numbers, use the following:

from functools import reduce
from operator import imul
def largest_product(arr, n):
 return reduce(imul, sorted(arr, reverse=True)[:n], 1)

By using the reverse order you can avoid using negative indexing. And you can get the arithmetic product of a list of numbers using reduce+imul to avoid using a for loop.

• greybeard: (You can even use sorted(iterable, reverse=True) avoiding mutation of arr.)