## DEV Community is a community of 615,372 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Write better code: Day 1 - Highest Product

Arjun Rajkumar Updated on ・1 min read

This post originally appeared on Arjun Rajkumar's blog. Arjun is a web developer based in Bangalore, India.

--

### Day 1: Question 2

Given an array of integers, find the highest product you can get from three of the integers.

The input array_of_ints will always have at least three integers.

Question from InterviewCake

## Discussion (9)

Arjun Rajkumar

This was the logic:

• Get three highest inputs - multiply
• I could sort and choose highest 3 - but sort is worse than O[n] - so .. Trying something else.
• Go thru each int one by one. - o[n]
• See if the current int is greater than previous max_1 : then with max_2: then with max_3
• Return product.
• O[1] space as storing fixed.
• O[n] time

# Examples:

[10, 7, 5, 8, 11, 9] -> 990 ;
[10, 7, 100] -> 7000 ;
[-10, 7, 100] -> -7000;
[-10, 7, 100, 1] -> 700;

Mihail Malo • Edited

I feel like much less comparisons can be done by keeping track of the lowest number:

``````def get_product_of_3(array_of_ints):
maxes = [0, 0, 0]
min_val = 0
min_i = 0
for int in array_of_ints:
if int > min_val:
maxes[min_i] = int
min_i, min_val = min(enumerate(maxes), key=lambda x: x[1])

return maxes[0]*maxes[1]*maxes[2]
``````

Sorry, I replaced one language I don't know with a similar language I don't know because I didn't want to install ruby.

Arjun Rajkumar

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, 1, 3, 2] -> should give 60.

Mihail Malo • 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 • 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)
``````
Arjun Rajkumar • Edited

Just realised that my original attempt was wrong !

For two negative integers e.g [-5, -4, 1, 3, 2] the correct answer is 60.
But the code above gives 6.

So.. need to change.

Arjun Rajkumar

Ended up doing this by checking if the product of current number with the previous stored two numbers is greater than the the current max.

1. Highest number
2. Lowest number
3. Highest product of two numbers.
4. Lowest product of two numbers.
5. Max product of previous 3 numbers.

Then with each new number I check if the max product is greater than previous, and also update each. As there are negative numbers, the lowest product of two numbers can suddenly give the max product when multiplied with the current.

This is O[n] which is still better than sort which is O[nlogn]