Maximum product of 3 integers in an int array using Python

Question

This is an interview question from Interview Cake:

Given a list_of_ints, find the highest_product you can get from three of the integers. The input list_of_ints will always have at least three integers.

I'm looking for feedback on how to improve readability, space, time complexity, using Python idiomatic code and general feedback.

import unittest


def highest_product(list_of_ints):
    pos = [0, 0, 0]
    neg = [0, 0]

    for x in list_of_ints:
        if x > 0 and x > pos[0]:
            pos[2], pos[1], pos[0] = pos[1], pos[0], x
        elif x > 0 and x > pos[1]:
            pos[2], pos[1] = pos[1], x
        elif x > 0 and x > pos[2]:
            pos[2] = x
        elif x < 0 and x < neg[0]:
            neg[1], neg[0] = neg[0], x
        elif x < 0 and x < neg[1]:
            neg[1] = x

    if neg[1] < 0:
        max_product = max([x * neg[0] * neg[1] for x in pos])
        max_product = max(pos[0] * pos[1] * pos[2], max_product)
    else:
        max_product = pos[0] * pos[1] * pos[2]

    return max_product


class TestHighestProduct(unittest.TestCase):
    def test_highest_product(self):
        self.assertEqual(highest_product([6, -1, -1, -2, 0]), 12)


if __name__ == '__main__':
    unittest.main(verbosity=2)

Answer 1

First, I'm not a Python guy, so please don't use anything I say to suggest style. I'm trying to copy the style that you used with minor algorithmic differences. I apologize if I make a mistake in doing so.

        if x > 0 and x > pos[0]:
            pos[2], pos[1], pos[0] = pos[1], pos[0], x
        elif x > 0 and x > pos[1]:
            pos[2], pos[1] = pos[1], x
        elif x > 0 and x > pos[2]:
            pos[2] = x
        elif x < 0 and x < neg[0]:
            neg[1], neg[0] = neg[0], x
        elif x < 0 and x < neg[1]:
            neg[1] = x

The x > 0 and x < 0 will have the same result throughout. So we can do just one of each.

        if x > 0:
            if x > pos[0]:
                pos[2], pos[1], pos[0] = pos[1], pos[0], x
            elif x > pos[1]:
                pos[2], pos[1] = pos[1], x
            elif x > pos[2]:
                pos[2] = x
        elif x < 0:
            if x < neg[0]:
                neg[1], neg[0] = neg[0], x
            elif x < neg[1]:
                neg[1] = x

Now we do at most four comparisons and may do as few as two. The original also did at least two and could do as many as eight (if greater than 0 but smaller than the three largest positive values).

We can actually reduce that and keep the same behavior

        if x > pos[2]:
            if x > pos[0]:
                pos[2], pos[1], pos[0] = pos[1], pos[0], x
            elif x > pos[1]:
                pos[2], pos[1] = pos[1], x
            else:
                pos[2] = x
        elif x < neg[1]:
            if x < neg[0]:
                neg[1], neg[0] = neg[0], x
            else:
                neg[1] = x

Still the same minimum of two, but the maximum drops to three. We get the same behavior because both values are initialized to 0 and only move in one direction from there. So if x > pos[2], it will also be greater than 0. And x < neg[1] means that it is less than 0.

Perhaps you've noticed a problem though. This code does not solve the problem correctly. But it does produce the same result as your original code, so the bug is in the original code.

Bug

You have one unit test:

class TestHighestProduct(unittest.TestCase):
    def test_highest_product(self):
        self.assertEqual(highest_product([6, -1, -1, -2, 0]), 12)

But what if you add a second that says

        self.assertEqual(highest_product([-6, -1, -1, -2]), -2)

Your code will fail, returning 0 instead of -2. This is because you initialize the arrays to 0, but you don't verify that there are non-negative members of the array. 0 is not a valid answer here.

If all the numbers are negative, then max_product is negative when

        max_product = max(pos[0] * pos[1] * pos[2], max_product)

So the first product is 0 * 0 * 0, which is 0. 0 will be greater than the product of any three negative numbers. This incorrect answer will hide any possible correct answer.

        max_product = max([x * neg[0] * neg[1] for x in pos])

This is also wrong. Even if you fix the other line, this may multiply the wrong three numbers. For example, consider the input above. The neg variable would hold -6 and -2 (the two smallest negative numbers). So the max product would be -6 * -2 * -1 = -12. But the actual answer should be -2 * -1 * -1 = -2, which is the product of the three largest numbers.

I'll leave it up to you to think through the ramifications of possible fixes. You may want to consider when

        max_product = pos[0] * neg[0] * neg[1];

will give a different result than checking every x. Also, how do you tell when pos[0] * pos[1] * pos[2] should and should not be zero? In particular, consider if it matters if those three values are positive.

To what else could you initialize pos other than 0?

Answer 2

Your code is not readable at all, due to the use of the fairly non-descriptive variables pos and neg and in general how dense it is, with pos[foo] and neg[bar] everywhere.

Something that would assist in the readability, and make it more idiomatic would be to use combinations from the itertools module to generate the 3-integer sublists of the list_of_ints, and then process the sublists (that part is fairly simple btw).

