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] <= 1000This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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: |
Maximum Product Subarray - Dynamic Programming - Leetcode 152 • NeetCode • 452,934 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