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] <= 1000The goal of #628 Maximum Product of Three Numbers is to find the largest possible product formed by any three integers in an array. Because the array may contain negative values, the maximum product does not always come from the three largest numbers. Two large negative numbers multiplied together can produce a large positive value, which can significantly affect the result.
A common strategy is to sort the array. After sorting, compare the product of the three largest numbers with the product of the two smallest numbers and the largest number. The maximum of these two possibilities gives the correct result.
An optimized method avoids full sorting by tracking the three largest and two smallest values during a single pass through the array. This reduces the time complexity while still considering negative-number scenarios. Sorting takes O(n log n) time, while the single-pass approach runs in O(n) time with constant space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting the Array | O(n log n) | O(1) |
| Single Pass Tracking Max/Min Values | O(n) | O(1) |
NeetCode
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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we use in-place sorting.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
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.
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.
Time Complexity: O(n) as there's only a single pass through the array.
Space Complexity: O(1).
1def
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in technical interviews at large tech companies. It tests understanding of edge cases, handling negative numbers, and optimizing from a sorting approach to a linear-time solution.
The optimal approach tracks the three largest numbers and the two smallest numbers in a single pass through the array. This works because two negative numbers can create a large positive product when multiplied with the largest number. The method runs in O(n) time and uses constant space.
Negative numbers are important because multiplying two negative values results in a positive number. In some cases, the product of the two smallest (most negative) numbers and the largest positive number is greater than the product of the three largest numbers.
The problem typically uses arrays and simple variable tracking. Some solutions sort the array, while optimized approaches maintain running values for the largest and smallest elements without additional data structures.
This solution captures the top three largest and two smallest values during one loop through the list, allowing us to calculate and compare the products efficiently.