Discussion on: Write better code: Day 1 - Highest Product

View post

Replies for: Thanks Mihail. This looks much more neat. Will test it out later. But did you test the case if two negative numbers are passed? For e.g [-5, -4, ...

Mihail Malo • Dec 6 '18 • Edited

Yes, I see the problem.
So far I see three cases:

The biggest product is all positives.
The biggest product is two smallest negatives and one biggest positive.
The biggest product is negative itself(!), which can happen in at least these two distinct cases:
- [n,p,p]: There are only 3 inputs, one of them negative. For any length 3 input we should just return the input anyway, implicitly or explicitly.
- [n,n,n...]: There are 3 or more inputs, none of which are positive. In this case we should return the 3 negative numbers closest to 0 (3 biggest numbers, same as the all-positive happy case)

I'll post a fix later, let's see how messy.

Mihail Malo • Dec 6 '18 • Edited

Okay, I think I got it:

import math


def get_product_of_3(array_of_ints):
    if len(array_of_ints) < 3:
        return 0

    min_max = -math.inf
    min_max_i = 0
    maxes = [min_max, min_max, min_max]
    max_neg = 0
    max_neg_i = 0
    negs = [0, 0]
    for int in array_of_ints:
        if int > min_max:
            maxes[min_max_i] = int
            min_max_i, min_max = min(enumerate(maxes), key=lambda x: x[1])
        if int < max_neg:
            negs[max_neg_i] = int
            max_neg_i, max_neg = max(enumerate(negs), key=lambda x: x[1])

    prod_maxes = maxes[0]*maxes[1]*maxes[2]
    prod_negs = negs[0]*negs[1]
    # This condition is only needed for `[n,p,p]`, to not return the invalid product of `0` when the product of maxes is negative. 
    if prod_negs != 0:
        return max(prod_negs*max(maxes), prod_maxes)
    return prod_maxes

If we instead explicitly return the product of 3 inputs, this condition is no longer needed:

import math


def get_product_of_3(array_of_ints):
    if len(array_of_ints) < 3:
        return 0
    if len(array_of_ints) == 3:
        return array_of_ints[0]*array_of_ints[1]*array_of_ints[2]

    min_max = -math.inf
    min_max_i = 0
    maxes = [min_max, min_max, min_max]
    max_neg = 0
    max_neg_i = 0
    negs = [0, 0]
    for int in array_of_ints:
        if int > min_max:
            maxes[min_max_i] = int
            min_max_i, min_max = min(enumerate(maxes), key=lambda x: x[1])
        if int < max_neg:
            negs[max_neg_i] = int
            max_neg_i, max_neg = max(enumerate(negs), key=lambda x: x[1])

    prod_maxes = maxes[0]*maxes[1]*maxes[2]
    prod_negs = negs[0]*negs[1]
    return max(prod_negs*max(maxes), prod_maxes)

Another possible optimization, for input such as [...-100,-99,-98,-97,1,-96,-95,-94...] is to stop expecting the "all negatives" case. This can easily be done by resetting all negative maxes to 0, so that incoming negatives are always smaller:

import math


def get_product_of_3(array_of_ints):
    if len(array_of_ints) < 3:
        return 0
    if len(array_of_ints) == 3:
        return array_of_ints[0]*array_of_ints[1]*array_of_ints[2]

    awaiting_not_negatve = True
    min_max = -math.inf
    min_max_i = 0
    maxes = [min_max, min_max, min_max]
    max_neg = 0
    max_neg_i = 0
    negs = [0, 0]
    for int in array_of_ints:
        if int > min_max:
            maxes[min_max_i] = int
            if awaiting_not_negatve and int >= 0:
                awaiting_not_negatve = False
                for i, v in enumerate(maxes):
                    if v < 0:
                        maxes[i] = 0
            min_max_i, min_max = min(enumerate(maxes), key=lambda x: x[1])
        if int < max_neg:
            negs[max_neg_i] = int
            max_neg_i, max_neg = max(enumerate(negs), key=lambda x: x[1])

    prod_maxes = maxes[0]*maxes[1]*maxes[2]
    prod_negs = negs[0]*negs[1]
    return max(prod_negs*max(maxes), prod_maxes)