628. Maximum Product of Three Numbers
DifficultyEasy
Description
You are 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
Explanation:
The only three numbers are 1, 2, and -3, so the maximum product is 1 * 2 * -3 = -6.
Example 2:
Input: nums = [1,2,3,4]
Output: 24
Explanation:
The largest product comes from the three greatest numbers: 2 * 3 * 4 = 24.
Example 3:
Input: nums = [-1,-2,-3]
Output: -6
Explanation:
The only three numbers are -1, -2, and -3, so the maximum product is (-1) * (-2) * (-3) = -6.
Constraints:
3 <= nums.length <= 104-1000 <= nums[i] <= 1000
Solutions
Solution 1: Sorting + Case Analysis
Thinking
The maximum product of three numbers is either the three largest values or the two smallest (possibly negative) times the largest. Sorting is cheap for \(n\le 10^4\).
After sorting, compare \(\textit{nums}[-1]\times \textit{nums}[-2]\times \textit{nums}[-3]\) with \(\textit{nums}[-1]\times \textit{nums}[0]\times \textit{nums}[1]\).
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 \log n)\), and the space complexity is \(O(\log n)\), where \(n\) is the length of the array \(\textit{nums}\).
1 2 3 4 5 6 | |
1 2 3 4 5 6 7 8 9 | |
1 2 3 4 5 6 7 8 9 10 | |
1 2 3 4 5 6 7 8 9 10 | |
1 2 3 4 5 6 7 | |
Solution 2: Single Pass
Thinking
Sorting is more than we need: only the two smallest and three largest values matter. A linear pass (or nlargest) keeps those five extrema.
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)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array.
1 2 3 4 5 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | |