#628

Easy

LeetCode Problem Workspace

Maximum Product of Three Numbers

Find three numbers in an array whose product is the largest using sorting and careful handling of negative values.

Problem Statement

Given an integer array nums, identify three numbers such that their product is maximized and return this maximum product. Consider that negative numbers may increase the maximum product when combined correctly.

For example, if nums = [1,2,3,4], the maximum product is 24. If nums = [-1,-2,-3], the maximum product is -6. Ensure the solution handles arrays with both negative and positive integers efficiently.

Examples

Example 1

Input: nums = [1,2,3]

Output: 6

Example details omitted.

Example 2

Input: nums = [1,2,3,4]

Output: 24

Example details omitted.

Example 3

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

Output: -6

Example details omitted.

Constraints

3 <= nums.length <= 104
-1000 <= nums[i] <= 1000

Solution Approach

Sort the array

Sorting nums in ascending order allows direct access to the largest and smallest numbers, which are the main candidates for producing the maximum product.

Compare key product candidates

Compute the product of the three largest numbers and the product of the two smallest numbers with the largest number. The maximum of these two gives the correct result.

Return the maximum product

After calculating both candidate products, simply return the larger one. This guarantees correctness regardless of negative or positive number distributions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting the array takes O(n log n) time, and computing candidate products is O(1). Space complexity is O(1) if sorting in-place, otherwise O(n).

What Interviewers Usually Probe

Clarifies array length limits and negative number handling.
Asks if the candidate product combinations cover all edge cases.
Checks for efficient handling without unnecessary nested loops.

Common Pitfalls or Variants

Common pitfalls

Ignoring the effect of negative numbers on the maximum product.
Assuming the three largest numbers always produce the maximum.
Not handling small arrays of exactly three elements properly.

Follow-up variants

Find the maximum product of k numbers for k > 3 in an array.
Return the triplet of numbers, not just the product, that produces the maximum.
Compute the maximum product in a stream of numbers without storing all elements.

FAQ

Why do we consider the two smallest numbers for the maximum product?

Two negative numbers multiplied together yield a positive product, which can exceed the product of the three largest positive numbers.

Can the maximum product always be formed by the three largest numbers?

No, if negative numbers are present, combining the two smallest negatives with the largest positive may yield a higher product.

What is the time complexity for this approach?

Sorting the array dominates with O(n log n) time; computing the candidate products is O(1).

What if the array contains exactly three numbers?

Simply return the product of all three numbers, as there are no alternative combinations.

How does this problem relate to the array plus math pattern?

It combines array manipulation (sorting and indexing) with mathematical reasoning about negative and positive products to find the maximum.

terminal

Solution

Solution 1: Sorting + Case Analysis

First, we sort the array $\textit{nums}$, and then discuss two cases:

1

2

3

4

5

6

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        a = nums[-1] * nums[-2] * nums[-3]
        b = nums[-1] * nums[0] * nums[1]
        return max(a, b)

Solution 2: Single Pass

We can avoid sorting the array by maintaining five variables: $\textit{mi1}$ and $\textit{mi2}$ represent the two smallest numbers in the array, while $\textit{mx1}$, $\textit{mx2}$, and $\textit{mx3}$ represent the three largest numbers in the array.

1

2

3

4

5

6

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        a = nums[-1] * nums[-2] * nums[-3]
        b = nums[-1] * nums[0] * nums[1]
        return max(a, b)

Continue Practicing

#710 random pick with blacklist #539 minimum time difference #462 minimum moves to equal array elements ii