Maximum Product of Three Numbers — 🔴 Advanced (3/3) — LeetCode Daily Python Solution (the two-negative trap)

8. Introduction

Some LeetCode problems look trivial until they quietly punish you for trusting your intuition. Maximum Product of Three Numbers (LeetCode 628) is one of them. On the surface it reads like a warm-up: grab the three biggest numbers, multiply them, done. That instinct is exactly what interviewers are waiting for you to say — because it is wrong the moment negative numbers enter the array.

This problem is a favorite in coding interviews precisely because it tests something deeper than array manipulation. It checks whether you can spot a hidden assumption in your own reasoning, articulate an invariant, and defend why your solution is provably correct rather than "correct on the examples I tried." Those are the exact skills that separate a candidate who memorized solutions from a software engineer who understands them.

If you learn this problem properly, you walk away with a reusable mental model — the extremes live at the corners — that reappears in dozens of array problems. Let's build that intuition from the ground up, in Python, the way an experienced engineer actually discovers it.

9. Problem Overview

You are given a list of integers. Your task is to choose exactly three of them whose product is the largest possible, and return that product.

A few things worth pinning down before writing any code — the same questions you should ask an interviewer:

• How many elements do we pick? Exactly three.
• Is the array guaranteed to have at least three elements? Yes, n >= 3.
• What are the value bounds? Elements can be negative, zero, or positive. In the classic constraints, values sit within roughly -1000 to 1000 and n up to 10^4.
• Do we need to worry about overflow? In Python, no — integers grow arbitrarily large. But you should flag it out loud for C++ or Java, where three values near 1000 can approach the 32-bit ceiling. Naming that shows maturity.

The trap is that "largest product" and "three largest numbers" are not the same thing when negatives are involved.

10. Example

Let's make the danger concrete.

Example 1

Input:  [-10, -9, 1, 2, 3]
Output: 270

The three biggest numbers are 1, 2, 3, giving a product of 6. But -10 * -9 * 3 = 270. Two negatives multiply into a large positive, and pairing them with the single largest positive crushes the "top three" answer. 270 wins.

Example 2

Input:  [1, 2, 3, 4]
Output: 24

All positive. Here the naive instinct is correct — 2 * 3 * 4 = 24.

Example 3

Input:  [-5, -4, 1, 2, 3]
Output: 60

Top three gives 6. The two smallest (most negative) times the largest gives -5 * -4 * 3 = 60. 60 wins by a mile.

Three examples, two different winning shapes. That tension is the whole problem.

11. Intuition

Here is how an experienced engineer reasons toward the answer — without writing code first.

Start by asking: what sign must a winning product have? We want the maximum, and as long as the array contains any positive numbers or any pair of negatives, the maximum product is positive. A product of three numbers is positive only when it has an even number of negative factors — meaning zero negatives or exactly two negatives.

That single observation collapses the entire search space:

• Zero negatives → all three factors are positive → we want the three largest numbers.
• Two negatives → we want the two most negative numbers (largest magnitude, so their product is a large positive) multiplied by the single largest positive number.

There is no third configuration. A triple with one negative or three negatives can never beat these two when a better option exists — and the all-negative case is quietly handled by "three largest" anyway (the three largest of all-negatives are the three closest to zero, i.e. the least negative triple).

Now, how do we cheaply grab "the three largest" and "the two smallest"? Sort the array. After sorting, the largest values sit at the right tail and the smallest at the left tail — both addressable by fixed index. The answer is simply:

max( nums[-1] * nums[-2] * nums[-3],   # three largest
     nums[0]  * nums[1]  * nums[-1] )  # two smallest × largest

The invariant, stated cleanly: after sorting, no interior element can beat a tail element in either candidate, because swapping a middle factor toward a tail only increases magnitude while keeping sign fixed. So the search space is exactly two triples, no matter how large n grows.

12. Brute Force Solution

Idea: If we don't trust any cleverness, just try every possible triple and keep the maximum product.

Algorithm:

1. Loop over all combinations of three distinct indices (i, j, k).
2. Compute each product.
3. Track and return the maximum.

from itertools import combinations

def maximum_product_brute(nums):
    return max(a * b * c for a, b, c in combinations(nums, 3))

Advantages:

• Impossible to get wrong — it literally checks everything.
• Great as a reference to verify a faster solution during testing.

Disadvantages:

• Catastrophically slow. For n = 10^4, the number of triples is on the order of 10^12 — it will never finish in an interview.

Complexity:

• Time: O(n^3) — three nested choices over n elements.
• Space: O(1) (the generator streams; no extra storage).

13. Optimal Solution

We proved only two candidates matter, so we never need O(n^3). The clean, interview-ready approach is sort, then compare two products.

Step by step:

