Code Implementation

class Solution:
    def maximumProduct(self, nums):
        nums.sort()
        # Product of three largest OR two smallest (possibly negative) and the largest
        return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])
      

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        return max(nums[n-1] * nums[n-2] * nums[n-3],
                   nums[0] * nums[1] * nums[n-1]);
    }
};
      

class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return Math.max(nums[n-1] * nums[n-2] * nums[n-3],
                        nums[0] * nums[1] * nums[n-1]);
    }
}
      

var maximumProduct = function(nums) {
    nums.sort((a, b) => a - b);
    let n = nums.length;
    return Math.max(nums[n-1] * nums[n-2] * nums[n-3],
                    nums[0] * nums[1] * nums[n-1]);
};
      

Problem Description

Given an integer array nums, find the maximum product you can get by multiplying any three distinct numbers from the array. The array contains at least three integers, and can include both positive and negative numbers. You must choose three different elements (no reuse), and return the largest possible product.

Key Constraints:

• Each input has at least three elements.
• Elements can be negative, zero, or positive.
• You must use three distinct elements.
• There is always at least one valid solution.

Thought Process

At first glance, it might seem like the largest product would always come from the three biggest numbers in the array. However, because negative numbers can multiply to make a positive result, we need to consider cases where using two negative numbers and a large positive number could yield a bigger product.

A brute-force approach would be to check the product of every combination of three numbers, but that's inefficient for large arrays. Instead, we can optimize by focusing on the largest three numbers and the smallest two numbers (which could be negative) plus the largest number.

The key insight is that either:

• The product of the three largest numbers is maximal, or
• The product of the two smallest numbers (possibly both negative) and the largest number is maximal.

Solution Approach

Let's break down the steps to solve this efficiently:

1. Sort the array. This puts the smallest numbers at the start and the largest at the end.
2. Compute two candidate products:
   • The product of the three largest numbers: nums[-1] * nums[-2] * nums[-3]
   • The product of the two smallest numbers (could be negative) and the largest: nums[0] * nums[1] * nums[-1]
3. Return the maximum of these two products.

By sorting, we can directly access the numbers we care about. This approach is simple, avoids unnecessary computation, and always considers the edge case with negative numbers.

Example Walkthrough

Suppose nums = [-10, -10, 5, 2].

1. Sort the array: [-10, -10, 2, 5]
2. Compute the two candidate products:
   • Product of three largest: 5 * 2 * -10 = -100
   • Product of two smallest and largest: -10 * -10 * 5 = 500
3. Choose the maximum: max(-100, 500) = 500

The answer is 500, which comes from multiplying the two smallest (most negative) numbers with the largest positive number.

Time and Space Complexity

Brute-force approach: Try every combination of three numbers.

• Time: O(n^3) (very slow for large n)
• Space: O(1) (no extra data structures needed)

Optimized approach (sorting):

• Time: O(n \log n) due to sorting
• Space: O(1) if sorting in-place, otherwise O(n) if not

This is much faster and works well for large arrays.

Summary

The problem asks for the largest product of any three distinct numbers in an array. The key insight is to consider both the largest three numbers and the combination of the two smallest (possibly negative) numbers with the largest number. Sorting the array allows us to easily pick out these candidates and compare their products. This approach is efficient, elegant, and robust against arrays with both positive and negative numbers.