Short Problem Definition:
Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).
expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(1)
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!
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.