Maximum Product of Three Numbers

The most literal reading is to try every unordered triple of indices and track the biggest product. Use nested loops with i < j < k so each combination of three distinct elements is checked exactly once, and keep a running maximum. It always returns the right answer because it exhausts every possible choice of three values — but it recomputes the same work over and over with no structure.

class Solution:
    def maximumProduct(self, nums: list[int]) -> int:
        n = len(nums)
        best = -10**18          # smaller than any possible product here
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    best = max(best, nums[i] * nums[j] * nums[k])
        return best

Why it is cubic: there are about n choose 3 triples, which grows like n³ / 6. For each triple we do a couple of multiplications, so the work is O(n³). On .length = 10^4 that means roughly 1.6 × 10^11 triples — far too many. It is correct but useless at scale, and it ignores the structure that makes the problem easy.

Sort ascending, then the two ends carry everything the answer needs. Candidate A is the product of the three largest values (the last three in the sorted array). Candidate B is the product of the largest value and the two most-negative values (the first two) — because negative × negative is positive, so the two smallest values are secretly the two largest magnitudes, and paired with the largest value they can dwarf candidate A. The answer is simply max(A, B).

class Solution:
    def maximumProduct(self, nums: list[int]) -> int:
        nums.sort()
        n = len(nums)
        # Candidate A: the three largest values.
        largest_three = nums[-1] * nums[-2] * nums[-3]
        # Candidate B: the largest value times the two most negative.
        largest_with_negatives = nums[-1] * nums[0] * nums[1]
        return max(largest_three, largest_with_negatives)

Watch the file example, [-100, -98, -1, 2, 3, 4], where the two most-negative values blow past the three largest — candidate B wins at 39200:

Then the all-negative case, [-1, -2, -3], where only three numbers exist so both candidates converge on the whole array:

Why both candidates are necessary: with all-positive numbers candidate A trivially wins and the problem collapses to the three largest. But with a pair of strong negatives, candidate B wins — as in [-100,-98,-1,2,3,4], where 4 · (-100) · (-98) = 39200 beats 4 · 3 · 2 = 24 by far. A sorted middle value like -1 can never help, because swapping it for its larger right neighbor or its more-negative left neighbor never shrinks the product. So evaluating both candidates and taking the max, the formula stays correct for positive-only, negative-only, and mixed arrays alike.

Why it is optimal for this approach: one sort costs O(n log n) and produces the two ends directly; the two products and the max are O(1), and we reuse the input array so space is O(1) (ignoring the sort’s internal recursion stack). You cannot answer the question without examining every element, and O(n log n) easily clears 10^4.

The O(n) variant: because only the two smallest and three largest values matter, you can skip the sort entirely and track five variables in one pass — mi1, mi2 for the two smallest, mx1, mx2, mx3 for the three largest — then take max(mi1 * mi2 * mx1, mx1 * mx2 * mx3). That is O(n) time and O(1) space, and it is the version you would recite in an interview to drop the log factor.

from math import inf

class Solution:
    def maximumProduct(self, nums: list[int]) -> int:
        mi1 = mi2 = inf
        mx1 = mx2 = mx3 = -inf
        for x in nums:
            if x < mi1:
                mi2, mi1 = mi1, x
            elif x < mi2:
                mi2 = x
            if x > mx1:
                mx3, mx2, mx1 = mx2, mx1, x
            elif x > mx2:
                mx3, mx2 = mx2, x
            elif x > mx3:
                mx3 = x
        return max(mi1 * mi2 * mx1, mx1 * mx2 * mx3)