Maximum Product of Three Numbers
EasyPrompt
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: 6Example 2:
Input: nums = [1,2,3,4]
Output: 24Example 3:
Input: nums = [-1,-2,-3]
Output: -6
Constraints:
3 <= nums.length <= 104-1000 <= nums[i] <= 1000
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves checking every possible combination of three numbers from the array. We use three nested loops to select three distinct numbers, calculate their product, and keep track of the maximum product found so far.
Algorithm
- Initialize a variable
maxProducttoInteger.MIN_VALUE. - Use a loop to iterate from
i = 0ton-3. - Inside this loop, use a nested loop to iterate from
j = i + 1ton-2. - Inside the second loop, use a third nested loop to iterate from
k = j + 1ton-1. - Calculate the product of
nums[i],nums[j], andnums[k]. - Compare this product with
maxProductand updatemaxProductif the current product is greater. - After the loops complete, return
maxProduct.
Walkthrough
The simplest way to solve the problem is to iterate through all unique triplets (i, j, k) where i < j < k. For each triplet, we calculate the product nums[i] * nums[j] * nums[k]. We maintain a variable, maxProduct, initialized to the smallest possible value, and update it with the current product if the current product is larger. After checking all possible triplets, maxProduct will hold the result.
class Solution { public int maximumProduct(int[] nums) { int n = nums.length; if (n < 3) { // This case is not possible based on constraints. return 0; } int maxProduct = Integer.MIN_VALUE; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { int currentProduct = nums[i] * nums[j] * nums[k]; if (currentProduct > maxProduct) { maxProduct = currentProduct; } } } } return maxProduct; }}Complexity
Time
O(n^3), where n is the number of elements in the `nums` array. This is because of the three nested loops, each iterating up to n times.
Space
O(1), as we only use a few variables to store the maximum product and loop indices, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Cons
Very inefficient and will likely result in a 'Time Limit Exceeded' error for large inputs, as its complexity is cubic.
A more efficient approach is to sort the array first. The maximum product will either be the product of the three largest numbers or the product of the two smallest (most negative) numbers and the largest number. After sorting, these numbers are easy to find.
Algorithm
- Sort the input array
numsin non-decreasing order. - Let
nbe the length of the array. - Calculate the first candidate product:
product1 = nums[n-1] * nums[n-2] * nums[n-3]. - Calculate the second candidate product:
product2 = nums[0] * nums[1] * nums[n-1]. - Return the maximum of
product1andproduct2.
Walkthrough
The key insight is that the three numbers that give the maximum product must involve the largest numbers in the array. However, we must also consider negative numbers. The product of two large negative numbers is a large positive number. Therefore, the maximum product can be one of two possibilities:
- The product of the three largest numbers.
- The product of the two smallest numbers (which could be negative) and the single largest number.
By sorting the array nums, we can easily identify these candidates. The three largest numbers will be at the end of the sorted array (nums[n-1], nums[n-2], nums[n-3]), and the two smallest numbers will be at the beginning (nums[0], nums[1]). We then calculate both potential maximum products and return the larger of the two.
import java.util.Arrays; class Solution { public int maximumProduct(int[] nums) { int n = nums.length; Arrays.sort(nums); // Candidate 1: Product of the three largest numbers int product1 = nums[n - 1] * nums[n - 2] * nums[n - 3]; // Candidate 2: Product of the two smallest (most negative) and the largest number int product2 = nums[0] * nums[1] * nums[n - 1]; return Math.max(product1, product2); }}Complexity
Time
O(n log n), dominated by the sorting algorithm. In Java, `Arrays.sort()` has an average time complexity of O(n log n).
Space
O(log n) to O(n), depending on the implementation of the sorting algorithm. `Arrays.sort()` in Java for primitive types uses a variant of Quicksort, which requires O(log n) space for the recursion stack on average.
Trade-offs
Pros
Much more efficient than the brute-force approach.
Relatively easy to implement using built-in sorting functions.
Cons
Not the most optimal solution as sorting the entire array is not strictly necessary.
The most optimal approach is to find the required numbers (three largest and two smallest) in a single pass through the array, without sorting it. This avoids the O(n log n) cost of sorting.
Algorithm
- Initialize two variables,
min1andmin2, toInteger.MAX_VALUE. - Initialize three variables,
max1,max2, andmax3, toInteger.MIN_VALUE. - Iterate through each number
numin thenumsarray. - In each iteration, update the
minandmaxvariables:- If
numis smaller than or equal tomin1, updatemin2 = min1andmin1 = num. - Else if
numis smaller than or equal tomin2, updatemin2 = num. - If
numis greater than or equal tomax1, updatemax3 = max2,max2 = max1, andmax1 = num. - Else if
numis greater than or equal tomax2, updatemax3 = max2andmax2 = num. - Else if
numis greater than or equal tomax3, updatemax3 = num.
- If
- After the loop, calculate
product1 = max1 * max2 * max3. - Calculate
product2 = min1 * min2 * max1. - Return the maximum of
product1andproduct2.
Walkthrough
We only need to know the three largest elements and the two smallest elements to determine the maximum product. We can find these five values by iterating through the array just once. We'll maintain five variables:
min1,min2to store the two smallest numbers found so far (initialized toInteger.MAX_VALUE).max1,max2,max3to store the three largest numbers found so far (initialized toInteger.MIN_VALUE).
As we iterate through each number num in the input array, we compare it with our tracked minimums and maximums and update them if num is smaller than min1 or min2, or larger than max1, max2, or max3. After the single pass is complete, we will have the two smallest and three largest numbers. Then, just like in the sorting approach, we compute the two candidate products and return the maximum.
class Solution { public int maximumProduct(int[] nums) { int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE; int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE; for (int num : nums) { // Update minimums if (num <= min1) { min2 = min1; min1 = num; } else if (num <= min2) { min2 = num; } // Update maximums if (num >= max1) { max3 = max2; max2 = max1; max1 = num; } else if (num >= max2) { max3 = max2; max2 = num; } else if (num >= max3) { max3 = num; } } int product1 = max1 * max2 * max3; int product2 = min1 * min2 * max1; return Math.max(product1, product2); }}Complexity
Time
O(n), as we iterate through the array only once.
Space
O(1), as we only use a constant number of variables to track the minimums and maximums, regardless of the input size.
Trade-offs
Pros
Most efficient solution with linear time complexity.
Constant space complexity.
Cons
The logic for updating the five tracking variables is slightly more complex to write correctly compared to the sorting approach.
Solutions
Solution
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); }};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])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.