Jobs

Interviews

Discussions

Maximum Product of Three Numbers

Easy

Intuit

2 views

Topics:

ArraysGreedy Algorithms

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

Example 1:

Input: nums = [1,2,3]
Output: 6

Example 2:

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

Example 3:

Input: nums = [-1,-2,-3]
Output: -6

Constraints:

3 <= nums.length <= 10⁴
-1000 <= nums[i] <= 1000

Maximum Product of Three Numbers

Easy

Intuit

2 views

Topics:

ArraysGreedy Algorithms

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

Example 1:

Input: nums = [1,2,3]
Output: 6

Example 2:

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

Example 3:

Input: nums = [-1,-2,-3]
Output: -6

Constraints:

3 <= nums.length <= 10⁴
-1000 <= nums[i] <= 1000

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers within the input array `nums`?
Can the input array `nums` contain negative numbers or zero?
What is the expected size of the input array `nums`? Should I be concerned about potential memory constraints or integer overflow?
Are duplicate numbers allowed in the array, and if so, how might they impact the maximum product?
Is the input array guaranteed to have at least three numbers?

Brute Force Solution

Approach

The goal is to find three numbers in a list that, when multiplied together, give the biggest possible result. The brute force method involves simply checking every single combination of three numbers from the list.

Here's how the algorithm would work step-by-step:

Take the first number from the list.
Combine it with every possible pair of the remaining numbers in the list.
Multiply these three numbers together.
Remember this product.
Repeat this process, starting with the second number in the original list, and pairing it with every possible combination of two other numbers.
Continue until you've tried every possible group of three numbers from the list.
Compare all the products you remembered, and find the largest one.

Code Implementation

def maximum_product_of_three_numbers_brute_force(numbers):
    list_length = len(numbers)
    if list_length < 3:
        return None

    maximum_product = float('-inf')

    for first_number_index in range(list_length):
        # Iterate through all possible first numbers

        for second_number_index in range(first_number_index + 1, list_length):

            for third_number_index in range(second_number_index + 1, list_length):
                # Ensure unique triplets
                product = numbers[first_number_index] * numbers[second_number_index] * numbers[third_number_index]

                # Keep track of the largest product seen so far
                if product > maximum_product:
                    maximum_product = product

    return maximum_product

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n³) – The provided solution iterates through each number in the input list of size n. For each number, it combines it with every possible pair of the remaining numbers. Selecting a pair from the remaining numbers takes O(n²) time. Since this pairing process is performed for each of the n elements in the input, the overall time complexity becomes O(n * n²), which simplifies to O(n³). Therefore, the dominant factor is the triple nested loop inherent in choosing every possible combination of three numbers.

Space Complexity

O(1) – The brute force approach, as described, only remembers the maximum product found so far. This requires a single variable to store the current maximum product and potentially a few loop counters, all of which consume a constant amount of extra memory regardless of the input list's size, N. No auxiliary data structures like arrays or hash maps are created to store intermediate results or combinations. Therefore, the space complexity is constant, or O(1).

Optimal Solution

Approach

To find the largest product of three numbers, we don't need to check every combination. The key is to realize that the largest product will either come from the three largest numbers or from the two smallest (most negative) numbers multiplied by the largest number. We just need to keep track of these potential candidates.

Here's how the algorithm would work step-by-step:

Find the three largest numbers in the set.
Find the two smallest (most negative) numbers in the set.
Calculate the product of the three largest numbers.
Calculate the product of the two smallest numbers and the largest number.
Compare these two products and choose the larger one. That's the maximum product of three numbers from the set.

Code Implementation

def maximum_product_of_three_numbers(numbers):
    numbers.sort()

    # Get the three largest numbers.
    largest_number_1 = numbers[-1]
    largest_number_2 = numbers[-2]
    largest_number_3 = numbers[-3]

    # Get the two smallest numbers.
    smallest_number_1 = numbers[0]
    smallest_number_2 = numbers[1]

    # Calculate product of three largest numbers.
    product_of_largest_numbers = largest_number_1 * largest_number_2 * largest_number_3

    # Calculate product of two smallest and one largest.
    product_of_smallest_with_largest = smallest_number_1 * smallest_number_2 * largest_number_1

    # Return the larger of the two products
    return max(product_of_largest_numbers, product_of_smallest_with_largest)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves finding the three largest and two smallest numbers in the input array of size n. This can be done in O(n) time by iterating through the array and keeping track of the current largest and smallest values. Calculating the products then involves constant time operations. Therefore, the overall time complexity is dominated by the initial scan of the array, resulting in O(n).

