Problem
Given an integer array, find three numbers whose product is maximum and output the maximum product.
Example 1:
Input: [1,2,3] Output: 6
Example 2:
Input: [1,2,3,4] Output: 24
Note:
- The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
- Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.
Idea:
Find the top 3 numbers t1, t2, t3, and bottom 2 numbers, b1, b2.
If all numbers are positives, answer must be t1 * t2 * t3.
Since the number can go negative, the answer must be either t1*t2*t3 or b1 * b2 * t1, if b1 and b2 are both negatives.
ex. nums: [5, 1, -6, 3, -1]
t1, t2, t3: 5, 3, 1
b1, b2: -6, -1
t1 * t2 * t3 = 15
t1 * b1 * b2 = 30
Solution 1: Manual Tracking
Time complexity: O(n)
Space complexity: O(1)
|
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 28 29 30 31 32 33 34 |
// Author: Huahua // Running time: 28 ms class Solution { public: int maximumProduct(vector<int>& nums) { int max1 = INT_MIN; int max2 = INT_MIN; int max3 = INT_MIN; int min1 = INT_MAX; int min2 = INT_MAX; for (const int num: nums) { if (num > max1) { max3 = max2; max2 = max1; max1 = num; } else if (num > max2) { max3 = max2; max2 = num; } else if (num > max3) { max3=num; } if (num < min1) { min2 = min1; min1 = num; } else if (num < min2) { min2=num; } } return max(max1*max2*max3, max1*min1*min2); } }; |
Solution 2: Sorting
Time complexity: O(nlogn)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua // Running time: 48 ms class Solution { public: int maximumProduct(vector<int>& nums) { int n = nums.size(); sort(nums.rbegin(), nums.rend()); return max(nums[0] * nums[1] * nums[2], nums[0] * nums[n - 1] * nums[n - 2]); } }; |
Solution 3: Two Heaps (Priority Queues)
Time complexity: O(nlog3)
Space complexity: O(2 + 3)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 40 ms class Solution { public: int maximumProduct(vector<int>& nums) { priority_queue<int, vector<int>, less<int>> min_q; // max_heap priority_queue<int, vector<int>, greater<int>> max_q; // min_heap for (int num : nums) { max_q.push(num); if (max_q.size() > 3) max_q.pop(); min_q.push(num); if (min_q.size() > 2) min_q.pop(); } int max3 = max_q.top(); max_q.pop(); int max2 = max_q.top(); max_q.pop(); int max1 = max_q.top(); max_q.pop(); int min2 = min_q.top(); min_q.pop(); int min1 = min_q.top(); min_q.pop(); return max(max1 * max2 * max3, max1 * min1 * min2); } }; |