We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Product of Three Numbers

Number: 628

Difficulty: Easy

Paid? No

Companies: Salesforce, Amazon, Apple, Nutanix, TikTok, Accenture, tcs, Siemens, Bloomberg, Microsoft, Uber, Adobe, Intuit

Problem Description

Given an integer array nums, the task is to find three numbers in the array whose product is maximum and return that maximum product.

Key Insights

  • The maximum product can be obtained either by multiplying the three largest numbers or by multiplying the two smallest (which can be negative) and the largest number.
  • Sorting the array can quickly give access to these candidate numbers.
  • A careful consideration of negative numbers is required as two negatives make a positive.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting (or O(n) if using a linear scan strategy)
Space Complexity: O(1), ignoring the space used by the sorting algorithm if done in-place

Solution

The solution involves determining the maximum product by considering two cases:

  1. The product of the three largest numbers in the sorted array.
  2. The product of the two smallest numbers (which could be negative) and the largest number.

Steps:

  • Sort the array.
  • Compute the product of the last three elements (largest three).
  • Compute the product of the first two elements (smallest) and the last element (largest).
  • Return the maximum of these two products.

Data Structures:

  • Array: The input is processed as an array.

Algorithm:

  • Sorting gives a straightforward method to access the smallest and largest values.

Gotchas:

  • Negative numbers might yield a larger product when paired appropriately.
  • It is critical to ensure that the array has at least three elements as per the constraints.

Code Solutions

# Python solution

def maximumProduct(nums):
    # Sort the array to easily access smallest and largest numbers
    nums.sort()  
    # Calculate product of three largest numbers
    product1 = nums[-1] * nums[-2] * nums[-3]
    # Calculate product of two smallest numbers and the largest number
    product2 = nums[0] * nums[1] * nums[-1]
    # Return the maximum of the two calculated products
    return max(product1, product2)

# Example usage:
# result = maximumProduct([1,2,3,4])
# print(result)  # Expected output: 24
← Back to All Questions