Leetcode – Maximum Product of Three Numbers Solution in Python

Spread the love

Introduction

In this article, we will explore a classic problem from Leetcode known as “Maximum Product of Three Numbers”. This problem tests our understanding of array manipulation, mathematical properties, and algorithm optimization. We will discuss the problem statement, explore multiple approaches to solve it, and analyze their complexity.

Problem Statement (Leetcode #628)

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example:

Input: [1,2,3,4] Output: 24

Note:

The length of the given array will be in range [3, 10^4] and all elements are in the range [-10^3, 10^3].

Solution Approaches

1. Brute Force Approach

The most straightforward approach is to check the product of every possible triplet in the array.

Algorithm:

  1. Iterate through each element, a, in the array.
  2. For each a, iterate through each element, b, after a.
  3. For each pair a and b, iterate through each element, c, after b.
  4. For each triplet a, b, and c, calculate their product and keep track of the maximum product.
def maximum_product(nums):
    max_product = float('-inf')
    n = len(nums)
    
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                max_product = max(max_product, nums[i] * nums[j] * nums[k])
                
    return max_product

Time Complexity:

  • O(n^3), as there are three nested loops iterating through the array.

Space Complexity:

  • O(1), as we are only using a constant amount of extra space.

2. Sorting Approach

An optimized approach involves sorting the array. Once the array is sorted, the maximum product can be the product of the last three elements (in case they are all positive or all negative) or the product of the first two elements and the last element (in case the first two elements are negative).

Algorithm:

  1. Sort the array.
  2. Calculate the product of the last three elements.
  3. Calculate the product of the first two elements and the last element.
  4. Return the maximum of the two products.
def maximum_product(nums):
    nums.sort()
    
    return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])

Time Complexity:

  • O(n log n), as the most time-consuming operation is sorting the array.

Space Complexity:

  • O(1), as we are using a constant amount of extra space.

3. Linear Scan Approach

We can optimize the solution further by realizing that we only need the three largest numbers and the two smallest numbers. We can find these five numbers in a single linear scan.

Algorithm:

  1. Initialize variables to keep track of the three largest numbers (max1, max2, max3) and the two smallest numbers (min1, min2).
  2. Iterate through each element in the array, updating the maximum and minimum values.
  3. Return the maximum between the product of the three largest numbers and the product of the two smallest numbers and the largest number.
def maximum_product(nums):
    max1 = max2 = max3 = float('-inf')
    min1 = min2 = float('inf')
    
    for num in nums:
        if num > max1:
            max3, max2, max1 = max2, max1, num
        elif num > max2:
            max3, max2 = max2, num
        elif num > max3:
            max3 = num
            
        if num < min1:
            min2, min1 = min1, num
        elif num < min2:
            min2 = num
            
    return max(max1 * max2 * max3, max1 * min1 * min2)

Time Complexity:

  • O(n), as we are iterating through the array once.

Space Complexity:

  • O(1), as we are using a constant amount of extra space.

Conclusion

In this article, we delved into the “Maximum Product of Three Numbers” problem on LeetCode and examined three different solutions in Python. The brute-force approach, though simple, is inefficient. By understanding the mathematical properties of the problem, we improved the performance using sorting. Finally, we achieved the most optimized solution through a single linear scan.

Leave a Reply