Space Complexity

O(1) – The algorithm requires storing a fixed number of variables to keep track of the three largest and two smallest numbers. These variables (e.g., max1, max2, max3, min1, min2) consume constant space, regardless of the input array's size, N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return null or throw an IllegalArgumentException, as no product can be computed.
Array with fewer than 3 elements	Return null or throw an IllegalArgumentException, since three numbers are required for the product.
Array contains only positive numbers	The largest three numbers should be multiplied to get the maximum product.
Array contains only negative numbers	The largest three (least negative) numbers should be multiplied to get the maximum product.
Array contains a mix of positive, negative, and zero numbers	Consider both the product of the three largest numbers and the product of the two smallest (most negative) numbers and the largest number, returning the greater of the two.
Array contains duplicate numbers	The algorithm should handle duplicate numbers correctly without any special adjustments.
Integer overflow during product calculation	Use long data type to store the product to prevent potential overflow issues.
Array contains MAX_INT/MIN_INT	Carefully choose the correct three elements to multiply such that the result is maximized without overflowing.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers within the input array `nums`?
Can the input array `nums` contain negative numbers or zero?
What is the expected size of the input array `nums`? Should I be concerned about potential memory constraints or integer overflow?
Are duplicate numbers allowed in the array, and if so, how might they impact the maximum product?
Is the input array guaranteed to have at least three numbers?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number from the list.
Combine it with every possible pair of the remaining numbers in the list.
Multiply these three numbers together.
Remember this product.
Repeat this process, starting with the second number in the original list, and pairing it with every possible combination of two other numbers.
Continue until you've tried every possible group of three numbers from the list.
Compare all the products you remembered, and find the largest one.

Code Implementation

def maximum_product_of_three_numbers_brute_force(numbers):
    list_length = len(numbers)
    if list_length < 3:
        return None

    maximum_product = float('-inf')

    for first_number_index in range(list_length):
        # Iterate through all possible first numbers

        for second_number_index in range(first_number_index + 1, list_length):

            for third_number_index in range(second_number_index + 1, list_length):
                # Ensure unique triplets
                product = numbers[first_number_index] * numbers[second_number_index] * numbers[third_number_index]

                # Keep track of the largest product seen so far
                if product > maximum_product:
                    maximum_product = product

    return maximum_product

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Find the three largest numbers in the set.
Find the two smallest (most negative) numbers in the set.
Calculate the product of the three largest numbers.
Calculate the product of the two smallest numbers and the largest number.
Compare these two products and choose the larger one. That's the maximum product of three numbers from the set.

Code Implementation

def maximum_product_of_three_numbers(numbers):
    numbers.sort()

    # Get the three largest numbers.
    largest_number_1 = numbers[-1]
    largest_number_2 = numbers[-2]
    largest_number_3 = numbers[-3]

    # Get the two smallest numbers.
    smallest_number_1 = numbers[0]
    smallest_number_2 = numbers[1]

    # Calculate product of three largest numbers.
    product_of_largest_numbers = largest_number_1 * largest_number_2 * largest_number_3

    # Calculate product of two smallest and one largest.
    product_of_smallest_with_largest = smallest_number_1 * smallest_number_2 * largest_number_1

    # Return the larger of the two products
    return max(product_of_largest_numbers, product_of_smallest_with_largest)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return null or throw an IllegalArgumentException, as no product can be computed.
Array with fewer than 3 elements	Return null or throw an IllegalArgumentException, since three numbers are required for the product.
Array contains only positive numbers	The largest three numbers should be multiplied to get the maximum product.
Array contains only negative numbers	The largest three (least negative) numbers should be multiplied to get the maximum product.
Array contains a mix of positive, negative, and zero numbers	Consider both the product of the three largest numbers and the product of the two smallest (most negative) numbers and the largest number, returning the greater of the two.
Array contains duplicate numbers	The algorithm should handle duplicate numbers correctly without any special adjustments.
Integer overflow during product calculation	Use long data type to store the product to prevent potential overflow issues.
Array contains MAX_INT/MIN_INT	Carefully choose the correct three elements to multiply such that the result is maximized without overflowing.