Welcome to Subscribe On Youtube
628. Maximum Product of Three Numbers
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 $\textit{nums}$, and then discuss two cases:
- If $\textit{nums}$ contains all non-negative or all non-positive numbers, the answer is the product of the last three numbers, i.e., $\textit{nums}[n-1] \times \textit{nums}[n-2] \times \textit{nums}[n-3]$;
- If $\textit{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., $\textit{nums}[n-1] \times \textit{nums}[0] \times \textit{nums}[1]$, or the product of the last three numbers, i.e., $\textit{nums}[n-1] \times \textit{nums}[n-2] \times \textit{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 $\textit{nums}$.
Solution 2: Single Pass
We can avoid sorting the array by maintaining five variables: $\textit{mi1}$ and $\textit{mi2}$ represent the two smallest numbers in the array, while $\textit{mx1}$, $\textit{mx2}$, and $\textit{mx3}$ represent the three largest numbers in the array.
Finally, return $\max(\textit{mi1} \times \textit{mi2} \times \textit{mx1}, \textit{mx1} \times \textit{mx2} \times \textit{mx3})$.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
-
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); } } // Solution 2 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); } } -
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); } }; // Solution 2 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); } }; -
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]) # Solution 2 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]) -
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) } // Solution 2 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) } -
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); } // Solution 2 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); }