Maximum Product of Three Numbers [D.E. Shaw Python Interview Question]

Given a list of integers, return the maximum product of any three numbers in the array.

For example, for A = [1, 3, 4, 5], you should return 60, since $3 * 4 * 5 = 60$.

For B = [−4, −2, 3, 5] you should return 40 since $-4 * -2 * 5 = 40$

p.s. this is the same as question 9.2 in Ace the Data Science Interview.

Brute-Force Solution: Computing All Triplets

In coding interviews, we want to first aim for correctness – then worry about efficiency. As such, we can start by coding up the brute-force solution which looks at all triplets in the list, and computes the product of every triplet.

If we find a triplet product that's larger than what we've seen previously, we update our variable. At the end, we return the variable.

Here's that brute-force solution:

More-Elegant Solution: Sorting Input

If all of the numbers were positive, then the maximum product of three numbers is a matter of finding the largest three numbers in the array and multiplying them. Be sure to clarify with the interviewer what’s in the integer array — don’t just assume they are all positive integers!

However, with negative integers, the largest product could arise if we take the two smallest numbers (both could be negative) and multiply that result by the largest positive number. We’d need to compare this potential product to the number involving just the largest three numbers.

By first sorting the array, you can get the largest three numbers and the smallest two numbers, and compare these two products to find the larger of the two.

Alternatively, we can use a heap (finding the largest three numbers using a max-heap, and the smallest two numbers using a min-heap), rather than sorting. An implementation involving heaps is below:

The time complexity is where O(N) is the size of the input array and the space complexity is O(1) for the heap, since the number of elements is fixed.