Solution to Codility lesson4-exercise1 Max Product of Three problem, link to Codility problem and complete solution at the end of the post.

**Definitions:**

**Product: **Product of three elements of *A, *

*,* such that

*. *Notice that saying that

, it’s the same that saying that the elements can’t be the same, and only this.

** Problem:**Define a function

*solution*with input

*A*, such that

*solution*returns the maximal

*product*.

- Expected worst-case time complexity is
*O(N*log(N))*; - Expected worst-case space complexity is
*O(1);*

**Elements of input arrays can be modified.**** **

### Analysis:

To solve this problem we have to find the *maxs*, but also we have to find two mins, this is because *a* and *b* being the mins and lesser than zero, *a*b*max(A)* could be greater than the product of the three maximums. We have three possible outcomes here.

With three elements the solution is the product of this three elements.

10 11 |
if N == 3: return A[0]*A[1]*A[2] |

The second outcome is if we have four elements, by choosing the three maximums we only have one possible minimum. And the result will be the max between the product of the maximums and the max(*A*)*min(*A*)*(the third greater element).

61 62 63 |
if mins[1] == 1001: # if maxs[2] < 0, mins[0]*maxs[2] > 0, and could be greater than maxs[1]*maxs[2] return max(maxs[0]*maxs[1]*maxs[2], maxs[0]*maxs[2]*mins[0]) |

We rule out the second element of *maxs*, because if min is positive the result will be the product of the maximums, if min is negative and the others are positive this is not a valid solution either, so the second and the third must be negative. If both are negative the third is the right choice, because both being negative the result of the product with the third will always be greater or equal to the product with the second.

The third outcome is

. And the result will be the max between the product of the maximums and the product of max(*A*) times the product of the minimums as we stated above.

65 66 |
# If mins < 0, mins[0]*mins[1] > 0 and could be greater than maxs[1]*maxs[2] return max(maxs[0]*maxs[1]*maxs[2], maxs[0]*mins[0]*mins[1]) |

So now we only have to find the *maxs* and *mins*. First we mount the *maxs* array, with the first three elements of *A.*

*
*

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
# Prepares the maxs array if maxs[0] == A[0]: maxs[1] = max([A[1], A[2]]) if maxs[1] == A[1]: maxs[2] = A[2] else: maxs[2] = A[1] elif maxs[0] == A[1]: maxs[1] = max([A[0], A[2]]) if maxs[1] == A[0]: maxs[2] = A[2] else: maxs[2] = A[0] else: maxs[1] = max([A[0], A[1]]) if maxs[1] == A[0]: maxs[2] = A[1] else: maxs[2] = A[0] |

Then we iterate through the others elements of *A, *comparing them with the elements of *maxs *array, and shifting the *maxs *according to the position of the element. Or comparing them with the *mins* array’s elements.

38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
# Iterate to find the three maxs and two mins if it exists # Shift maxs if A[k] is greter than any element of maxs # maxs[2] could be a min. for k in xrange(3, N): if A[k] > maxs[0]: switch(mins, maxs[2]) maxs[2] = maxs[1] maxs[1] = maxs[0] maxs[0] = A[k] elif A[k] > maxs[1]: switch(mins, maxs[2]) maxs[2] = maxs[1] maxs[1] = A[k] elif A[k] > maxs[2]: switch(mins, maxs[2]) maxs[2] = A[k] else: switch(mins, A[k]) |

After that, the lesser element of *maxs *that just have been pushed out could be a min so that’s when we compare this element with the *mins *array in the switch method.

69 70 71 72 73 74 75 |
# Shift mins if n is lesser than any elements of mins def switch(mins, n): if n < mins[0]: mins[1] = mins[0] mins[0] = n elif n < mins[1]: mins[1] = n |

Because we visit every element of A only once the total time complexity is *O(N), * and the numbers of operations inside the loop doesn’t depend on the input size. Codility gives O(N*log(N)) time complexity, and that’s probably because of the number of operations that happens inside the loop. But the maximum of operations inside it is 8, so in the worst case for every loop we got 8 operations that gives us at most *8*N * operations, so for *N > 512, *its execution time is smaller than *N*log(N)*.

For the space complexity we have *O(1) *because the variables doesn’t depend on the input size.

Since this problem is part of the Sorting session, it could be solved in O(N*log(N)) using sort with this lines of code.

1 2 3 4 |
def solution(A): A.sort() return max(A[-1]*A[-2]*A[-3], A[0]*A[1]*A[-1]) |

I ran both solutions to compare and this what i got from Codility analysis,

O(N) |
O(N*log(N)) |

Strangely with greater inputs the times get’s bigger for the possible *O(N)* solution.

**Complete Solution:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
# Name: MaxProductOhThree # Link: https://codility.com/demo/take-sample-test/max_product_of_three/ def solution(A): N = len(A) maxs = [0]*3 mins = [1001]*2 if N == 3: return A[0]*A[1]*A[2] maxs[0] = max([A[0], A[1], A[2]]) # Prepares the maxs array if maxs[0] == A[0]: maxs[1] = max([A[1], A[2]]) if maxs[1] == A[1]: maxs[2] = A[2] else: maxs[2] = A[1] elif maxs[0] == A[1]: maxs[1] = max([A[0], A[2]]) if maxs[1] == A[0]: maxs[2] = A[2] else: maxs[2] = A[0] else: maxs[1] = max([A[0], A[1]]) if maxs[1] == A[0]: maxs[2] = A[1] else: maxs[2] = A[0] # Iterate to find the three maxs and two mins if it exists # Shift maxs if A[k] is greter than any element of maxs # maxs[2] could be a min. for k in xrange(3, N): if A[k] > maxs[0]: switch(mins, maxs[2]) maxs[2] = maxs[1] maxs[1] = maxs[0] maxs[0] = A[k] elif A[k] > maxs[1]: switch(mins, maxs[2]) maxs[2] = maxs[1] maxs[1] = A[k] elif A[k] > maxs[2]: switch(mins, maxs[2]) maxs[2] = A[k] else: switch(mins, A[k]) # If has only one minimum if mins[1] == 1001: # if maxs[2] < 0, mins[0]*maxs[2] > 0, and could be greater than maxs[1]*maxs[2] return max(maxs[0]*maxs[1]*maxs[2], maxs[0]*maxs[2]*mins[0]) # If mins < 0, mins[0]*mins[1] > 0 and could be greater than maxs[1]*maxs[2] return max(maxs[0]*maxs[1]*maxs[2], maxs[0]*mins[0]*mins[1]) # Shift mins if n is lesser than any elements of mins def switch(mins, n): if n < mins[0]: mins[1] = mins[0] mins[0] = n elif n < mins[1]: mins[1] = n |

*Time Complexity O(N*log(N))*

*Space Complexity O(1)*

## One thought on “Codility – Max Product of Three”