re: Write better code: Day 1 - Highest Product VIEW POST

VIEW PARENT COMMENT VIEW FULL DISCUSSION

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.

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)
code of conduct - report abuse