Maximum Product of Three Numbers — Problem & Solution
Maximum Product of Three Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Product of Three Numbers is an easy coding problem on arrays, math and sorting, asked in Amazon, Meta, Bloomberg and Intuit interviews.
- Difficulty: Easy
- Topics: Arrays, Math, Sorting
- Asked at: Amazon, Meta, Bloomberg, Intuit
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, find three numbers whose product is maximum and return that product.
Example 1
Input: nums = [1,2,3]
Output: 6
Example 2
Input: nums = [1,2,3,4]
Output: 24
Example 3
Input: nums = [-100,-98,-1,2,3,4]
Output: 39200
Explanation: Two large negatives multiply to a large positive.
Constraints
3 <= nums.length <= 40-1000 <= nums[i] <= 1000The answer fits in a signed 32-bit integer.
Hints for Maximum Product of Three Numbers
Hint 1
Sorting makes both candidates obvious.
Hint 2
Either the three largest values win, or the two most negative values pair with the single largest.
Hint 3
Take the maximum of those two products — nothing else can beat them.
How to solve Maximum Product of Three Numbers
Either the three largest values or the two most negative with the largest; take the bigger product.
Approach
- Sort.
- Return
max(a[-1]·a[-2]·a[-3], a[0]·a[1]·a[-1]).
Why it works
A maximum product uses either zero or two negatives; with zero negatives the three largest win, with two negatives the most negative pair times the largest positive wins. No other combination can exceed both.
Complexity
- Time —
O(n log n) - Space —
O(1) beyond the sort
Pitfalls
- Tracking the top three and bottom two in one pass makes it O(n).
Reference solution
Python
def maximumProduct(nums) -> int:
a = sorted(nums)
return max(a[-1] * a[-2] * a[-3], a[0] * a[1] * a[-1])Java
public static int maximumProduct(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length;
return Math.max(a[n - 1] * a[n - 2] * a[n - 3], a[0] * a[1] * a[n - 1]);
}C++
int maximumProduct(vector<int>& nums) {
vector<int> a = nums;
sort(a.begin(), a.end());
int n = (int) a.size();
return max(a[n - 1] * a[n - 2] * a[n - 3], a[0] * a[1] * a[n - 1]);
}JavaScript
var maximumProduct = function(nums) {
const a = nums.slice().sort(function(x, y) { return x - y; });
const n = a.length;
const highThree = a[n - 1] * a[n - 2] * a[n - 3];
const twoLow = a[0] * a[1] * a[n - 1];
return Math.max(highThree, twoLow);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms