Maximum Product of Three Numbers LeetCode Solution

Difficulty Level Easy
Frequently asked in Amazon Apple ByteDance Citadel Facebook Google Intuit Microsoft Salesforce Splunk Uber
RedfinViews 225

Problem Statement

Maximum Product of Three Numbers LeetCode Solution – We are given an array, the question asks us to calculate the maximum product of any 3 numbers.

Examples

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

Approach

If all the numbers are greater than 0, then the maximum product of 3 numbers will obviously be the product of the largest 3 numbers. The problem arises in the case of negative numbers.

Let us observe some cases first and then think about the solution. For these cases, let us assume the nums sorted in non-decreasing order.

Case 1:

nums = [2, 3, 4, 7, 9, 100]

output = 7 *9 *100

Explanation: 3 max numbers are 100, 9 & 7

Case 2:

nums = [-13, -12, -1, 0, 1, 3, 14, 16, 17]

output = 14 *16 *17

Explanation: 3 max numbers are 17, 16 & 14

Case 3:

nums = [-13, -12, -11, -1, 0, 2, 3, 4, 5]

output = -13*(-12)*5

Explanation: even though the max numbers 3, 4 & 5, we can generate a much larger positive product from two negative numbers, in this case (-13)(-12) > 4 *5. After including the 2 negative numbers, we can not include any negative numbers as it will make the product negative hence small. Therefore, we have to include the 3rd number as the largest positive only.

In a sorted array, the maximum product will be either the last three largest elements or the first two (negative elements) multiplied by the last (largest) element.

Code

C++ code for Maximum Product of Three Numbers

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

Java code for Maximum Product of Three Numbers

public class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int option1 = nums[0] * nums[1] * nums[nums.length - 1];
        int option2 = nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];
        return Math.max(option1, option2);
    }
}

Complexity Analysis for Maximum Product of Three Numbers LeetCode Solution

Reference: https://en.wikipedia.org/wiki/Array_data_structure

Translate »