Maximum Product of Three Numbers
Maximum Product of Three Numbers is a easy arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (one pass, top three and bottom two), runs in O(n) time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.
Problem
You are given an integer array nums with at least three elements. Pick three numbers at three different indices so that their product is as large as possible, and return that product.
The array can contain negative numbers and zeros, so the three largest values are not always the right choice.
Examples
Example 1
- Input
nums = [2, 7, 3, 5]- Output
105- Why
- The three largest values give 7 × 5 × 3 = 105.
Example 2
- Input
nums = [-9, -6, 1, 2, 4]- Output
216- Why
- Two negatives make a positive: (-9) × (-6) × 4 = 216 beats 4 × 2 × 1 = 8.
Example 3
- Input
nums = [-5, -4, -3, -2]- Output
-24- Why
- Every product is negative; the one closest to zero is (-4) × (-3) × (-2) = -24.
Constraints
3 <= nums.length <= 10^4-1000 <= nums[i] <= 1000
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n³) | O(1) |
| Better (sort) | O(n log n) | O(log n) |
| Optimal (one pass, top three and bottom two) | O(n) | O(1) |
1Brute force
O(n³)There are n(n - 1)(n - 2) / 6 triples.O(1)Only loop indices and the running best.Try every triple of distinct indices and keep the largest product.
- Loop i < j < k over all indices.
- Compute nums[i] * nums[j] * nums[k] and keep the maximum.
class Solution {
public int maximumProduct(int[] nums) {
int n = nums.length;
int best = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
best = Math.max(best, nums[i] * nums[j] * nums[k]);
}
}
}
return best;
}
}class Solution:
def maximumProduct(self, nums: List[int]) -> int:
n = len(nums)
best = -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 bestclass Solution {
public:
int maximumProduct(vector<int>& nums) {
int n = nums.size();
int best = INT_MIN;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
best = max(best, nums[i] * nums[j] * nums[k]);
}
}
}
return best;
}
};function maximumProduct(nums) {
const n = nums.length;
let best = -Infinity;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
best = Math.max(best, nums[i] * nums[j] * nums[k]);
}
}
}
return best;
}2Better (sort)
O(n log n)The sort dominates; the rest is O(1).O(log n)Stack space used by the sort.After sorting, the answer is one of two products: the last three values, or the first two (the most negative) times the last one. Any other triple is beaten by one of these.
- Sort nums ascending.
- a = nums[n-1] * nums[n-2] * nums[n-3].
- b = nums[0] * nums[1] * nums[n-1].
- Return max(a, b).
class Solution {
public int maximumProduct(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int a = nums[n - 1] * nums[n - 2] * nums[n - 3];
int b = nums[0] * nums[1] * nums[n - 1];
return Math.max(a, b);
}
}class Solution:
def maximumProduct(self, nums: List[int]) -> int:
nums.sort()
a = nums[-1] * nums[-2] * nums[-3]
b = nums[0] * nums[1] * nums[-1]
return max(a, b)class Solution {
public:
int maximumProduct(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
int a = nums[n - 1] * nums[n - 2] * nums[n - 3];
int b = nums[0] * nums[1] * nums[n - 1];
return max(a, b);
}
};function maximumProduct(nums) {
nums.sort((x, y) => x - y);
const n = nums.length;
const a = nums[n - 1] * nums[n - 2] * nums[n - 3];
const b = nums[0] * nums[1] * nums[n - 1];
return Math.max(a, b);
}3Optimal (one pass, top three and bottom two)
O(n)One pass with a constant number of comparisons per element.O(1)Five tracked values.The sorted solution only reads five values: the three largest and the two smallest. Track exactly those in a single scan, shifting them down like a tiny leaderboard.
- Keep max1 >= max2 >= max3 and min1 <= min2.
- For each x: if x > max1 shift max1 → max2 → max3 and set max1 = x; else if x > max2 shift max2 → max3; else if x > max3 set max3.
- Likewise: if x < min1 shift min1 → min2 and set min1 = x; else if x < min2 set min2.
- Return max(max1 * max2 * max3, min1 * min2 * max1).
class Solution {
public int maximumProduct(int[] nums) {
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
for (int x : nums) {
if (x > max1) {
max3 = max2;
max2 = max1;
max1 = x;
} else if (x > max2) {
max3 = max2;
max2 = x;
} else if (x > max3) {
max3 = x;
}
if (x < min1) {
min2 = min1;
min1 = x;
} else if (x < min2) {
min2 = x;
}
}
return Math.max(max1 * max2 * max3, min1 * min2 * max1);
}
}class Solution:
def maximumProduct(self, nums: List[int]) -> int:
max1 = max2 = max3 = -inf
min1 = min2 = inf
for x in nums:
if x > max1:
max3, max2, max1 = max2, max1, x
elif x > max2:
max3, max2 = max2, x
elif x > max3:
max3 = x
if x < min1:
min2, min1 = min1, x
elif x < min2:
min2 = x
return max(max1 * max2 * max3, min1 * min2 * max1)class Solution {
public:
int maximumProduct(vector<int>& nums) {
int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
int min1 = INT_MAX, min2 = INT_MAX;
for (int x : nums) {
if (x > max1) {
max3 = max2;
max2 = max1;
max1 = x;
} else if (x > max2) {
max3 = max2;
max2 = x;
} else if (x > max3) {
max3 = x;
}
if (x < min1) {
min2 = min1;
min1 = x;
} else if (x < min2) {
min2 = x;
}
}
return max(max1 * max2 * max3, min1 * min2 * max1);
}
};function maximumProduct(nums) {
let max1 = -Infinity, max2 = -Infinity, max3 = -Infinity;
let min1 = Infinity, min2 = Infinity;
for (const x of nums) {
if (x > max1) {
max3 = max2;
max2 = max1;
max1 = x;
} else if (x > max2) {
max3 = max2;
max2 = x;
} else if (x > max3) {
max3 = x;
}
if (x < min1) {
min2 = min1;
min1 = x;
} else if (x < min2) {
min2 = x;
}
}
return Math.max(max1 * max2 * max3, min1 * min2 * max1);
}Edge cases to test
- Exactly three numbers: the only product is the answer
- Two large negatives and one large positive beat the three largest values
- All numbers negative: the three largest (closest to zero) win
- Zeros in the array, where 0 can be the best available product
Hints
Hint 1
If you sort the array, the best three numbers must sit at the ends.
Hint 2
There are only two real candidates: the three largest values, or the two smallest (most negative) values times the largest.
Hint 3
You don't need a full sort: track the top three and the bottom two in one pass.
FAQ
What is the best time complexity for Maximum Product of Three Numbers?
Optimal (one pass, top three and bottom two) runs in O(n) time and O(1) extra space. One pass with a constant number of comparisons per element.
Which pattern does Maximum Product of Three Numbers use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Maximum Product of Three Numbers?
Yes. Brute force takes O(n³) time and O(1) space. Try every triple of distinct indices and keep the largest product.
Which edge cases should I test for Maximum Product of Three Numbers?
Exactly three numbers: the only product is the answer; Two large negatives and one large positive beat the three largest values; All numbers negative: the three largest (closest to zero) win; Zeros in the array, where 0 can be the best available product.