Maximum Product of Three Numbers: Why Negatives Matter

Given an integer array nums, find three numbers whose product is maximum and return that product.

This is LeetCode 628: Maximum Product of Three Numbers, and it is deceptively simple. Your first instinct might be to just grab the three largest numbers and multiply them together. That works when all the values are positive, but it falls apart the moment negative numbers enter the picture.

Why negatives change everything

The trick is a basic math fact that is easy to overlook: multiplying two negative numbers produces a positive result. If your array contains large negative values like -1000 and -999, their product is 999,000, which is a very large positive number. Multiply that by the largest positive value in the array and you might get a bigger result than multiplying the three largest positives together.

Consider nums = [-4, -3, 1, 2, 5]. The three largest are 1, 2, and 5, giving a product of 10. But (-4) * (-3) * 5 = 60, which is six times bigger. You would miss the answer entirely if you only looked at the top three.

This means you always have to check two candidates:

1. The product of the three largest numbers
2. The product of the two smallest (most negative) numbers and the largest number

The answer is whichever candidate is bigger.

Approach 1: Sort first

The simplest way to find both candidates is to sort the array. After sorting:

• The three largest values are at the end: nums[-1], nums[-2], nums[-3]
• The two most negative values are at the front: nums[0], nums[1]
• The largest value is nums[-1]

So you just compare nums[-1] * nums[-2] * nums[-3] against nums[0] * nums[1] * nums[-1] and return the bigger one.

def maximum_product(nums):
    nums.sort()
    return max(
        nums[-1] * nums[-2] * nums[-3],
        nums[0] * nums[1] * nums[-1]
    )

That is the entire solution. Sort, compare two products, done.

Step-by-step walkthrough

Let's trace through nums = [1, -4, 5, 2, -3] using the sorting approach.

The key takeaway: sorting puts the candidates in predictable positions. You do not need to search for them. They are always at the two ends of the sorted array.

Approach 2: Linear scan (no sorting needed)

Sorting works, but it costs O(n log n). You can do this in a single O(n) pass by tracking five values as you walk through the array:

• The three largest values (max1, max2, max3)
• The two smallest values (min1, min2)

At the end, compare max1 * max2 * max3 against min1 * min2 * max1.

def maximum_product(nums):
    max1 = max2 = max3 = float("-inf")
    min1 = min2 = float("inf")

    for n in nums:
        if n > max1:
            max3 = max2
            max2 = max1
            max1 = n
        elif n > max2:
            max3 = max2
            max2 = n
        elif n > max3:
            max3 = n

        if n < min1:
            min2 = min1
            min1 = n
        elif n < min2:
            min2 = n

    return max(max1 * max2 * max3, min1 * min2 * max1)

This approach maintains the top three largest and bottom two smallest in a single pass. Each element triggers at most a few comparisons and swaps, so the work per element is O(1).

The logic for updating max1, max2, max3 is like an insertion sort into a three-element sorted list. When a new value is larger than the current biggest, everything shifts down. Same idea for the two minimums.

Complexity analysis

*Python's sort() is in-place, so no extra space beyond the sorting itself.

Both approaches use O(1) extra space. The linear scan wins on time complexity, but for most practical input sizes (the problem guarantees n is between 3 and 10^4), the sorting approach is perfectly fast and much easier to write correctly under pressure.

Edge cases to watch for

All negatives like [-5, -4, -3, -2, -1]: The three largest (least negative) are -3, -2, -1, giving a product of -6. The two-smallest-plus-largest candidate is (-5) * (-4) * (-1) = -20. So the answer is -6. The sorting approach handles this correctly because max(nums[-1]*nums[-2]*nums[-3], nums[0]*nums[1]*nums[-1]) = max(-6, -20) = -6.

Mix of positive and negative like [-10, -10, 1, 3, 2]: Candidate 1 gives 3 * 2 * 1 = 6. Candidate 2 gives (-10) * (-10) * 3 = 300. The answer is 300.

Zeros in the array like [0, 0, 1, 2, 3]: Candidate 1 gives 3 * 2 * 1 = 6. Candidate 2 gives 0 * 0 * 3 = 0. The answer is 6. Zeros never help with products, but they do not break anything either.

All zeros or mostly zeros like [0, 0, 0]: Both candidates give 0. Correct.

Exactly three elements like [1, 2, 3]: There is only one possible triplet, so both candidates collapse to the same product. This is the minimum valid input.

The building blocks

This problem is built on two reusable patterns:

1. Sorting for candidate identification

When you need to find extreme values (largest, smallest, or combinations of both), sorting the array puts those values in known positions. You do not need to search for them. This same technique appears in 3Sum, Two Sum II, and many other problems where sorted order makes the solution obvious.

2. Handling negative numbers in products

Whenever multiplication is involved and the input includes negative values, you must consider that two negatives produce a positive. This is the same insight behind Maximum Product Subarray, where you track both the running minimum and maximum product because a negative minimum can become a positive maximum at the next step.

These two building blocks combine here in a very direct way: sort to find the candidates, then compare the products while accounting for the sign flip.

From understanding to recall

Right now the two-candidate approach makes perfect sense. But will you remember it in two weeks? The most common mistake people make on this problem is forgetting to check the two-smallest-times-largest candidate. They grab the three biggest values, get a wrong answer on a test case with negatives, and then scramble.

Spaced repetition locks in the key insight: "products with negatives means I need two candidates." You practice writing the solution from scratch at increasing intervals. After a few reps, the two-candidate check becomes automatic. You do not have to re-derive it every time.

The negative-product pattern and sorting for extreme values are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more efficient than solving random problems and hoping the patterns stick.

Related posts

• Maximum Product Subarray - A harder product problem where negatives flip signs across subarrays. Same core insight about tracking both min and max.
• Product of Array Except Self - Another product-based array problem, solved with prefix and suffix passes.
• Contains Duplicate - A simpler array problem that introduces the seen-set pattern, another fundamental building block worth drilling.