Watch 10 video solutions for Maximum Product of Three Numbers, a easy level problem involving Array, Math, Sorting. This walkthrough by code Explainer has 13,516 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |