LeetCode 628: Maximum Product of Three Numbers Solution in Python – A Step-by-Step Guide

What Is LeetCode 628: Maximum Product of Three Numbers?

In LeetCode 628: Maximum Product of Three Numbers, you’re given an integer array nums, and your task is to find the maximum product of any three distinct elements. The array can include positive and negative numbers, so you need to consider both the largest positives (e.g., 2 * 3 * 4) and the potential of two large negatives with a positive (e.g., -4 * -3 * 2). For example, in [1, 2, 3, 4], the max is 24 (2 * 3 * 4), but in [-4, -3, -2, 1, 60], it’s 720 (-4 * -3 * 60). This problem tests your ability to handle sign combinations and optimize triplet selection.

Problem Statement

• Input:
• nums: A list of integers.
• Output: An integer—the maximum product of three numbers.
• Rules:
• Choose exactly three distinct elements.
• Maximize their product.
• Array contains positives, negatives, and possibly zeros.

Constraints

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

Examples

• Input: nums = [1, 2, 3, 4]
• Output: 24 (2 3 4)
• Input: nums = [-4, -3, -2, 1, 60]
• Output: 720 (-4 -3 60)
• Input: nums = [1, 2, 3]
• Output: 6 (1 2 3)

These examples highlight the challenge—let’s solve it!

Understanding the Problem: Maximizing a Triplet Product

To solve LeetCode 628: Maximum Product of Three Numbers in Python, we need to find three numbers in an array that, when multiplied, give the largest possible result. A brute-force approach might check every triplet (O(n³)), but with array sizes up to 10⁴, we need efficiency. Since we’re picking three numbers, the max product comes from either:

• The three largest numbers (all positive).
• Two smallest numbers (possibly negative) and the largest (if negatives yield a big positive).

We’ll use:

• Best Solution (Sorting-Based Approach): O(n log n) time, O(1) space—fast and clear.
• Alternative Solution (Linear Scan with Tracking): O(n) time, O(1) space—manual but optimal.

Let’s start with the sorting solution, breaking it down for beginners.

Best Solution: Sorting-Based Approach

Why This Is the Best Solution

The sorting-based approach is the top choice for LeetCode 628 because it’s efficient—O(n log n) time with O(1) extra space—and straightforward, leveraging Python’s sorting to quickly identify key elements. It handles all cases (positives, negatives, zeros) by comparing the product of the three largest numbers with the product of two smallest and the largest, ensuring the max is found in one pass after sorting. It’s like lining up your numbers and picking the best team!

How It Works

Think of this as a number lineup:

• Step 1: Sort the Array:
• Arrange nums in ascending order.
• Step 2: Identify Candidates:
• Three largest: Last three elements (nums[-1], nums[-2], nums[-3]).
• Two smallest and largest: First two and last (nums[0], nums[1], nums[-1]).
• Step 3: Compute Products:
• Product 1: Three largest.
• Product 2: Two smallest and largest.
• Step 4: Return Maximum:
• Take the max of the two products.

It’s like a product picker—sort and choose!

Step-by-Step Example

Example: nums = [1, 2, 3, 4]

• Step 1: Sort: [1, 2, 3, 4].
• Step 2: Candidates:
• Three largest: 4, 3, 2.
• Two smallest: 1, 2; largest: 4.
• Step 3: Products:
• 4 3 2 = 24.
• 1 2 4 = 8.
• Step 4: Max(24, 8) = 24.
• Output: 24.

Example: nums = [-4, -3, -2, 1, 60]

• Step 1: Sort: [-4, -3, -2, 1, 60].
• Step 2:
• Three largest: 60, 1, -2.
• Two smallest: -4, -3; largest: 60.
• Step 3:
• 60 1 -2 = -120.
• -4 -3 60 = 720.
• Step 4: Max(-120, 720) = 720.
• Output: 720.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        # Step 1: Sort the array
        nums.sort()

        # Step 2: Compute two possible products
        # Product of three largest numbers
        prod1 = nums[-1] * nums[-2] * nums[-3]
        # Product of two smallest and largest
        prod2 = nums[0] * nums[1] * nums[-1]

        # Step 3: Return the maximum
        return max(prod1, prod2)

