Maximum product of 3 integers in an int array using Python 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 &gt; 0 and x &gt; pos[0]:
            pos[2], pos[1], pos[0] = pos[1], pos[0], x
        elif x &gt; 0 and x &gt; pos[1]:
            pos[2], pos[1] = pos[1], x
        elif x &gt; 0 and x &gt; pos[2]:
            pos[2] = x
        elif x &lt; 0 and x &lt; neg[0]:
            neg[1], neg[0] = neg[0], x
        elif x &lt; 0 and x &lt; neg[1]:
            neg[1] = x

    if neg[1] &lt; 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)
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 &gt; 0 and x &gt; pos[0]:
            pos[2], pos[1], pos[0] = pos[1], pos[0], x
        elif x &gt; 0 and x &gt; pos[1]:
            pos[2], pos[1] = pos[1], x
        elif x &gt; 0 and x &gt; pos[2]:
            pos[2] = x
        elif x &lt; 0 and x &lt; neg[0]:
            neg[1], neg[0] = neg[0], x
        elif x &lt; 0 and x &lt; neg[1]:
            neg[1] = x



The x &gt; 0 and x &lt; 0 will have the same result throughout.  So we can do just one of each.  

        if x &gt; 0:
            if x &gt; pos[0]:
                pos[2], pos[1], pos[0] = pos[1], pos[0], x
            elif x &gt; pos[1]:
                pos[2], pos[1] = pos[1], x
            elif x &gt; pos[2]:
                pos[2] = x
        elif x &lt; 0:
            if x &lt; neg[0]:
                neg[1], neg[0] = neg[0], x
            elif x &lt; 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 &gt; pos[2]:
            if x &gt; pos[0]:
                pos[2], pos[1], pos[0] = pos[1], pos[0], x
            elif x &gt; pos[1]:
                pos[2], pos[1] = pos[1], x
            else:
                pos[2] = x
        elif x &lt; neg[1]:
            if x &lt; 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 &gt; pos[2], it will also be greater than 0.  And x &lt; 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?