1. Sort the array ascending. This exposes both tails: smallest values on the left, largest on the right.
2. Candidate A — the three largest: nums[-1] * nums[-2] * nums[-3].
3. Candidate B — the two smallest (most negative) times the largest: nums[0] * nums[1] * nums[-1].
4. Return the larger of the two.

Here's a table showing why both candidates are necessary, across sign patterns:

Input	3 Largest (A)	2 Smallest × Largest (B)	Winner
[1, 2, 3, 4]	24	1*2*4 = 8	A
[-10, -9, 1, 2, 3]	6	-10*-9*3 = 270	B
[-5, -4, 1, 2, 3]	6	-5*-4*3 = 60	B
[-4, -3, -2, -1]	-6	-4*-3*-1 = -12	A

Notice the last row: with all negatives, Candidate A correctly returns the least-negative triple (-1 * -2 * -3 = -6), and it beats B. This is why keeping both corner checks makes the solution robust across every sign combination.

The sort is only there to make the two tails cheap to read. If an interviewer forbids sorting, we replace it with a single linear scan tracking five running extremes — same two candidates, O(n) time.

14. Python Code

The clean, sort-based solution (recommended for a graded submission):

from typing import List


def maximum_product(nums: List[int]) -> int:
    """Return the largest product of any three numbers in nums."""
    nums.sort()  # ascending: smallest on the left, largest on the right

    # Candidate A: the three largest numbers.
    top_three = nums[-1] * nums[-2] * nums[-3]

    # Candidate B: the two most negative numbers times the largest.
    two_neg_one_pos = nums[0] * nums[1] * nums[-1]

    return max(top_three, two_neg_one_pos)

The O(n) one-pass (the expected follow-up):

from typing import List


def maximum_product_one_pass(nums: List[int]) -> int:
    """O(n) time, O(1) space — no sorting, streams in a single pass."""
    max1 = max2 = max3 = float("-inf")  # three largest
    min1 = min2 = float("inf")          # two smallest

    for x in nums:
        # Update the three largest.
        if x >= max1:
            max1, max2, max3 = x, max1, max2
        elif x >= max2:
            max2, max3 = x, max2
        elif x >= max3:
            max3 = x

        # Update the two smallest.
        if x <= min1:
            min1, min2 = x, min1
        elif x <= min2:
            min2 = x

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

15. Code Walkthrough

Sort-based version:

• nums.sort() mutates the list in place into ascending order. After this, nums[0] and nums[1] are the two smallest, and nums[-1], nums[-2], nums[-3] are the three largest. Everything downstream depends on this ordering.
• top_three is Candidate A — the all-positive (or least-negative) case.
• two_neg_one_pos is Candidate B — the two-negative trap answer.
• max(...) picks the winner. Two multiplications, one comparison, branch-free.

Note on space: sort() mutates the caller's input. If that's unacceptable, use nums = sorted(nums) to work on a copy — at the cost of O(n) extra space.

One-pass version:

• We seed max1/max2/max3 to negative infinity and min1/min2 to positive infinity. This seeding is the single most important line. If you seed the mins to 0 instead of +inf, an all-negative input silently corrupts the minimums and produces a wrong answer.
• The max cascade shifts values down like a tiny podium: a new champion pushes the old first place into second, and so on.
• The min cascade tracks the two most negative values the same way.
• Finally we compare the same two candidates as before: three largest vs. two smallest times the largest.

16. Dry Run

Let's trace the sort-based solution on [-10, -9, 1, 2, 3].

Step 1 — Sort: already ascending → [-10, -9, 1, 2, 3].

Step 2 — Candidate A (three largest):

nums[-1] * nums[-2] * nums[-3] = 3 * 2 * 1 = 6

Step 3 — Candidate B (two smallest × largest):

nums[0] * nums[1] * nums[-1] = (-10) * (-9) * 3 = 90 * 3 = 270

Step 4 — Compare:

max(6, 270) = 270

Output: 270. The two negatives -10 and -9 combined into +90, and pairing that with the largest positive 3 produced the winning product. This is exactly the two-negative trap that defeats the naive "top three" one-liner.

17. Complexity Analysis

Sort-based solution:

