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.

53 Replies to “Solution to Max-Product-Of-Three by codility

  1. 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?

  2. Here is my C++ code:

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

  4. 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).
    Part of task description
    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?

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

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

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

          • 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. C# solution

    • 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

      • 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. C++ 100% solution , O(NlogN):

  8. 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?

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

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

      • 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

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

  9. 100% , 100% Answer in java.

  10. 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!

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

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

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

    • 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

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

  15. Java 100/1000:

  16. # 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

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

  17. Result: 100/100/100
    Please check.

  18. pascal solution, with one pass of Array

  19. Here is my solution. Got 100/100 with C#

  20. Hi Sheng,
    I am referring to the solution using sorting.
    Assume that if we have the array – A, such that the maximum element is repeated more than once, then in that case,: A[-1] = A[-2].
    However, the question says : P < Q < R.
    So, we have to find the maximum 3 elements that are not repeating?
    PS: Same is true with the minimum elements if there are negative number. We have to find the Minimum non repeating elements ?


    • The condition “P < Q < R" is intentionally misleading. (?) It does NOT matter at all. The only thing "P < Q < R" says is these three numbers come from three DIFFERENT index. PS: P, Q, and R are index, not the number. Order? Does not matter. For example, the product of triplet (2, 4, 5) = the product of triplet (4, 5, 2) = the product of triplet (5, 4, 2).

  21. 100% Python solution. Hi @Sheng, I tried solving it without using sorting. Just min and max. I believe my complexity is O(N), but Codility shows O(N*logN). Could you please comment regarding time complexity? Thanks.

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!