LeetCode 628 - Maximum Product of Three Numbers

LeetCode Problem 628

Difficulty: 🟢 Easy
Topics: Array, Math, Sorting

Solution

Problem Understanding

The problem gives an integer array nums and asks us to select exactly three numbers whose product is as large as possible. We must return that maximum product value.

In simpler terms, among all possible combinations of three elements in the array, we need to determine which combination produces the greatest multiplication result.

The input is an array of integers, and the integers may be positive, negative, or zero. The output is a single integer representing the maximum product obtainable from any three distinct elements.

The constraints are important:

• The array length is at least 3, so there is always a valid answer.
• The array can contain up to 10^4 elements, which is large enough that very slow algorithms become impractical.
• Values range from -1000 to 1000, meaning negative numbers are common and must be handled carefully.

Negative values are the key complication in this problem. A naive intuition might suggest taking the three largest numbers, but that is not always correct. Two very small negative numbers multiplied together become a large positive number. For example:

[-10, -10, 5, 2]

The maximum product is:

(-10) * (-10) * 5 = 500

not:

5 * 2 * (-10) = -100

This means the optimal answer can come from one of two possibilities:

• The three largest numbers
• The two smallest numbers, both negative, combined with the largest positive number

Important edge cases include arrays containing all negative numbers, arrays containing zeros, and arrays where the best product comes from negative pairs instead of the largest positive values. The problem guarantees at least three elements, so we never need to handle invalid input sizes.

Approaches

Brute Force Approach

The brute force solution checks every possible combination of three numbers in the array. For each triplet, we compute the product and track the maximum value seen so far.

This works because it exhaustively evaluates all valid choices, guaranteeing that the largest product will eventually be found.

However, the time complexity is too expensive for larger inputs. If the array has n elements, then there are:

n choose 3 = n * (n - 1) * (n - 2) / 6

possible triplets.

For n = 10^4, this becomes far too large to compute efficiently.

Optimal Approach

The key insight is that only a few numbers actually matter.

To maximize the product of three numbers, there are only two meaningful candidates:

1. The three largest values in the array
2. The two smallest values and the largest value

The reason for the second case is that two negative numbers multiply into a positive number. If the negative values have large magnitudes, their product may exceed the product formed by the third-largest positive number.

For example:

[-100, -99, 1, 2, 3]

The best product is:

(-100) * (-99) * 3 = 29700

instead of:

3 * 2 * 1 = 6

We can solve this efficiently by sorting the array once. After sorting:

• The three largest numbers are at the end
• The two smallest numbers are at the beginning

Then we compute both candidate products and return the larger one.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every possible triplet
Optimal	O(n log n)	O(1) or O(n) depending on sorting implementation	Uses sorting and compares only two candidate products

Algorithm Walkthrough

1. Sort the array in non-decreasing order.

Sorting places the smallest values at the beginning and the largest values at the end. This arrangement makes it easy to identify the only candidate combinations that can produce the maximum product. 2. Compute the product of the three largest numbers.

After sorting, these values are:

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

This represents the straightforward case where large positive numbers produce the best result. 3. Compute the product of the two smallest numbers and the largest number.

After sorting, the two smallest values are:

nums[0], nums[1]

If these numbers are both negative, their product becomes positive. Multiplying that positive value by the largest number may produce the overall maximum product. 4. Compare the two candidate products.

The correct answer must be the larger of these two values. 5. Return the maximum product.

Why it works

The algorithm works because any optimal triplet must fall into one of two categories:

• It uses the three numerically largest values
• It uses two extremely negative values whose positive product outweighs the third-largest positive number

No other combination can produce a larger result. Sorting guarantees we can access these candidates directly, and comparing the two products ensures we select the optimal answer.

Python Solution

from typing import List

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

        product_largest = nums[-1] * nums[-2] * nums[-3]
        product_smallest = nums[0] * nums[1] * nums[-1]

        return max(product_largest, product_smallest)

The implementation begins by sorting the array in ascending order. This is the core operation that enables easy access to both the largest and smallest values.

After sorting, the code computes two candidate products:

• product_largest uses the three largest values in the array
• product_smallest uses the two smallest values and the largest value

Finally, the max() function returns whichever product is larger.

The implementation is concise because the mathematical insight reduces the problem to evaluating only two possibilities.

Go Solution

package main

import "sort"

func maximumProduct(nums []int) int {
	sort.Ints(nums)

	n := len(nums)

	productLargest := nums[n-1] * nums[n-2] * nums[n-3]
	productSmallest := nums[0] * nums[1] * nums[n-1]

	if productLargest > productSmallest {
		return productLargest
	}

	return productSmallest
}

