Codility ‘MaxProductOfThree’ Solution

Short Problem Definition:

Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).

Link

MaxProductOfThree

Complexity:

expected worst-case time complexity is O(N*log(N));

expected worst-case space complexity is O(1)

Execution:

After sorting the largest product can be found as a combination of the last three elements. Additionally, two negative numbers add to a positive, so by multiplying the two largest negatives with the largest positive, we get another candidate. If all numbers are negative, the three largest (closest to 0) still get the largest element!

Solution:
def solution(A):
    if len(A) < 3:
        raise Exception("Invalid input")
        
    A.sort()
    
    return max(A[0] * A[1] * A[-1], A[-1] * A[-2] * A[-3])

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Amit Verma

    I am beginner for codility,Can you please help me ,how you think of these type of solution ,I mean what are pre-requisite required for this type of solution as i am preparing for some recruitment process where major constrain to solve a given problem a required time complexity

    • Hi Amin, it is purely training. Start with the easy ones (HackerRank is easier btw) and progress to harder ones. Try not to look at my solutions but let it sink first.

      As for your recruitment process, read the book Coding Interview. It helped me a lot in setting my expectations. Many people ignore challenges at all and it is fine with many employers… depends on the type of job you want, the position etc… Challenges like Codility/HR are not that often seen. Rather trees/hashes/linked-lists and similar. Try learning those 😉

  • Suresh Felidae Attanayake

    In the original problem at codility, there is a condition (0 ≤ P < Q < R < N). If we sort the array A as you do in the line 5, this condition is violated. So how could the solution be correct ?

  • Александр Ковалев

    can someone tell me why we skipped index 3?