Maximum Product of Three Numbers Solution

Problem

Given an integer array, find the largest possible product formed by multiplying exactly three of its elements. Negative numbers are the complication — two deeply negative values multiply to a large positive, which can beat any combination of positives.

Input: nums = [-4, -3, 5, 2, 1]
Output: 60
Explanation: (-4) × (-3) × 5 = 60, which beats the product of any three non-negative numbers in the array.

Counter-example showing why "just take the top three" fails:

Input: nums = [-10, -9, 1]
Output: 90
Explanation: The three largest are -9, 1, and... wait, there are only three elements. But with [-10, -9, 1, 2], the top three (1 × 2 × (-9) = -18) lose to the pair-of-negatives candidate: (-10) × (-9) × 2 = 180.

Intuition

There are only two candidates worth comparing: the product of the three largest values, and the product of the two smallest (most negative) values paired with the single largest value. Any other triple either uses only one negative (sign goes negative) or none of the extremes and can't win. Recognize these two candidates and the problem collapses to a single max call.

Approach 1 — Sort

Sort the array, then read off the two candidate products from the ends.

Sort nums in ascending order.
Compute top_three as the product of the last three elements (nums[-1] * nums[-2] * nums[-3]).
Compute neg_pair_and_max as the product of the first two elements and the last element (nums[0] * nums[1] * nums[-1]).
Return the larger of the two candidates.

1def maximumProduct(self, nums: List[int]) -> int:
2    nums.sort()
3    n = len(nums)
4    # two candidates: three largest, or two most-negative × the global maximum
5    return max(
6        nums[n-1] * nums[n-2] * nums[n-3],
7        nums[0] * nums[1] * nums[n-1]
8    )

Time: O(n log n) — dominated by sorting.
Space: O(1) — sorting is in-place (O(log n) call stack internally in most implementations).

Approach 2 — Linear Scan

Track the five values we care about — the two smallest and three largest — in a single pass, avoiding the sort entirely.

Initialize min1 = min2 = +∞ and max1 = max2 = max3 = -∞.
For each number, check if it displaces min1; if so, push the old min1 into min2. Otherwise check if it beats min2 alone.
Apply the same cascading logic downward through max1 → max2 → max3.
Return the larger of max1 × max2 × max3 and min1 × min2 × max1.

1def maximumProduct(self, nums: List[int]) -> int:
2    min1 = min2 = float('inf')
3    max1 = max2 = max3 = float('-inf')
4    for num in nums:
5        # shift old min1 into the min2 slot before overwriting min1
6        if num <= min1:
7            min2, min1 = min1, num
8        elif num < min2:
9            min2 = num
10        # cascade the new champion down through the top-three slots
11        if num >= max1:
12            max3, max2, max1 = max2, max1, num
13        elif num >= max2:
14            max3, max2 = max2, num
15        elif num > max3:
16            max3 = num
17    return max(max1 * max2 * max3, min1 * min2 * max1)

Time: O(n) — single pass through the array.
Space: O(1) — five scalar variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Sort	O(n log n)	O(1)	Default choice — clearest to read and reason about
Linear Scan	O(n)	O(1)	When strict O(n) is required, or as a follow-up optimization in an interview

Common Mistakes

Only checking the three largest: Returning nums[-1] * nums[-2] * nums[-3] (after sorting) misses the case where two deeply negative numbers pair with the maximum to form a larger product. Always evaluate both candidates.
Wrong cascade order in the linear scan: Writing max1 = num; max2 = max1 clobbers max1 before it can be copied into max2. The displacement must go in reverse order — max3 = max2; max2 = max1; max1 = num — so each slot is saved before it gets overwritten.
Pairing the two smallest with the second-largest: Some implementations try nums[0] * nums[1] * nums[-2] as a third candidate, but the optimal negative pair always wants the single global maximum (nums[-1]), not the second largest — the global max only amplifies the pair's product further.
Off-by-one when porting Python's negative indexing to Java/C++: nums[-1] in Python equals nums[n-1] in Java/C++. Mixing conventions (e.g., writing nums[n] by accident) causes an out-of-bounds exception rather than a wrong answer, so it surfaces immediately — but it's a common slip during contests.
Assuming the answer is always positive: With input [-3, -2, -1], the maximum product is (-3) × (-2) × (-1) = -6 — the least negative option. Code that guards return 0 if result < 0 will silently return the wrong answer for all-negative arrays.

Maximum Product of Three Numbers — Solution