Codility - Max Product of Three

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

Definitions:
\mathbf{A} = \{x \in \mathbb{Z}\ |-1,000\leq x \leq 1000\land |A| = N\},\mathbf{A}\, is\, a\, multiset.
\{N \in \mathbb{N}\ |\ 3\leq N \leq 100,000\}
Product: Product of three elements of A,  A[P] * A[Q] * A[R], such that (0\leq\,P < Q < R < N)Notice that saying that (0\leq\,P < Q < R < N), 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.

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).

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 N\geq5. 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.

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

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.

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.

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.

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

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

Max Product of Three Codility Analysis O(N)
Max Product of Three Codility Analysis O(N)

Max Product of Three Codility Analysis O(N*log(N))
Max Product of Three Codility Analysis O(N*log(N))

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

Complete Solution:

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

Link to GitHub solution here .
Link to Codility problem here .

One thought on “Codility - Max Product of Three

/*Comment here*/