.png)
Maximum Product of Three Numbers
Problem Statement
You are given an integer array nums.
Find the maximum product of any three numbers.
Key Insight
Because numbers can be negative, the answer is:
max(
largest1 * largest2 * largest3,
smallest1 * smallest2 * largest1
)
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| 1 | Brute Force | O(n³) | O(1) |
| 2 | Sorting | O(n log n) | O(1) |
| 3 | One Pass (Tracking Extremes) | O(n) | O(1) |
Here is your clean and complete version of all three approaches with all 5 implementations + output, properly written.
Approach 1: Brute Force
Idea
Try all possible triplets and compute the product, then take the maximum.
Time Complexity
O(n³)
C
#include
#include
int main(){
int nums[] = {-10,-10,5,2};
int n = 4;
long long ans = LLONG_MIN;
for(int i=0;i ans) ans = p;
}
}
}
printf("%lld", ans);
return 0;
}
C++
#include
#include
#include
using namespace std;
int main(){
vector nums = {-10,-10,5,2};
long long ans = LLONG_MIN;
for(int i=0;iJava
class Brute {
public static void main(String[] args){
int[] nums = {-10,-10,5,2};
long ans = Long.MIN_VALUE;
for(int i=0;iPython
nums = [-10,-10,5,2]
ans = float('-inf')
for i in range(len(nums)):
for j in range(i+1,len(nums)):
for k in range(j+1,len(nums)):
ans = max(ans, nums[i]*nums[j]*nums[k])
print(ans)
JavaScript
let nums = [-10,-10,5,2];
let ans = -Infinity;
for(let i=0;iOutput
500
Approach 2: Sorting
Idea
After sorting, only two cases matter:
- Product of 3 largest numbers
- Product of 2 smallest (negative) and largest
Take maximum of both.
Time Complexity
O(n log n)
C
#include
#include
int cmp(const void* a, const void* b){
return (*(int*)a - *(int*)b);
}
int main(){
int nums[] = {-10,-10,5,2};
int n = 4;
qsort(nums, n, sizeof(int), cmp);
long long a = 1LL * nums[n-1]*nums[n-2]*nums[n-3];
long long b = 1LL * nums[0]*nums[1]*nums[n-1];
printf("%lld", a > b ? a : b);
}
C++
#include
#include
#include
using namespace std;
int main(){
vector nums = {-10,-10,5,2};
sort(nums.begin(), nums.end());
int n = nums.size();
long long a = 1LL*nums[n-1]*nums[n-2]*nums[n-3];
long long b = 1LL*nums[0]*nums[1]*nums[n-1];
cout << max(a,b);
}
Java
import java.util.*;
class SortSol {
public static void main(String[] args){
int[] nums = {-10,-10,5,2};
Arrays.sort(nums);
int n = nums.length;
long a = (long)nums[n-1]*nums[n-2]*nums[n-3];
long b = (long)nums[0]*nums[1]*nums[n-1];
System.out.println(Math.max(a,b));
}
}
Python
nums = [-10,-10,5,2]
nums.sort()
ans = max(nums[-1]*nums[-2]*nums[-3],
nums[0]*nums[1]*nums[-1])
print(ans)
JavaScript
let nums = [-10,-10,5,2];
nums.sort((a,b)=>a-b);
let n = nums.length;
let ans = Math.max(
nums[n-1]*nums[n-2]*nums[n-3],
nums[0]*nums[1]*nums[n-1]
);
console.log(ans);
Output
500
Approach 3: One Pass (Optimal)
Idea
Track:
- 3 largest values
- 2 smallest values
Then compute:
- max1 * max2 * max3
- min1 * min2 * max1
Time Complexity
O(n)
C
#include
#include
int main(){
int nums[] = {-10,-10,5,2};
int n = 4;
int max1=INT_MIN, max2=INT_MIN, max3=INT_MIN;
int min1=INT_MAX, min2=INT_MAX;
for(int i=0;imax1){ max3=max2; max2=max1; max1=x; }
else if(x>max2){ max3=max2; max2=x; }
else if(x>max3){ max3=x; }
if(x b ? a : b);
}
C++
#include
#include
#include
using namespace std;
int main(){
vector nums = {-10,-10,5,2};
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(xJava
class OnePass {
public static void main(String[] args){
int[] nums = {-10,-10,5,2};
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(xPython
nums = [-10,-10,5,2]
max1 = max2 = max3 = float('-inf')
min1 = min2 = float('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
print(max(max1*max2*max3, min1*min2*max1))
JavaScript
let nums = [-10,-10,5,2];
let max1=-Infinity,max2=-Infinity,max3=-Infinity;
let min1=Infinity,min2=Infinity;
for(let 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(xOutput
500
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
