# Solution to Max-Product-Of-Three by codility

21 Jan

Question Name: MaxProductOfThree

An small trap: multiplying two negatives makes a positive number.

UPDATE on 03-02-2015: Thanks to @Julian, there is an O(N) solution. We sort the input in the original solution, because we want the two minimum and three maximum elements. However, with bookkeeping, sorting is not necessary.

The second solution is provided by @Julian.

### 46 Replies to “Solution to Max-Product-Of-Three by codility”

• Sheng says:

Yes, it is working perfect! Thanks for sharing your new solution!

• Paul says:

Thanks for sharing this cool solution! Looks like codility mistakenly evaluate it as O(nlogn) rather than O(n)

• Sheng says:

Yes, you are right. Probably they did not notice the O(N) solution, which is not so general ðŸ™‚

• Christopher Yeleighton says:

It seems that it is impossible to distinguish between O (N) and O (N log N) in practice unless you impose a very drastic constant, but then the requirement is actually much stricter.

• Christopher Yeleighton says:

You could use a heap instead of sorting to get 3 max, and an inverse heap of the rest to get 2 min.

• Sheng says:

Good idea! Thanks!

1. Nakul says:

How do you think of the perfect solutions? I can’t get the best performance even though I can get 100% accurate solutions. Any tips?

• Sheng says:

Please refer to my blog post.

2. Chen says:

Here is my C++ code:

• Sheng says:

3. Eli says:

The line “A[P] * A[Q] * A[R] (0 less P less Q less R less N)” was really confusing since one can assume that R should be less then N, since they are saying about PRQ triplet, and not (A[P]*A[Q]*A[R]) triplet at first.

Here is my O(N) CPP solution, which somehow similar to a java code, but anyways, you don’t need to sort an array to find 5 elements.

• Sheng says:

Yes, sorting is not necessary, but makes the solution shorter.

4. Stefan says:

Related to task description, I would expect that both solutions returns wrong values, or what do I miss here (because with sorting, I ignore the position in the original array completely, with second solution, the min-values might occur after the retrieved max value).

A non-empty zero-indexed array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 â‰¤ P < Q < R < N).

However, codility says to both solutions 100%. Do they ignore their own posted condition here?

• Sheng says:

It is a bit tricky. Actually sorting is fine, because the order does not matter. Given any three valid and non-duplicate indexes (0<= P, Q, R < N and P != Q, Q != R, R != P), we can get one and only one arrangement, whose items are an increasing array.The only meaning of 0 â‰¤ P < Q < R < N is: P, Q and R are valid index; and P, Q and R are not duplicate.

• Stefan says:

Dear Sheng,

thanks for feedback. My understanding of P < Q < R is a bit different (for me it reads that P should be smaller than Q and Q should be smaller than R), which would mean that the values have to appear in this order. Funnily also the samples provided by Codility are manifesting this approach (Triplets (0,1,2), (1,2,4) and (2,4,5) ).

However, that would increase the difficulty level pretty much and wouldnÂ´t fit to the "Painless" level, so probably my understanding is wrong (and maybe I should raise this question to Codility ðŸ™‚ ).

• Sheng says:

It is completely a mathematical language issue. Consider any three elements A, B, and C, there indexes are M, N, L.

One one hand, the product of them is same, no matter what order is taken: A * B * C = C * B * A = A * C * B = ……

On the other hand, because they are not duplicate (their indexes are different). M != N != L. We can make: P = min(M, N, L), Q = middle(M, N, L), R = max(M, N, L).

As a result, ANY three-element-arrangement is a candidate for the answer. The statement “0 â‰¤ P < Q < R < N" means nothing BUT these three elements should be different in index.There are some similar description in other Codility challenges. You need to get through its real definition. Otherwise, some of them are intractable.PS: in other words, in the question's example input, the product of triplet (2, 3, 5) is the same as (2, 5, 3) and (5, 3, 2). In all these three triplets, the P is 2, Q is 3, and R is 5. Actually the content of P, Q, and R does not matter at all. We can try (5, 3, 2) instead of (2, 3, 5), because they have the same product.

• Stefan says:

Thanks again for feedback. I think I got now my misunderstanding. I implicitly interpreted that P, Q and R are linked to the position in the array, but that is not mentioned, it is just defined for the triplet (and there indeed it doesnÂ´t matter).

And good to know that I will face that more often in other Codility challenges :-).

5. MC says:

C# solution

• Jeffrey Coho says:

Technically, this is a fail. Because you are *replacing* the array with a new one – which requires you to use another array and throw away the input memory. An adaptation of your solution would be to use System.Array.Sort(A); which sorts A in place in O(n log n) time, and doesn’t create an extra array, and therefore satisfies the space complexity requirement. But otherwise, your solution is bang on. There are faster ways (the O(N) solution), but yours passes the test so who cares. It’s way more readable.

