628. Maximum Product of Three Numbers - Detailed Explanation
Problem Statement
Given an integer array nums, find three numbers whose product is maximum and return the maximum product.
Examples
- Input:
nums = [1,2,3]
Output:6
Explanation: 1 × 2 × 3 = 6 - Input:
nums = [1,2,3,4]
Output:24
Explanation: 2 × 3 × 4 = 24 - Input:
nums = [-10,-10,5,2]
Output:500
Explanation: (−10) × (−10) × 5 = 500
Constraints
3 ≤ nums.length ≤ 10⁴-1000 ≤ nums[i] ≤ 1000
Hints
- If you sort the array, which three positions could yield the maximum product?
- What role do negative numbers play when multiplied in pairs?
Approach 1 Brute Force Triplet Enumeration
Explanation
Try every combination of three distinct indices (i, j, k), compute nums[i] * nums[j] * nums[k], and track the maximum. This guarantees correctness but is too slow for large inputs.
Step‑by‑step Walkthrough
-
Initialize
maxProduct = -∞. -
Loop
ifrom0ton−3. -
Loop
jfromi+1ton−2. -
Loop
kfromj+1ton−1. -
Compute
prod = nums[i] * nums[j] * nums[k]. -
Update
maxProduct = max(maxProduct, prod). -
Return
maxProduct.
Visual Example
nums = [−10, 5, 2, −10]
Triplets and products:
(−10, 5, 2) → −100
(−10, 5, −10) → 500 ← maximum
(−10, 2, −10) → 200
(5, 2, −10) → −100
…etc.
Python Code
Java Code
Complexity Analysis
- Time O(n³)
- Space O(1)
Approach 2 Sorting Based
Explanation
After sorting, the maximum product is either the product of the three largest numbers or the product of the two smallest (most negative) numbers and the largest number.
Step‑by‑step Walkthrough
- Sort
nums. - Compute
a = nums[n-1] * nums[n-2] * nums[n-3]. - Compute
b = nums[0] * nums[1] * nums[n-1]. - Return
max(a, b).
Visual Example
nums = [−10, 2, 5, −10] → sorted [−10, −10, 2, 5]
a = 5 × 2 × (−10) = −100
b = (−10) × (−10) × 5 = 500 ← answer
Python Code
Java Code
Complexity Analysis
- Time O(n log n) due to sorting
- Space O(1) (or O(log n) if sorting in-place stack usage counted)
Approach 3 One‑pass Scan (Optimal)
Explanation
Track the three largest and two smallest elements in one pass; then compute the same two candidate products as in sorting.
Step‑by‑step Walkthrough
- Initialize
max1, max2, max3 = -∞andmin1, min2 = +∞. - For each
xinnums:- Update
max1, max2, max3appropriately ifxis among the top three. - Update
min1, min2ifxis among the bottom two.
- Update
- Return
max(max1*max2*max3, min1*min2*max1).
Visual Example
nums = [−10, 2, 5, −10]
After scan:
max1=5, max2=2, max3=−10
min1=−10, min2=−10
Compare 5*2*(−10)=−100 vs (−10)*(−10)*5=500 → 500
Python Code
Java Code
Complexity Analysis
- Time O(n)
- Space O(1)
Common Mistakes
- Forgetting that two large negatives can boost the product
- Only tracking the top three positives
- Incorrectly updating maxima/minima in the wrong order
Edge Cases
- Exactly three elements → direct product
- All positives
- Mix of positives and negatives
- Zeros present
Alternative Variations
- Maximum product of
knumbers instead of three - Maximum product subarray (contiguous)
- Minimum product of three numbers
Related Problems
GET YOUR FREE
Coding Questions Catalog
