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

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:

6

Example 2:

nums = [1, 2, 3, 4]

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

2 * 3 * 4 = 24

So the answer is:

24

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:

Algorithm: Sorting

Sort the array in ascending order.

After sorting:

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

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.

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: