# Codility ‘MaxProductOfThree’ Solution

##### Short Problem Definition:

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

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 * A * A[-1], A[-1] * A[-2] * A[-3])
```

A better solution has been suggested in the commends by

```def betterSolution(A):
if len(A) < 3:
raise Exception("Invalid input")

minH = []
maxH = []

for val in A:
if len(minH) < 2:
heapq.heappush(minH, -val)
else:
heapq.heappushpop(minH, -val)

if len(maxH) < 3:
heapq.heappush(maxH, val)
else:
heapq.heappushpop(maxH, val)

max_val = heapq.heappop(maxH) * heapq.heappop(maxH)
top_ele = heapq.heappop(maxH)
max_val *= top_ele
min_val = -heapq.heappop(minH) * -heapq.heappop(minH) * top_ele

return max(max_val, min_val)
```

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