The Go implementation follows the same logic as the Python version. The main difference is that Go requires explicit length handling and uses the sort.Ints() function from the standard library.

Because the input constraints are small enough, integer overflow is not a concern in Go. The largest possible product is:

1000 * 1000 * 1000 = 10^9

which fits safely within Go's standard integer range.

Worked Examples

Example 1

Input: [1,2,3]

After sorting:

[1,2,3]

Variable	Value
product_largest	1 × 2 × 3 = 6
product_smallest	1 × 2 × 3 = 6

Maximum value:

6

Returned answer:

6

Example 2

Input: [1,2,3,4]

After sorting:

[1,2,3,4]

Variable	Value
product_largest	2 × 3 × 4 = 24
product_smallest	1 × 2 × 4 = 8

Maximum value:

24

Returned answer:

24

Example 3

Input: [-1,-2,-3]

After sorting:

[-3,-2,-1]

Variable	Value
product_largest	(-3) × (-2) × (-1) = -6
product_smallest	(-3) × (-2) × (-1) = -6

Maximum value:

-6

Returned answer:

-6

Additional Negative Example

Input: [-10,-10,5,2]

After sorting:

[-10,-10,2,5]

Variable	Value
product_largest	(-10) × 2 × 5 = -100
product_smallest	(-10) × (-10) × 5 = 500

Maximum value:

500

Returned answer:

500

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(n)	Depends on the sorting implementation used internally

The algorithm spends almost all of its time sorting the array. After sorting, computing the two candidate products requires only constant time.

The extra space complexity depends on the underlying sorting algorithm implementation. Conceptually, the algorithm itself only uses a few variables.

Test Cases

from typing import List

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

        product_largest = nums[-1] * nums[-2] * nums[-3]
        product_smallest = nums[0] * nums[1] * nums[-1]

        return max(product_largest, product_smallest)

solution = Solution()

assert solution.maximumProduct([1, 2, 3]) == 6  # Basic smallest valid input
assert solution.maximumProduct([1, 2, 3, 4]) == 24  # Three largest positives
assert solution.maximumProduct([-1, -2, -3]) == -6  # All negatives
assert solution.maximumProduct([-10, -10, 5, 2]) == 500  # Negative pair dominates
assert solution.maximumProduct([0, 0, 0]) == 0  # All zeros
assert solution.maximumProduct([-5, -4, 1, 2, 3]) == 60  # Negative pair with positive
assert solution.maximumProduct([-1000, -999, 1000, 999]) == 999000000  # Large magnitudes
assert solution.maximumProduct([5, 4, 3, 2, 1]) == 60  # Descending positives
assert solution.maximumProduct([-4, -3, -2, -1, 60]) == 720  # Large positive with negatives
assert solution.maximumProduct([1, 1, 1]) == 1  # Repeated values

Test	Why
[1,2,3]	Smallest valid array size
[1,2,3,4]	Standard positive case
[-1,-2,-3]	All negative values
[-10,-10,5,2]	Negative pair creates optimal product
[0,0,0]	Handles zeros correctly
[-5,-4,1,2,3]	Tests mixed positive and negative values
[-1000,-999,1000,999]	Large magnitude values
[5,4,3,2,1]	Descending sorted input
[-4,-3,-2,-1,60]	Large positive combined with negatives
[1,1,1]	Duplicate values

Edge Cases

One important edge case occurs when the array contains large negative values. A naive solution that simply selects the three largest numbers would fail here. For example:

[-10, -10, 5, 2]

The best answer comes from multiplying the two negative numbers together. The implementation handles this correctly by explicitly checking the product formed by the two smallest values and the largest value.

Another important edge case is when all numbers are negative. In this scenario, the result itself may also be negative. For example:

[-1, -2, -3]

Some implementations incorrectly assume the answer must be positive. Our implementation does not make that assumption and simply compares the two mathematically valid candidate products.

Arrays containing zeros are another common source of bugs. Consider:

[-5, -4, 0, 1]

A careless implementation might accidentally prioritize a negative product instead of zero. Since the algorithm directly compares the two candidate products numerically, it naturally handles zeros correctly without requiring special-case logic.

A final edge case involves duplicate values. Arrays like:

[1, 1, 1, 1]

or:

[-2, -2, -2, -2]

must still behave correctly. Because the algorithm relies only on sorted positions and not uniqueness, duplicates are handled naturally and produce the correct maximum product.