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