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] <= 1000Problem Overview: You are given an integer array and must return the maximum product possible using any three numbers. The tricky part is handling negative values. Two large negative numbers multiplied together produce a positive number, which can sometimes beat the product of the three largest values.
Approach 1: Sorting for Maximum Product (O(n log n) time, O(1) space)
Sort the array and evaluate the only two combinations that can produce the maximum result. First, the product of the three largest numbers at the end of the sorted array. Second, the product of the two smallest numbers (which may be large negatives) with the largest number. After sorting, both combinations are available with direct index access, so you simply compute both and return the larger value. The logic relies on properties of signed multiplication and is easy to reason about, which makes it a common baseline solution when working with sorting problems on an array. The tradeoff is the O(n log n) sorting cost.
Approach 2: Single Pass Min/Max Tracking (O(n) time, O(1) space)
This approach avoids sorting by tracking the three largest numbers and the two smallest numbers during a single iteration of the array. Maintain variables for max1, max2, max3 (largest values) and min1, min2 (smallest values). For each element, update these trackers using simple comparisons. After one pass, compute two candidate products: max1 * max2 * max3 and max1 * min1 * min2. The first represents the top three positives, while the second captures the case where two negatives produce a large positive. This method uses constant memory and linear traversal, making it the optimal solution for large inputs and a classic pattern in math-based array optimization problems.
Recommended for interviews: The single-pass approach is what interviewers usually expect because it demonstrates awareness of edge cases with negative numbers while keeping the runtime at O(n). Mentioning the sorting solution first shows clear reasoning and correctness, but implementing the O(n) min/max tracking method shows stronger algorithmic thinking and attention to performance.
This approach involves sorting the array, and then choosing the maximum product by examining either the product of the three largest numbers or the product of the two smallest numbers and the largest number.
We sort the array using the standard library function qsort. After sorting, the maximum product can either be from the three largest numbers or from the product of the two smallest numbers and the largest number. This is due to the potential for large negative numbers producing a positive product.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we use in-place sorting.
This approach involves finding the largest three and smallest two numbers in a single traversal of the array. This avoids sorting and gives a more optimal solution for time complexity.
We maintain variables for the three largest and two smallest numbers as we iterate. This allows us to compute the potential maximum products and choose the maximum one without needing to sort the array.
Time Complexity: O(n) as there's only a single pass through the array.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Sorting for Maximum Product | Time Complexity: |
| Single Pass Approach | Time Complexity: |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting for Maximum Product | O(n log n) | O(1) | Simple and readable approach when sorting is acceptable |
| Single Pass Min/Max Tracking | O(n) | O(1) | Optimal solution for large arrays or interview scenarios |
628. Maximum Product of Three Numbers | LEETCODE EASY | SORTING | LOGIC • code Explainer • 13,516 views views
Watch 9 more video solutions →Practice Maximum Product of Three Numbers with our built-in code editor and test cases.
Practice on FleetCode