Description
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
Solutions
Solution 1: Sorting + Case Analysis
First, we sort the array nums, and then discuss two cases:
- If nums contains all non-negative or all non-positive numbers, the answer is the product of the last three numbers, i.e., nums[n-1] × nums[n-2] × nums[n-3];
- If nums contains 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] × nums[0] × nums[1], or the product of the last three numbers, i.e., nums[n-1] × nums[n-2] × nums[n-3].
Finally, return the maximum of the two cases.
The time complexity is O(n × log n), and the space complexity is O(log n). Here, n is the length of the array nums.
PythonJavaC++GoTypeScript
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)(code-box)
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[n - 1] * nums[0] * nums[1];
return Math.max(a, b);
}
}(code-box)
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[n - 1] * nums[0] * nums[1];
return max(a, b);
}
};(code-box)
func maximumProduct(nums []int) int {
sort.Ints(nums)
n := len(nums)
a := nums[n-1] * nums[n-2] * nums[n-3]
b := nums[n-1] * nums[0] * nums[1]
if a > b {
return a
}
return b
}(code-box)
function maximumProduct(nums: number[]): number {
nums.sort((a, b) => a - b);
const n = nums.length;
const a = nums[n - 1] * nums[n - 2] * nums[n - 3];
const b = nums[n - 1] * nums[0] * nums[1];
return Math.max(a, b);
}(code-box)
Solution 2: 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 × mi2 × mx1, mx1 × mx2 × mx3).
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
PythonJavaC++GoTypeScript
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
top3 = nlargest(3, nums)
bottom2 = nlargest(2, nums, key=lambda x: -x)
return max(top3[0] * top3[1] * top3[2], top3[0] * bottom2[0] * bottom2[1])(code-box)
class Solution {
public int maximumProduct(int[] nums) {
final int inf = 1 << 30;
int mi1 = inf, mi2 = inf;
int mx1 = -inf, mx2 = -inf, mx3 = -inf;
for (int x : nums) {
if (x < mi1) {
mi2 = mi1;
mi1 = x;
} else if (x < mi2) {
mi2 = x;
}
if (x > mx1) {
mx3 = mx2;
mx2 = mx1;
mx1 = x;
} else if (x > mx2) {
mx3 = mx2;
mx2 = x;
} else if (x > mx3) {
mx3 = x;
}
}
return Math.max(mi1 * mi2 * mx1, mx1 * mx2 * mx3);
}
}(code-box)
class Solution {
public:
int maximumProduct(vector<int>& nums) {
const int inf = 1 << 30;
int mi1 = inf, mi2 = inf;
int mx1 = -inf, mx2 = -inf, mx3 = -inf;
for (int x : nums) {
if (x < mi1) {
mi2 = mi1;
mi1 = x;
} else if (x < mi2) {
mi2 = x;
}
if (x > mx1) {
mx3 = mx2;
mx2 = mx1;
mx1 = x;
} else if (x > mx2) {
mx3 = mx2;
mx2 = x;
} else if (x > mx3) {
mx3 = x;
}
}
return max(mi1 * mi2 * mx1, mx1 * mx2 * mx3);
}
};(code-box)
func maximumProduct(nums []int) int {
const inf = 1 << 30
mi1, mi2 := inf, inf
mx1, mx2, mx3 := -inf, -inf, -inf
for _, x := range nums {
if x < mi1 {
mi1, mi2 = x, mi1
} else if x < mi2 {
mi2 = x
}
if x > mx1 {
mx1, mx2, mx3 = x, mx1, mx2
} else if x > mx2 {
mx2, mx3 = x, mx2
} else if x > mx3 {
mx3 = x
}
}
return max(mi1*mi2*mx1, mx1*mx2*mx3)
}(code-box)
function maximumProduct(nums: number[]): number {
const inf = 1 << 30;
let mi1 = inf,
mi2 = inf;
let mx1 = -inf,
mx2 = -inf,
mx3 = -inf;
for (const x of nums) {
if (x < mi1) {
mi2 = mi1;
mi1 = x;
} else if (x < mi2) {
mi2 = x;
}
if (x > mx1) {
mx3 = mx2;
mx2 = mx1;
mx1 = x;
} else if (x > mx2) {
mx3 = mx2;
mx2 = x;
} else if (x > mx3) {
mx3 = x;
}
}
return Math.max(mi1 * mi2 * mx1, mx1 * mx2 * mx3);
}(code-box)
