628. Maximum Product of Three Numbers
Problem Description
The given problem provides an integer array called nums. The objective is to determine three numbers from this array such that their product is the maximum possible among all combinations of three numbers from the array. The function should then return this maximum product. This is essentially a problem of combination and maximizing an objective function under certain constraints (in this case, the product of three numbers).
Intuition
The intuition behind the solution approach is based on considering the nature of the product operation in mathematics and the distribution of positive and negative values within the integer array:
-
The largest product of three numbers could be the product of the three largest numbers in the array. This is simply because larger numbers generally lead to larger products, especially when they are all positive.
-
However, if the array contains negative numbers, the scenario changes slightly. The product of two negative numbers is positive. Therefore, if the largest number is positive, the product of this number with two large negative numbers (which become positive when multiplied together) could potentially be larger than the product of three positive numbers. This situation arises if there are at least two negative numbers in the array with large absolute values.
Combining these two observations, we realize there are two scenarios to consider for obtaining the maximum product:
- The product of the three largest numbers (in case they are all positive or two of them are negative).
- The product of the largest number and the two smallest numbers (which would be the largest negative numbers if negatives are present).
The Python code implements this approach by first finding the three largest numbers in the array using a built-in function nlargest(3, nums), which returns the three largest numbers in descending order. Then it finds the two smallest numbers by once again using nlargest(2, nums, key=lambda x: -x) where the key argument transforms the problem into finding the "largest" numbers when viewed as negative, essentially giving us the smallest numbers of the array.
Finally, it computes the maximum product by considering both scenarios mentioned above and returns the greater of the two.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Solution Approach
To implement the solution, the Python code uses two important functions from the heapq module: nlargest() and nsmallest(). However, the provided solution cleverly only uses nlargest() in both cases, once with the default behavior and once with a key function to change the behavior.
The heapq.nlargest(n, iterable) function is used to find out the n largest numbers from the given iterable. It is an efficient way to obtain the largest values without the need to sort the entire array. Sorting would have a time complexity of O(nlogn), but nlargest() can perform the same task in O(nlogk) time complexity, where k is the number of largest elements to find, which is more efficient when k is much smaller than n.
Here's a breakdown of how the code operates:
-
top3 = nlargest(3, nums): This line uses thenlargest()function to find the three largest numbers in thenumsarray. The resulting listtop3contains these numbers in descending order. -
bottom2 = nlargest(2, nums, key=lambda x: -x): This line again uses thenlargest()function, but with a key functionlambda x: -xthat negates the numbers innums. By doing this, the function effectively retrieves the two smallest numbers, because negating the numbers turns the task of finding the largest negative numbers into finding the largest numbers post-negation. -
return max(top3[0] * top3[1] * top3[2], top3[0] * bottom2[0] * bottom2[1]): This is the final step which compares the product of the top three largest numbers with the product of the largest number and the two smallest numbers (which could be negative). Themax()function is used here to return the larger of these two products, which is the desired maximum product of three numbers in the array.
By using a combination of heap operations and the max() function, the solution arrives at the correct maximum product without having to sort the entire array, thus making the solution more efficient for larger inputs.
How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).
Example Walkthrough
Let's consider a small example with the following integer array:
1nums = [-10, -10, 5, 4]
Here is how the solution approach would work with this array:
-
Find the three largest numbers: We use the
heapq.nlargest(3, nums)function, which would return[5, 4, -10]because 5 is the largest, followed by 4, and then -10 (which is larger than the other -10 based on hownlargestbreaks ties). This gives us our first potential set of numbers for the maximum product. -
Find the two smallest numbers: We employ the
heapq.nlargest(2, nums, key=lambda x: -x)function, which with the negating key finds the "largest" numbers when viewed as negative, effectively returning[ -10, -10]because these are the smallest numbers when their sign is negated (they become the largest positively). -
Calculate the products and find the maximum: We have two sets of numbers to consider,
[5, 4, -10]and[5, -10, -10]. We calculate the products of these combinations:- The product of
5 * 4 * -10is-200. - The product of
5 * -10 * -10is500.
- The product of
-
Return the maximum product: Between the two products
-200and500, the larger product is500, which is the expected output from our function.
The application of the solution has clearly walked us through a simple example and demonstrated the effectiveness of considering both the largest positive and largest negative numbers in the array to obtain the maximum product of three numbers.
Solution Implementation
1from heapq import nlargest # Import the nlargest function from heapq module
2
3class Solution:
4 def maximumProduct(self, nums: List[int]) -> int:
5 # Find the three largest numbers from the list using nlargest
6 top_3 = nlargest(3, nums)
7 # Find the two smallest numbers from the list using nlargest with a key that inverts the values for sorting
8 bottom_2 = nlargest(2, nums, key=lambda x: -x)
9
10 # The maximum product can be either the product of the three largest numbers
11 # or the product of the two smallest numbers and the largest number
12 # (in case of two large negative numbers and one positive number)
13 return max(
14 top_3[0] * top_3[1] * top_3[2], # Product of the three largest numbers
15 top_3[0] * bottom_2[0] * bottom_2[1] # Product of the largest number and two smallest (negative) numbers
16 )
171class Solution {
2 public int maximumProduct(int[] nums) {
3 // Define infinity value to represent very high positive value
4 // as Java doesn't include infinity for integers.
5 final int infinity = Integer.MAX_VALUE;
6
7 // Initialize variables to represent the smallest and second smallest numbers
8 int min1 = infinity;
9 int min2 = infinity;
10
11 // Initialize variables to represent the largest, second largest, and third largest numbers
12 int max1 = -infinity;
13 int max2 = -infinity;
14 int max3 = -infinity;
15
16 // Traverse through the array
17 for (int num : nums) {
18
19 // Check if current number is smaller than the smallest or second smallest
20 if (num <= min1) {
21 min2 = min1; // Smallest number becomes second smallest
22 min1 = num; // Current number is the new smallest
23 } else if (num <= min2) {
24 min2 = num; // Current number is the new second smallest
25 }
26
27 // Check if current number is larger than the largest, second or third largest
28 if (num >= max1) {
29 max3 = max2; // Second largest number becomes third largest
30 max2 = max1; // Largest number becomes second largest
31 max1 = num; // Current number is the new largest
32 } else if (num >= max2) {
33 max3 = max2; // Second largest number becomes third largest
34 max2 = num; // Current number is the new second largest
35 } else if (num >= max3) {
36 max3 = num; // Current number is the new third largest
37 }
38 }
39
40 // Compute the maximum product by comparing two possibilities:
41 // 1. Product of the three largest numbers.
42 // 2. Product of the smallest two numbers and the largest number.
43 // This accounts for the case where the two smallest numbers might be negative,
44 // and their product with the largest positive number could be maximum.
45 return Math.max(min1 * min2 * max1, max1 * max2 * max3);
46 }
47}
481#include <vector>
2#include <algorithm> // Required for std::max
3
4class Solution {
5public:
6 int maximumProduct(vector<int>& nums) {
7 // Initialize constants and variables to keep track of the smallest and largest values.
8 const int MAX_INT = INT_MAX; // Using INT_MAX from climits instead of a hardcoded value.
9 const int MIN_INT = INT_MIN; // Using INT_MIN for clarity when initializing maximums.
10 int min1 = MAX_INT, min2 = MAX_INT; // Smallest and second smallest numbers.
11 int max1 = MIN_INT, max2 = MIN_INT, max3 = MIN_INT; // Largest, second, and third largest numbers.
12
13 // Iterate over the numbers to find the top two minimums and top three maximums.
14 for (int num : nums) {
15 // Check for new smallest or second smallest.
16 if (num < min1) {
17 min2 = min1;
18 min1 = num;
19 } else if (num < min2) {
20 min2 = num;
21 }
22
23 // Check for new largest, second or third largest.
24 if (num > max1) {
25 max3 = max2;
26 max2 = max1;
27 max1 = num;
28 } else if (num > max2) {
29 max3 = max2;
30 max2 = num;
31 } else if (num > max3) {
32 max3 = num;
33 }
34 }
35
36 // The maximum product can either be from three largest numbers
37 // or from two smallest numbers (which might be negative) and the largest number.
38 return std::max(min1 * min2 * max1, max1 * max2 * max3);
39 }
40};
411function maximumProduct(nums: number[]): number {
2 // Initialize the smallest and second smallest values with the maximum safe integer.
3 let smallest = Number.MAX_SAFE_INTEGER;
4 let secondSmallest = Number.MAX_SAFE_INTEGER;
5 // Initialize the largest, second largest, and third largest values with the minimum safe integer.
6 let largest = Number.MIN_SAFE_INTEGER;
7 let secondLargest = Number.MIN_SAFE_INTEGER;
8 let thirdLargest = Number.MIN_SAFE_INTEGER;
9
10 for (const num of nums) {
11 // Check if current number is smaller than the smallest or the second smallest.
12 if (num < smallest) {
13 secondSmallest = smallest;
14 smallest = num;
15 } else if (num < secondSmallest) {
16 secondSmallest = num;
17 }
18
19 // Check if current number is larger than the largest, second largest, or third largest.
20 if (num > largest) {
21 thirdLargest = secondLargest;
22 secondLargest = largest;
23 largest = num;
24 } else if (num > secondLargest) {
25 thirdLargest = secondLargest;
26 secondLargest = num;
27 } else if (num > thirdLargest) {
28 thirdLargest = num;
29 }
30 }
31
32 // Calculate and return the maximum product of three numbers.
33 // Need to consider the product of the largest with two smallest (could be negatives making a positive)
34 // and the product of the three largest numbers.
35 return Math.max(smallest * secondSmallest * largest, largest * secondLargest * thirdLargest);
36}
37Which of these pictures shows the visit order of a depth-first search?
Time and Space Complexity
The provided Python code computes the maximum product of three numbers in a list using two operations: finding the three largest elements and the two smallest (or "bottom") elements.
Time Complexity
The time complexity of the nlargest(3, nums) operation is O(N * log(3)) since it maintains a heap of size 3 during iteration over the list of N numbers, and each insertion into the heap takes logarithmic time. Similarly, the nlargest(2, nums, key=lambda x: -x) operation has a time complexity of O(N * log(2)). However, because the base of the logarithm is constant and small, the complexities can be considered close to O(N) for each operation, and because they do not depend on each other and are not nested, they could be summed up. Therefore, the overall time complexity is O(N + N), which simplifies to O(N).
Space Complexity
The space complexity is the additional space required besides the input. Here, it includes the space for storing the largest and smallest elements. Since it stores a constant number of elements (three for the largest and two for the smallest), the space complexity is O(1) as it does not scale with the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following array represent a max heap?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.