Maximum Product Of Three Numbers

Difficulty: Medium

Asked in: Amazon

Understanding the Problem

Given an integer array nums[], write a program to find three numbers from the array whose product is maximum and output the result.

Problem Note

• The array contains both +ve and -ve numbers.
• The elements on the array can be non-contiguous.

Example 1

Input: nums[] = [-5, -7, 4, 2, 1, 9]
Output: 315
Explanation: Max Product of 3 numbers = -5 * -7 * 9 = 315

Example 2

Input: nums[]= [4, 5, -19, 3]
Output: 60
Explanation: Max Product of 3 numbers = 4 * 5 * 3 = 60

Solutions

We will be discussing three different solutions for this problem

1. Brute Force Approach: Try to find all the triplets in the array while maintaining the maximum value of their products.
2. Using sorting: Sort the input array. The maximum product would be the product of the last three elements or the starting two elements with the last element.
3. Single scan: Create 5 variables to maintain the largest, second-largest, third-largest, smallest, and second smallest. The combination of three would be the maximum product.

You may try to solve this problem here Maximum Product of Three Numbers. Learning via problem-solving is the best way to crack any coding interview. So, just visit the link and try to solve using the above methods. If stuck, then you can find the solution below.

1. Brute Force Approach

To find the maximum product of three numbers, we can find all the triplets of the array and multiply them to get the maximum result.

Solution steps

1. Create a variable maxProduct and initialize it with INT_MIN
2. Find all the triplets of the array, multiply them and update

• maxProduct with max(maxProduct, product(triplet))

Pseudo Code

int maximumProduct(int[] nums) {
    n = nums.size
    maxProduct = INT_MIN
    for(int i = 0 to i < n-2) {
        for(int j = i + 1 to j < n-1) {
            for(int k = j + 1 to k < n) {
                tripletProduct = nums[i] * nums[j] * nums[k]
                maxProduct = max(maxProduct, tripletProduct)
            }
        }
    }
    return maxProduct
}

Complexity Analysis

Time Complexity: O(n³)

Space Complexity: O(1)

Critical Ideas to Think

• Why did we initialize maxProduct with INT_MIN?
• Is it necessary to find all the triplets to find the maximum product?
• Can you think of a more optimal approach?

2. Using Sorting

If you will think for a second, you may realize that the maximum product of any three numbers would be the product of the greatest three numbers or the smallest two numbers with the greatest number from the nums array.

The reason why the maximum product of any triplet could have two smallest numbers because there could be negative numbers in the nums array and the product of the two smallest numbers could be largely positive if the numbers are greater than the 2nd and 3rd largest number of the array.

So if we will sort the array in ascending order, then the largest three numbers will be available at the end of the array. Also, the smallest two numbers will be available at the beginning of the array.

Solution Step

1. Sort the nums array in ascending order
2. Create a maxProduct variable and initialize it with INT_MIN.
3. Update the maxProduct with

• max(maxProduct, nums[0]*nums[1]*nums[n-1])
• max(maxProduct, nums[n-1]*nums[n-2]*nums[n-3])

Pseudo Code

int maximumProduct(int[] nums) {
    n = nums.size
    maxProduct = INT_MIN
    sort(nums)
    maxProduct = max(maxProduct, nums[0]*nums[1]*nums[n-1))
    maxProduct = max(maxProduct, nums[n-3]*nums[n-2]*nums[n-1))
    return maxProduct
}

Complexity Analysis

Time Complexity: O(n log n), due to sorting.

Space Complexity: O(log n), Sorting stack space using merge sort or quicksort.

Critical Ideas To Think

• Why did we only check for the product of the last three elements for maxProduct?
• How can the smallest two values participate for maxProduct?(comment down below)

3. In Single Scan

If you have understood the second approach, then by this time you would have realized that only the three maximum values and two smallest values participate in finding the maximum product of three numbers in the nums array.

So, we can find the largest three values and the smallest two values of the array in a single pass of the nums array by using five variables.

Solution Step

• Create 5 variables to store the largest three integers and the smallest two integers of the nums array.
• Initialize three of them INT_MIN that be used to store the maximum three values of the array.
• Initialize the rest two with INT_MAX, that can be used to store the minimum two values of the array.
• In a single pass, maintain all the five variables such that at the end, they would have stored maximum, 2nd maximum, 3rd maximum, minimum, 2nd minimum.

Pseudo Code

int maximumProduct(int[] nums) {
    min1 = INT_MAX
    min2 = INT_MAX
    max1 = INT_MIN
    max2 = INT_MIN
    max3 = INT_MIN
    for (int i = 0 to i < nums.size) {
        if (nums[i] <= min1) {
            min2 = min1
            min1 = nums[i]
        } else if (nums[i] <= min2) {     // n lies between min1 and min2
            min2 = nums[i]
        }
        if (nums[i] >= max1) {            // n is greater than max1, max2 and max3
            max3 = max2
            max2 = max1
            max1 = nums[i]
        } else if (nums[i] >= max2) {     // n lies betweeen max1 and max2
            max3 = max2
            max2 = nums[i]
        } else if (nums[i] >= max3) {     // n lies betwen max2 and max3
            max3 = nums[i]
        }
    }
    return max(min1 * min2 * max1, max1 * max2 * max3)
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Critical Ideas to Think

• Why did we maintain five variables?
• Can you track that how does the maximum three have been maintained in a single pass?

Comparison of Approaches

Suggested Problems to Solve

• Maximum product of subsequence of size K
• Find Maximum XOR value of a sub-array of size K
• Largest triplet product in a stream
• Maximum Product Quadruple in an array

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

Happy Coding! Enjoy Algorithms!