UPDATE #1: ignore my last. linq is smart enough to apply the sort in place, and ignore the ToArray() (simply casting the sorted source elements). So it doesn’t violate the spatial complexity

UPDATE #2: Ignore my last again! Linq is NOT applying the sort in place. it is in fact creating a new array. So this is technically a fail. You DO need to use something line Array.Sort(A) which is an in place sort

• Sheng says:

Yes, there is some space to improve the space complexity.

FYI, O(NlogN) and O(N) is definitely different. The problem for the OJ platform is that, they are so close that OJ platform cannot distinguish them with small testing cases.

6. Adding my verbose solution 100%:
I also was going to use bookkeeping but the requirements in terms of space says O(1) and I got a little bit confused, thinking that every array will be O(n) in space, but it’s cool how arrays with O(1) space can be used, thanks @Julian.

7. df611 says:

C++ 100% solution , O(NlogN):

8. JG says:

I submitted my code which is basically merge sort and return like your Python code in two lines at the start of this page but it says performance is 80% only (Accuracy: 100%), can you comment on why that could be the case?

• Sheng says:

At least, your solution does not meet the space requirements: expected worst-case space complexity is O(1). The merge sorting needs O(N) space.

9. Alex Kovalev says:

can someone tell me why we skipped index 3 ?

• Sheng says:

Because index 3 is never in the result three-element. There are three cases for the input numbers:
1. All positive; 2. all negative; 3. includes positive and negative. Think about the problem in each case and combine the result. Your will find out why.

• christian says:

that doesnt explain why we skipped index 3. This makes no sense. There is no explanation of why they chose (0, 1, 2), (1, 2, 4) and (2, 4, 5) in the example. Whats wrong with (0,1,3) for example

• Sheng says:

There is a mathematic proof. But I am too lazy to write it down:-) If you followed my suggestion (considering three cases), I would expect you got the right solution.

A quick correction: I am not skipping the 3rd items. After sorting, I skip all the items from the 3rd position to the 4th last position. For example, with sorted content [x0, x1, x2, x3, x4, x5, x6, x7], I ignored x2, x3, and x4.

10. Dimuthu says:

100% , 100% Answer in java.

11. Nice says:

Nice solution!
I achieved 100% by myself, but I wasn’t satisfied. I noticed that sorting (which gives the nlogn complexity) is not even necessary, you just have to find the mins and maxes. So I looked it up with Google and this came up.
Btw, I searched for the 3 smallest and 3 biggest numbers and just combined them in a nested loop. Brute force yay! Turns out there is a more elegant way, thanks!

• Sheng says:

Thanks for your visiting! Enjoy coding!

12. Tiago Pereira says:

Java solution, 100%. I don’t know if I am missing something.

• Sheng says:

You should have already covered all cases ðŸ™‚

13. Damian says:

Hi, i make some solution in Python but thinks that is more exact than main solution, if not, u can answer me why:

• Sheng says:

It’s too slow to pass the testing.

14. the initial sorted solution:
return max(A[0]*A[1]*A[-1], A[-1]*A[-2]*A[-3])

doesn’t pass the test: [-50, -45, -5, 4]; the max should be -50*-45*4 = 9000 but returns 900 (-45*-5*-4), so, if there are more than two negatives, and a single positive, you need to remove the third negative.

• Sheng says:

I did not see how could you get 900 with the my solution:
Your test case: [-50, -45, -5, 4]
Returned value: 9000

Apparently the solution will return 9000, because:
max(A[0]*A[1]*A[-1], A[-1]*A[-2]*A[-3])
= max(-50*-45*4 , -45*-5*-4)
= max(9000, 900)
= 9000

15. Patrick says:

You adopted the bookkeeping solution from Julian. I didn’t get it at first, so I decided to do it in Python to figure it out. Here’s what I got. It’s tested and got 100%. I guess the space for the 2 and 3 length lists that hold the highest and lowest values still count at O(1).

• Andre Leitao says:

This code raises an error.
This line dont look right:
elif a max[0]*min[0]*min[1]:

• Sheng says:

oops~ Patrick forgot to include the code into the “pre” section. The code is partially missing.

PS: I complete the code. It should work well now.

16. EndreBorcsok says:

Java 100/1000:

17. Tao Li says:

# Following is my code, always keeping the maximum three and minimum two numbers.
# Why it gives some wrong answers? for large_random, it gives 999,000,000 while the
# expectation is 1,000,000,000

• Sheng says:

Your logic to compute the L is wrong. It should be:

18. Result: 100/100/100
https://app.codility.com/demo/results/training9EME9B-ZN7/