This is one of those problems where the clean idea matters more than the amount of code. For 628. Maximum Product of Three Numbers, the solution in this repository is mainly a greedy solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: greedy.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are maximumProduct.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n)O(n). Only one iteration over the numsnums array of length nn is required.
- Space: O(1)O(1). Constant extra space is used.
Guide
C++ Solution
Your submission
The accepted solution
01/**
02Given an integer array, find three numbers whose product is maximum and output the maximum product.
03
04Example 1:
05
06Input: [1,2,3]
07Output: 6
08
09
10Example 2:
11
12Input: [1,2,3,4]
13Output: 24
14
15
16Note:
17
18The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
19Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.
20**/
21
22/**
23Approach 2: Using Sorting
24Another solution could be to sort the given numsnums array(in ascending order) and find out the product of the last three numbers.
25
26But, we can note that this product will be maximum only if all the numbers in numsnums array are positive. But, in the given problem statement, negative elements could exist as well.
27
28Thus, it could also be possible that two negative numbers lying at the left extreme end could also contribute to lead to a larger product if the third number in the triplet being considered is the largest positive number in the numsnums array.
29
30Thus, either the product nums[0] \times nums[1] \times nums[n-1]nums[0]×nums[1]×nums[n−1] or nums[n-3] \times nums[n-2] \times nums[n-1]nums[n−3]×nums[n−2]×nums[n−1] will give the required result. Thus, we need to find the larger one from out of these values.
31**/
32/**
33Complexity Analysis
34
35Time complexity : O\big(n\log n\big)O(nlogn). Sorting the numsnums array takes n\log nnlogn time.
36
37Space complexity : O(\log n)O(logn). Sorting takes O(\log n)O(logn) space.
38**/
39class Solution {
40public:
41 int maximumProduct(vector<int>& nums) {
42 int n = nums.size();
43 sort(nums.begin(), nums.end());
44 return max(nums[0]*nums[1]*nums[n-1], nums[n-3]*nums[n-2]*nums[n-1]);
45 }
46};
47
48/**
49Approach 3: Single Scan
50**/
51
52/**
53Complexity Analysis
54
55Time complexity : O(n)O(n). Only one iteration over the numsnums array of length nn is required.
56
57Space complexity : O(1)O(1). Constant extra space is used.
58**/
59
60//Runtime: 48 ms, faster than 86.06% of C++ online submissions for Maximum Product of Three Numbers.
61//Memory Usage: 10.9 MB, less than 97.89% of C++ online submissions for Maximum Product of Three Numbers.
62
63/**
64class Solution {
65public:
66 int maximumProduct(vector<int>& nums) {
67 int min1 = INT_MAX, min2 = INT_MAX;
68 int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
69
70 for(int n : nums){
71 if(n <= min1){
72 min2 = min1;
73 min1 = n;
74 }else if(n <= min2){
75 min2 = n;
76 }
77
78 if(n >= max1){
79 max3 = max2;
80 max2 = max1;
81 max1 = n;
82 }else if(n >= max2){
83 max3 = max2;
84 max2 = n;
85 }else if(n >= max3){
86 max3 = n;
87 }
88 }
89 return max(min1*min2*max1, max1*max2*max3);
90 }
91};
92**/Cost