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

1. Input: nums = [1,2,3]
   Output: 6
   Explanation: 1 × 2 × 3 = 6
2. Input: nums = [1,2,3,4]
   Output: 24
   Explanation: 2 × 3 × 4 = 24
3. Input: nums = [-10,-10,5,2]
   Output: 500
   Explanation: (−10) × (−10) × 5 = 500

Constraints

• 3 ≤ nums.length ≤ 10⁴
• -1000 ≤ nums[i] ≤ 1000

Hints

1. If you sort the array, which three positions could yield the maximum product?
2. 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

1. Initialize maxProduct = -∞.

2. Loop i from 0 to n−3.

3. Loop j from i+1 to n−2.

4. Loop k from j+1 to n−1.

5. Compute prod = nums[i] * nums[j] * nums[k].

6. Update maxProduct = max(maxProduct, prod).

7. 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