CODEWITHSUNDEEP
pythonpython-2.7python-3.xpython-itertools
Maverick
Maverick

Reputation: 2760

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

I was trying out a problem on hackerrank contest for fun, and there came 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 any other efficient way than this? As I am getting time out error on some test cases which I cant access (as its a small contest).

Upvotes: 5

Views: 4634

Answers (3)

Chris_Rands
Chris_Rands

Reputation: 41168

Here is an implementation following @User_Targaryen's logic. heapq returns the 2 largest and 2 smallest numbers in the list, mul operator returns the products of these 2 pairs of numbers, and max returns the largest of these 2 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

Upvotes: 2

mhawke
mhawke

Reputation: 87064

Just sort the list and select the largest of the products of 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 is a O(n log n) solution due to the sort. Someone else suggested a heapq solution which I found to be faster for lists longer than a few thousand random integers.

Upvotes: 4

User_Targaryen
User_Targaryen

Reputation: 4225

Iterate over the list and find the following:

Largest Positive number(a)

Second Largest Positive number(b)

Largest Negative number(c)

Second Largest Negative number(d)

Now, you will be able to figure out the maximum value upon multiplication, either a*b or c*d

Upvotes: 14

Related Questions