• Time: O(n log n) — dominated by the sort. The two product computations and the comparison are O(1).
• Space: O(1) if you use in-place sort() (technically O(log n) for Timsort's internal stack), or O(n) if you use sorted() to avoid mutating the input.

One-pass solution:

• Time: O(n) — a single sweep, constant work per element.
• Space: O(1) — just five running variables, regardless of input size.

At n = 10^4, both run in microseconds; the difference between n log n and n is academic here. The one-pass earns its keep only when the input is a stream you can't fully hold in memory, or n is enormous and you're memory-bound.

18. Alternative Solutions

The main alternative is the one-pass with running extremes, already shown above. It trades the elegant readability of sorting for O(n) time and streaming capability.

A quick comparison:

Approach	Time	Space	Best for
Brute force	O(n^3)	O(1)	Verifying correctness only
Sort + two candidates	O(n log n)	O(1)–O(n)	Interview submissions, readability
One-pass extremes	O(n)	O(1)	Streams, huge n, follow-up questions

For a graded submission, sort and move on. Cite the one-pass only when explicitly asked to optimize — reaching for it unprompted signals premature optimization.

19. Edge Cases

• Exactly three elements: [a, b, c] must return a * b * c regardless of sign. Verify your indices don't secretly assume n > 3.
• All negatives: [-4, -3, -2, -1] → the answer is the least-negative triple -6. Candidate A handles this; the two-corner check keeps you safe.
• Contains zeros: [-2, 0, 3, 4] → zeros need no special case. They simply lose to any positive product (or correctly produce 0 when that's genuinely the max).
• Two large negatives + small positives: the canonical [-10, -9, 1, 2, 3] trap.
• Duplicates: [3, 3, 3] → 27. Repeated values are fine; nothing assumes distinctness.
• Min/max value bounds: at the extremes of the value range, flag overflow risk for C++/Java (a non-issue in Python).

20. Common Mistakes

1. Returning the product of the three largest only. The classic failure — it ignores the two-negative trap entirely.
2. Seeding running mins to 0 in the one-pass. All-negative inputs then silently corrupt the extremes. Seed mins to +inf, maxes to -inf.
3. Adding a phantom third candidate like "two negatives times the second largest." A second-largest positive never beats the largest, so this branch is dead weight.
4. Assuming n > 3 and indexing out of bounds on a three-element array.
5. Using abs() to find "the biggest magnitude" and losing sign information. Sign is the entire crux of this problem — never discard it.
6. Forgetting that mutating the input with sort() may surprise the caller when they expected their list untouched.

21. Interview Questions

• Why are there exactly two candidate configurations, and why is a third impossible?
• Prove that a winning triple must have an even number of negative factors.
• Can you solve it without sorting? Walk me through the O(n) one-pass.
• What breaks if you seed the running minimums incorrectly?
• How would you generalize this to the maximum product of k elements?
• Does the sort mutate the input? How would you avoid that?
• In C++/Java, when could this overflow, and how would you guard against it?

22. Similar Problems

• LeetCode 152 — Maximum Product Subarray: Extends the sign-flipping idea to contiguous subarrays; you track running max and min because a negative can flip a minimum into the new maximum. Same "signs matter" reasoning, harder because the window is dynamic.
• LeetCode 628 — Maximum Product of Three Numbers: This problem itself.
• LeetCode 414 — Third Maximum Number: Reinforces tracking multiple running extremes in a single pass.
• LeetCode 53 — Maximum Subarray: The additive cousin — Kadane's algorithm — teaching the same "one linear pass with running state" muscle.
• LeetCode 1509 — Minimum Difference by Three Moves: Another "the answer lives at the sorted tails" problem where corners dominate.

23. Key Takeaways

• The maximum product of three numbers is always one of two candidates: the three largest, or the two smallest (most negative) times the largest.
• The reason is a sign argument: a maximum positive product needs an even number of negative factors.
• Sort + two products is the clean O(n log n) interview answer; the one-pass with five running extremes is the O(n) follow-up.
• The transferable insight — the extremes live at the corners — reappears across array problems. Internalize the invariant, not the code.

24. Watch the Video

Want to see the full trace, predict which branch wins before it's revealed, and check your answer against 270? Watch the complete walkthrough here: {LINK}. The video runs both quiz rounds and traces the two-candidate logic step by step — pause and call the branch before each reveal to test whether you've truly internalized the invariant.

25. About the Series

This breakdown is part of Fun with Learning Technology — a series that turns one coding problem at a time into deep, intuition-first understanding. Instead of memorizing solutions, you learn why each approach works, how an engineer discovers it, and how to defend it under interview pressure. Every episode covers a LeetCode problem end to end: intuition, brute force, optimal solution, dry runs, edge cases, and follow-ups.

26. Call To Action

If this made the two-negative trap click, here's how to help the series grow and keep leveling up:

• 👍 Like the video on YouTube — it genuinely helps more developers find it.
• 🔔 Subscribe so you never miss a daily problem breakdown.
• 📬 Subscribe on Substack for the written deep-dives delivered to your inbox.
• 💬 Comment with which branch you predicted — did you catch the trap?
• 🔁 Share it with a friend who's grinding LeetCode.

---

    top3 = nums[-1] * nums[-2] * nums[-3]
    low2 = nums[0] * nums[1] * nums[-1]
    return max(top3, low2)