Solution For Maximum Product Of Three Numbers

Problem Statement:
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

Approach:
The solution is quite easy to implement. What we need to do is to look for the highest three numbers by value and the two lowest numbers by value (in case of negative numbers). Then we calculate two potential results:

1. using the three highest numbers
2. using one lower number and two higher numbers

Then we return the highest result obtained.

Solution:

First, we define our function maxProductThreeNumbers:

class Solution:
def maximumProduct(self, nums: List[int]) -> int:

    nums.sort(reverse=True)
    # Function to calculate max product of three numbers

    def maxProductThreeNumbers(n):
        return max(n[0]*n[1]*n[2], 
                   n[0]*n[-1]*n[-2])

    return maxProductThreeNumbers(nums)

Here we first sort the given array nums in descending order. Then, we define a function maxProductThreeNumbers that calculates the maximum product of three numbers in the given array. We then return the maximum product of the three numbers using the two different cases we discussed earlier.

Let’s understand how the above code works.

We first sort the given array nums in descending order which makes n[0] the highest number of the sorted array and n[-1] the lowest number of the sorted array.

We then define the function maxProductThreeNumbers that takes the sorted array n as an argument. Inside this function, we calculate two potential results:

The first potential result is the maximum product of three numbers which is simply n[0] * n[1] * n[2].

The second potential result is the maximum product of two highest numbers and the lowest number. We calculate this product as (n[0] * n[-1] * n[-2]). This is done in case we have negative numbers in the array and the product of two negative numbers yields a positive number which could be bigger than the product of the three highest numbers.

The max function is then used to return the maximum of the two potential results obtained above.

This way we are able to get the maximum product of three numbers in the given array nums.

Let’s test this code with our examples:

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

Solution:
We pass the input array into our function and get the maximum product of three numbers:

print(Solution().maximumProduct([1,2,3]))

output: 6

The output is as expected.

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

Solution:
We pass the input array into our function and get the maximum product of three numbers:

print(Solution().maximumProduct([1,2,3,4]))

output: 24

The output is as expected.

Step by Step Implementation For Maximum Product Of Three Numbers

class Solution {
    public int maximumProduct(int[] nums) {
        // sort the array in ascending order
        Arrays.sort(nums);
        
        // return the product of the last three numbers in the array
        return nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];
    }
}

def maximumProduct(nums):

# We can sort the array in ascending order and then take the product of the last three numbers 
# which will be the maximum product possible

nums.sort()

return nums[-1] * nums[-2] * nums[-3]

var maximumProduct = function(nums) {
    // we need to sort the array so that we can keep track of the largest and smallest values
    nums.sort((a, b) => a - b);
    // the largest product will be the product of the 3 largest values in the array
    // or the product of the largest value and the two smallest values
    const largest = nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];
    const smallest = nums[0] * nums[1] * nums[nums.length - 1];
    return Math.max(largest, smallest);
};

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

public int MaximumProduct(int[] nums) { // sort the array in ascending order Array.Sort(nums); // if the array only contains positive numbers, then the last 3 numbers will give the maximum product if (nums[0] >= 0) { return nums[nums.Length - 1] * nums[nums.Length - 2] * nums[nums.Length - 3]; } // if the array contains both positive and negative numbers, then we need to compare the product of the last 3 numbers // with the product of the first 2 numbers and the last number int product1 = nums[nums.Length - 1] * nums[nums.Length - 2] * nums[nums.Length - 3]; int product2 = nums[0] * nums[1] * nums[nums.Length - 1]; return Math.Max(product1, product2); }