628. Maximum Product of Three Numbers
Model: qwen2.5-coder:14b
Topics: Array,Math
FAANG asked: 1
Acceptance rate: 46.8%
Problem Breakdown
The problem requires finding three numbers in an integer array whose product is maximum and returning that product. The input is an array of integers nums with a length between 3 and 10,000. Each element in the array can range from -1000 to 1000. The output should be the highest possible product of any three numbers from the array.
Inputs:
- An integer array
nums.
Outputs:
- The maximum product of any three numbers in the array.
Implicit Constraints or Tricky Edge Cases:
- The array can contain negative numbers, which could result in a positive product if two negatives are multiplied together.
- The array might have duplicate values, but this doesn’t affect the logic since we’re looking for the maximum product.
- Overflow is not an issue given the constraints.
Intuition
A brute-force approach would involve checking all possible combinations of three numbers from the array and calculating their products. This approach would be computationally expensive with a time complexity of O(n^3), which is inefficient for large arrays.
The key insight to improve this solution is to recognize that the maximum product can only be achieved in one of two ways:
- By multiplying the three largest numbers.
- By multiplying the two smallest (most negative) numbers and the largest number.
This observation allows us to reduce the problem to sorting the array and then considering these two potential products, resulting in a more efficient solution with O(n log n) time complexity due to sorting.
Approach
- Sort the array
nums. - Calculate the product of the three largest numbers:
nums[-1] * nums[-2] * nums[-3]. - Calculate the product of the two smallest numbers and the largest number:
nums[0] * nums[1] * nums[-1]. - Return the maximum of these two products.
Complexity Analysis
- Time Complexity: O(n log n) due to sorting the array.
- Space Complexity: O(1) as we are using a constant amount of extra space.
Solution
def maximumProduct(nums):
nums.sort()
return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])
Edge Cases Handled
- All positive numbers: The product of the three largest numbers will be correct.
- All negative numbers: The product of the two smallest (most negative) and the largest number will be correct.
- Mixed positive and negative numbers: Both potential products are considered, ensuring the maximum is found.
- Duplicates: Duplicates do not affect the logic since we’re looking for the maximum product of any three numbers.