Maximum Product of Three Numbers - Solution & Explanation
Problem Statement
Given an integer array nums, find three numbers whose product is maximum and return the maximum product.
Example 1:
Input: nums = [1,2,3] Output: 6
Example 2:
Input: nums = [1,2,3,4] Output: 24
Example 3:
Input: nums = [-1,-2,-3] Output: -6
Constraints:
3 <= nums.length <= 104-1000 <= nums[i] <= 1000
Approach Overview
Problem Overview: You are given an integer array and must return the maximum product possible using any three numbers. The tricky part is handling negative values. Two large negative numbers multiplied together produce a positive number, which can sometimes beat the product of the three largest values.
Approach 1: Sorting for Maximum Product (O(n log n) time, O(1) space)
Sort the array and evaluate the only two combinations that can produce the maximum result. First, the product of the three largest numbers at the end of the sorted array. Second, the product of the two smallest numbers (which may be large negatives) with the largest number. After sorting, both combinations are available with direct index access, so you simply compute both and return the larger value. The logic relies on properties of signed multiplication and is easy to reason about, which makes it a common baseline solution when working with sorting problems on an array. The tradeoff is the O(n log n) sorting cost.
Approach 2: Single Pass Min/Max Tracking (O(n) time, O(1) space)
This approach avoids sorting by tracking the three largest numbers and the two smallest numbers during a single iteration of the array. Maintain variables for max1, max2, max3 (largest values) and min1, min2 (smallest values). For each element, update these trackers using simple comparisons. After one pass, compute two candidate products: max1 * max2 * max3 and max1 * min1 * min2. The first represents the top three positives, while the second captures the case where two negatives produce a large positive. This method uses constant memory and linear traversal, making it the optimal solution for large inputs and a classic pattern in math-based array optimization problems.
Recommended for interviews: The single-pass approach is what interviewers usually expect because it demonstrates awareness of edge cases with negative numbers while keeping the runtime at O(n). Mentioning the sorting solution first shows clear reasoning and correctness, but implementing the O(n) min/max tracking method shows stronger algorithmic thinking and attention to performance.
Approach 1: Sorting for Maximum Product
This approach involves sorting the array, and then choosing the maximum product by examining either the product of the three largest numbers or the product of the two smallest numbers and the largest number.
We sort the array using the standard library function qsort. After sorting, the maximum product can either be from the three largest numbers or from the product of the two smallest numbers and the largest number. This is due to the potential for large negative numbers producing a positive product.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we use in-place sorting.
Approach 2: Single Pass Approach
This approach involves finding the largest three and smallest two numbers in a single traversal of the array. This avoids sorting and gives a more optimal solution for time complexity.
We maintain variables for the three largest and two smallest numbers as we iterate. This allows us to compute the potential maximum products and choose the maximum one without needing to sort the array.
Complexity
Time Complexity: O(n) as there's only a single pass through the array.
Space Complexity: O(1).
Approach 3: Sorting + Case Analysis
First, we sort the array nums, and then discuss two cases:
- If
numscontains all non-negative or all non-positive numbers, the answer is the product of the last three numbers, i.e.,nums[n-1] times nums[n-2] times nums[n-3]; - If
numscontains both positive and negative numbers, the answer could be the product of the two smallest negative numbers and the largest positive number, i.e.,nums[n-1] times nums[0] times nums[1], or the product of the last three numbers, i.e.,nums[n-1] times nums[n-2] times nums[n-3].
Finally, return the maximum of the two cases.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Single Pass
We can avoid sorting the array by maintaining five variables: mi1 and mi2 represent the two smallest numbers in the array, while mx1, mx2, and mx3 represent the three largest numbers in the array.
Finally, return max(mi1 times mi2 times mx1, mx1 times mx2 times mx3).
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sorting for Maximum Product | Time Complexity: |
| Single Pass Approach | Time Complexity: |
| Sorting + Case Analysis | — |
| Single Pass | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting for Maximum Product | O(n log n) | O(1) | Simple and readable approach when sorting is acceptable |
| Single Pass Min/Max Tracking | O(n) | O(1) | Optimal solution for large arrays or interview scenarios |
Video Solution
628. Maximum Product of Three Numbers | LEETCODE EASY | SORTING | LOGIC • code Explainer • 13,885 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Product of Three Numbers easy or hard?
Maximum Product of Three Numbers Python/Java solution
How to solve Maximum Product of Three Numbers in O(n)?
What is the best approach for Maximum Product of Three Numbers?
Is Maximum Product of Three Numbers asked at Google/Amazon/Meta?
What data structure is used in Maximum Product of Three Numbers?
What is the time complexity of Maximum Product of Three Numbers?
Ready to solve this problem?
Practice Maximum Product of Three Numbers with our built-in code editor and test cases.
Practice on FleetCode