• Line 4: Sort nums ascending.
• Lines 7-9: Compute products:
• prod1: Last three elements.
• prod2: First two and last.
• Line 12: Return max of products.
• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(1)—in-place sort.

This is like a product optimizer—sort and pick!

Alternative Solution: Linear Scan with Tracking

Why an Alternative Approach?

The linear scan with tracking finds the three largest and two smallest numbers in one pass—O(n) time, O(1) space. It’s more manual, avoiding sorting for optimal time complexity, but requires careful bookkeeping. It’s like scouting the array for the best players without lining them up!

How It Works

Picture this as a number scout:

• Step 1: Initialize trackers:
• Three largest: max1, max2, max3.
• Two smallest: min1, min2.
• Step 2: Scan array:
• Update maxes if larger, shift down.
• Update mins if smaller, shift up.
• Step 3: Compute products:
• max1 max2 max3.
• min1 min2 max1.
• Step 4: Return max.

It’s like a talent spotter—track and compute!

Step-by-Step Example

Example: nums = [-4, -3, -2, 1, 60]

• Step 1: Init:
• max1 = -inf, max2 = -inf, max3 = -inf.
• min1 = inf, min2 = inf.
• Step 2: Scan:
• -4: max1 = -4, min1 = -4.
• -3: max1 = -3, max2 = -4, min1 = -4, min2 = -3.
• -2: max1 = -2, max2 = -3, max3 = -4.
• 1: max1 = 1, max2 = -2, max3 = -3.
• 60: max1 = 60, max2 = 1, max3 = -2.
• Step 3: Products:
• 60 1 -2 = -120.
• -4 -3 60 = 720.
• Step 4: Max(-120, 720) = 720.
• Output: 720.

Code for Linear Scan Approach

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        # Step 1: Initialize trackers
        max1 = max2 = max3 = float('-inf')  # Three largest
        min1 = min2 = float('inf')          # Two smallest

        # Step 2: Scan array
        for num in nums:
            # Update three largest
            if num >= max1:
                max3, max2, max1 = max2, max1, num
            elif num >= max2:
                max3, max2 = max2, num
            elif num > max3:
                max3 = num

            # Update two smallest
            if num <= min1:
                min2, min1 = min1, num
            elif num < min2:
                min2 = num

        # Step 3: Compute products
        prod1 = max1 * max2 * max3
        prod2 = min1 * min2 * max1

        # Step 4: Return maximum
        return max(prod1, prod2)

• Lines 4-5: Init maxes and mins.
• Lines 8-19: Update trackers in one pass.
• Lines 22-24: Compute products.
• Time Complexity: O(n)—single scan.
• Space Complexity: O(1)—few variables.

It’s a number tracker—fast but manual!

Comparing the Two Solutions

• Sorting (Best):
• Pros: O(n log n) time, O(1) space, simple and clear.
• Cons: Slightly slower due to sort.
• Linear Scan (Alternative):
• Pros: O(n) time, O(1) space, optimal time.
• Cons: More complex logic.

Sorting wins for clarity and practicality.

Additional Examples and Edge Cases

• Input: [0, 0, 0]
• Output: 0.
• Input: [-5, -2, 1]
• Output: 10 (-5 -2 1).

Both handle these well.

Complexity Breakdown

• Sorting: Time O(n log n), Space O(1).
• Linear Scan: Time O(n), Space O(1).

Linear scan is theoretically faster, sorting simpler.

Key Takeaways

• Sorting: Easy pick—smart!
• Linear Scan: Fast track—clear!
• Numbers: Products are fun.
• Python Tip: Sorting rocks—see Python Basics.

Final Thoughts: Multiply Those Numbers

LeetCode 628: Maximum Product of Three Numbers in Python is a fun optimization challenge. Sorting offers clarity and ease, while linear scanning provides peak efficiency. Want more? Try LeetCode 152: Maximum Product Subarray or LeetCode 414: Third Maximum Number. Ready to multiply? Head to Solve LeetCode 628 on LeetCode and find that max product today!