# Maximum Product of Three Numbers **Difficulty:** EASY [External](https://leetcode.com/problems/maximum-product-of-three-numbers) Canonical: https://scaleengineer.com/dsa/problems/maximum-product-of-three-numbers **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math) **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array **Companies:** [FreshWorks](https://scaleengineer.com/companies/freshworks), [Infosys](https://scaleengineer.com/companies/infosys), [Intuit](https://scaleengineer.com/companies/intuit), [Nutanix](https://scaleengineer.com/companies/nutanix), [Siemens](https://scaleengineer.com/companies/siemens), [Salesforce](https://scaleengineer.com/companies/salesforce), [Roku](https://scaleengineer.com/companies/roku) --- ## Problem 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 **Example 2:** **Input:** nums = [1,2,3,4] **Output:** 24 **Example 3:** **Input:** nums = [-1,-2,-3] **Output:** -6 **Constraints:** * `3 <= nums.length <= 104` * `-1000 <= nums[i] <= 1000` # Approaches ## Brute Force 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. **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. **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. ### Explanation 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. ```java 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; } } ``` ### Algorithm - Initialize a variable `maxProduct` to `Integer.MIN_VALUE`. - Use a loop to iterate from `i = 0` to `n-3`. - Inside this loop, use a nested loop to iterate from `j = i + 1` to `n-2`. - Inside the second loop, use a third nested loop to iterate from `k = j + 1` to `n-1`. - Calculate the product of `nums[i]`, `nums[j]`, and `nums[k]`. - Compare this product with `maxProduct` and update `maxProduct` if the current product is greater. - After the loops complete, return `maxProduct`. ## Sorting Approach 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. **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. **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. ### Explanation 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: 1. The product of the three largest numbers. 2. 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. ```java 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); } } ``` ### Algorithm - Sort the input array `nums` in non-decreasing order. - Let `n` be 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 `product1` and `product2`. ## Single Scan (Linear Time) 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. **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. **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. ### Explanation 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`, `min2` to store the two smallest numbers found so far (initialized to `Integer.MAX_VALUE`). - `max1`, `max2`, `max3` to store the three largest numbers found so far (initialized to `Integer.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. ```java 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); } } ``` ### Algorithm - Initialize two variables, `min1` and `min2`, to `Integer.MAX_VALUE`. - Initialize three variables, `max1`, `max2`, and `max3`, to `Integer.MIN_VALUE`. - Iterate through each number `num` in the `nums` array. - In each iteration, update the `min` and `max` variables: - If `num` is smaller than or equal to `min1`, update `min2 = min1` and `min1 = num`. - Else if `num` is smaller than or equal to `min2`, update `min2 = num`. - If `num` is greater than or equal to `max1`, update `max3 = max2`, `max2 = max1`, and `max1 = num`. - Else if `num` is greater than or equal to `max2`, update `max3 = max2` and `max2 = num`. - Else if `num` is greater than or equal to `max3`, update `max3 = num`. - After the loop, calculate `product1 = max1 * max2 * max3`. - Calculate `product2 = min1 * min2 * max1`. - Return the maximum of `product1` and `product2`. # Solutions ### Java ```java 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); } } ``` ### CPP ```cpp class Solution { public: int maximumProduct(vector &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); } }; ``` ### Python ```python 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]) ```