LeetCode 628: Maximum Product of Three Numbers

Problem Restatement

We are given an integer array nums.

We need to choose three numbers from the array so that their product is as large as possible.

Return that maximum product.

The three numbers do not need to be next to each other. We only care about choosing any three different elements.

Input and Output

Item	Meaning
Input	An integer array `nums`
Output	The maximum product of any three numbers
Constraint	`nums.length >= 3`

Example function shape:

def maximumProduct(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [1, 2, 3]

The only possible product is:

1 * 2 * 3 = 6

So the answer is:

Example 2:

nums = [1, 2, 3, 4]

The best three numbers are 2, 3, and 4.

2 * 3 * 4 = 24

So the answer is:

Example 3:

nums = [-1, -2, -3]

There are exactly three numbers, so we must use all of them.

-1 * -2 * -3 = -6

So the answer is:

-6

First Thought: Try Every Triple

The direct solution is to check every possible group of three numbers.

For every i, j, and k, where all indices are different, compute:

nums[i] * nums[j] * nums[k]

Then keep the largest product.

Code:

class Solution:
    def maximumProduct(self, nums: list[int]) -> int:
        n = len(nums)
        best = float("-inf")

        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

This is correct, but it checks too many triples.

For n numbers, this takes O(n^3) time.

Key Insight

The maximum product must come from one of two cases.

The first case is simple: use the three largest numbers.

largest * second_largest * third_largest

This works when the best product comes from large positive values.

But negative numbers change the problem.

Two negative numbers multiply into a positive number. So the second possible answer is:

largest * smallest * second_smallest

For example:

nums = [-10, -10, 5, 2]

The three largest numbers are -10, 2, and 5 if sorted carefully by value near the end we get:

-10 * 2 * 5 = -100

But the two smallest numbers are -10 and -10.

-10 * -10 * 5 = 500

So the answer is 500.

That means we only need five important values:

Value	Why
Largest number	Used in both possible best products
Second largest number	Needed for three-largest case
Third largest number	Needed for three-largest case
Smallest number	May be a large negative
Second smallest number	May pair with the smallest negative

Algorithm: Sorting

Sort the array in ascending order.

After sorting:

Expression	Meaning
`nums[-1]`	largest number
`nums[-2]`	second largest number
`nums[-3]`	third largest number
`nums[0]`	smallest number
`nums[1]`	second smallest number

Then compute two candidate products:

candidate1 = nums[-1] * nums[-2] * nums[-3]
candidate2 = nums[-1] * nums[0] * nums[1]

Return the larger one.

Implementation

class Solution:
    def maximumProduct(self, nums: list[int]) -> int:
        nums.sort()

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

Code Explanation

First, we sort the array:

nums.sort()

This puts the smallest values at the front and the largest values at the back.

The product of the three largest values is:

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

The product of the largest value and the two smallest values is:

nums[-1] * nums[0] * nums[1]

This handles arrays with two large negative numbers.

Finally, we return the better of the two products:

return max(...)

Correctness

After sorting, nums[-1], nums[-2], and nums[-3] are the three largest values in the array.

If the maximum product uses three large positive numbers, then it is exactly:

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

If the maximum product uses negative numbers, it must use two negative numbers, because one negative number would make the product negative when multiplied by positive numbers. To make this product as large as possible, we want the two smallest numbers, since they are the most negative and give the largest positive product when multiplied together.

So that candidate is:

nums[-1] * nums[0] * nums[1]

Any maximum product must be one of these two forms. The algorithm computes both and returns the larger value, so it returns the maximum possible product.

Complexity

Metric	Value	Why
Time	`O(n log n)`	Sorting dominates the runtime
Space	`O(1)` or `O(n)`	Depends on the sorting implementation

The main idea is simple and reliable. Sorting gives direct access to the only values that can matter.

Alternative Solution: One Pass

We can solve this without sorting.

Track the three largest numbers and the two smallest numbers while scanning the array once.

class Solution:
    def maximumProduct(self, nums: list[int]) -> int:
        min1 = float("inf")
        min2 = float("inf")

        max1 = float("-inf")
        max2 = float("-inf")
        max3 = float("-inf")

        for num in nums:
            if num <= min1:
                min2 = min1
                min1 = num
            elif num <= min2:
                min2 = num

            if num >= max1:
                max3 = max2
                max2 = max1
                max1 = num
            elif num >= max2:
                max3 = max2
                max2 = num
            elif num >= max3:
                max3 = num

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

This version has better asymptotic time complexity.

Metric	Value	Why
Time	`O(n)`	One scan through the array
Space	`O(1)`	Only five variables are stored

Testing

def run_tests():
    s = Solution()

    assert s.maximumProduct([1, 2, 3]) == 6
    assert s.maximumProduct([1, 2, 3, 4]) == 24
    assert s.maximumProduct([-1, -2, -3]) == -6
    assert s.maximumProduct([-10, -10, 5, 2]) == 500
    assert s.maximumProduct([-100, -2, -3, 1]) == 300
    assert s.maximumProduct([0, 0, 0]) == 0
    assert s.maximumProduct([-5, -4, -3, -2, -1]) == -6

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
`[1, 2, 3]`	Minimum length
`[1, 2, 3, 4]`	Normal positive case
`[-1, -2, -3]`	All negative with exactly three values
`[-10, -10, 5, 2]`	Two negatives create the maximum
`[-100, -2, -3, 1]`	Smallest two values matter
`[0, 0, 0]`	Product can be zero
`[-5, -4, -3, -2, -1]`	All negative values