How to find the maximum product of two items in a list?

Question

I was looking for a problem in a hackerrank contest for fun, and this question came up with this question. I used itertools for this, here is the code:

import itertools l = [] for _ in range(int(input())): l.append(int(input())) max = l[0] * l[len(l)-1] for a,b in itertools.combinations(l,2): if max < (a*b): max = (a*b) print(max) 

Is their another effective way than this? Since I get a time error on some test cases that I cannot get (like a little competition).

Answer 1

Here is the implementation following @User_Targaryen's logic. heapq returns the 2 largest and 2 smallest numbers in the list, the mul operator returns the products of these two pairs of numbers, and max returns the largest of these two products.

 >>> import heapq >>> from operator import mul >>> l = [2,40,600,3,-89,-899] >>> max(mul(*heapq.nsmallest(2,l)),mul(*heapq.nlargest(2,l))) 80011 # -899*-89 = 80011 

Answer 2

Scroll through the list and find the following:

Maximum positive number (a)

Second highest positive number (b)

Largest negative number (c)

Second largest negative number (d)

Now you can determine the maximum value when multiplying, either a*b or c*d

Answer 3

Just sort the list and select the largest of the products from the last 2 items in the list and the first 2 items in the list:

 from operator import mul numbers = [10, 20, 1, -11, 100, -12] l = sorted(numbers) # or sort in place with numbers.sort() if you don't mind mutating the list max_product = max(mul(*l[:2]), mul(*l[-2:])) 

This solution is O (n log n) due to sorting. Someone else suggested a heapq solution, which, it seemed to me, was faster for lists longer than several thousand random numbers.