I don't know how this more readable algorithm would perform, but the complexity of operations being done are simple enough that the difference between more time-efficient algorithms and it are miniscule.

Answer 3

I don't want to repeat mdfst13's very good answer. So I'll skip changing the if and start from:

if x > pos[2]:
    if x > pos[0]:
        pos[2], pos[1], pos[0] = pos[1], pos[0], x
    elif x > pos[1]:
        pos[2], pos[1] = pos[1], x
    else:
        pos[2] = x
elif x < neg[1]:
    if x < neg[0]:
        neg[1], neg[0] = neg[0], x
    else:
        neg[1] = x

If we were to ignore algorithmic complexity, you can think of this as pos.insert. If x > pos[0] the index is 0. If x > pos[1] then the index is 1, otherwise it's 2. But as this increases the size of the array you'd have to remove an item, say through del pos[3:]. And so you can get:

if x > pos[2]:
    index = next(i for i, v in enumerate(pos) if x > v)
    pos.insert(index, x)
    del pos[3]
elif x < neg[1]:
    index = next(i for i, v in enumerate(neg) if x < v)
    neg.insert(index, x)
    del neg[2]

This is a bit long-winded, and so we can look at bisect. This works in almost the same way as above. And so we could change the code to:

if x > positive[0]:
    bisect.insort(positive, x)
    del positive[0]
elif x < negative[-1]:
    bisect.insort(negative, x)
    del negative[2]

This is much simpler than the original, but still requires del. This makes me think that it's not as efficient as yours was. As we now have at least two more operations than yours did. As the code shifts data to a new index, and then we remove that index. This reminds me of how you create an insertion sort.

So we could change this to use a heap queue via heapq. Which can further simplify the code:

if x > positive[0]:
    heapq.heapreplace(positive, x)
elif x < 0 and -x > negative[0]:
    heapq.heapreplace(negative, -x)

With both the above you may need to change the second part of your code slightly.

---

In all the above methods we're creating a priority queue. And so the maximum should always be in a constant place. Of either positive[0] or positive[-1]. Excluding the bug. To get the largest product you either use all positive numbers, or two negatives and the largest positive. And so you shouldn't need to create a product for all the positive numbers.

I'd also make a function product, which multiplies all the numbers passed into it together.

And so I'd use:

from heapq import heapreplace
from functools import reduce
from operator import mul

def product(nums):
    return reduce(mul, nums)

def max_product(numbers):
    positive = [0, 0, 0]
    negative = [0, 0]
    for x in numbers:
        if x > positive[0]:
            heapreplace(positive, x)
        elif x < 0 and -x > negative[0]:
            heapreplace(negative, -x)

    return max(product(positive[-1:] + negative), product(positive))

Answer 4

Seeing as the question on interview cake doesn't mention a requirement for complexity or efficiency, I would default on maximizing code readability and developer time leading to the less efficient version:

import unittest
from itertools import permutations
from operator import mul
from functools import reduce

def highest_product(list_of_ints):
    return max(reduce(mul, seq) for seq in permutations(list_of_ints, 3))


class TestHighestProduct(unittest.TestCase):
    def test_highest_product(self):
        self.assertEqual(highest_product([6, -1, -1, -2, 0]), 12)
        self.assertEqual(highest_product([-6, -1, -1, -2]), -2)

if __name__ == '__main__':
    unittest.main(verbosity=2)

Edit

This is using combinations instead of permutations thereby increasing efficiency. See comment below.

import unittest
from itertools import combinations
from operator import mul
from functools import reduce

def highest_product(list_of_ints):
    return max(reduce(mul, seq) for seq in combinations(list_of_ints, 3))


class TestHighestProduct(unittest.TestCase):
    def test_highest_product(self):
        self.assertEqual(highest_product([6, -1, -1, -2, 0]), 12)
        self.assertEqual(highest_product([-6, -1, -1, -2]), -2)

if __name__ == '__main__':
    unittest.main(verbosity=2)

Answer 5

You can simplify a building of "pos" and "neg" lists:

• use list comprehensions to build list of positive/negative integers
• extend list (minimum length of positive list is 3 / negative is 2). [0] * 3 produce [0, 0, 0]
• sort positive list in reverse order / negative list in normal order
• cut positive list to 3 elements / negative list to 2 elements

Code:

pos = [x for x in list_of_ints if x > 0]
pos.extend([0] * 3)
pos.sort(reverse=True)
pos = pos[:3]

neg = [x for x in list_of_ints if x < 0]
neg.extend([0] * 2)
neg.sort(reverse=False)
neg = neg[:2]

---

• if length of list_of_ints < 3, extend list_of_ints
• sort in reverse order - first 3 elements is pos list
• neg list does not have to be sorted - last 2 elements is neg list
• because neg list is in reverse order, You must check first element, not last

Code:

list_of_ints.extend([0] * 3)
list_of_ints.sort(reverse=True)
pos = list_of_ints[:3]
neg = list_of_ints[-2:]

if neg[0] < 0: