Maximum Product of Three Numbers

EASY

Description

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

Approaches

Checkout 3 different approaches to solve Maximum Product of Three Numbers. Click on different approaches to view the approach and algorithm in detail.

Brute Force

This approach involves checking every possible combination of three numbers from the array. We use three nested loops to select three distinct numbers, calculate their product, and keep track of the maximum product found so far.

Algorithm

Initialize a variable maxProduct to Integer.MIN_VALUE.
Use a loop to iterate from i = 0 to n-3.
Inside this loop, use a nested loop to iterate from j = i + 1 to n-2.
Inside the second loop, use a third nested loop to iterate from k = j + 1 to n-1.
Calculate the product of nums[i], nums[j], and nums[k].
Compare this product with maxProduct and update maxProduct if the current product is greater.
After the loops complete, return maxProduct.

The simplest way to solve the problem is to iterate through all unique triplets (i, j, k) where i < j < k. For each triplet, we calculate the product nums[i] * nums[j] * nums[k]. We maintain a variable, maxProduct, initialized to the smallest possible value, and update it with the current product if the current product is larger. After checking all possible triplets, maxProduct will hold the result.

class Solution {
    public int maximumProduct(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            // This case is not possible based on constraints.
            return 0; 
        }
        
        int maxProduct = Integer.MIN_VALUE;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    int currentProduct = nums[i] * nums[j] * nums[k];
                    if (currentProduct > maxProduct) {
                        maxProduct = currentProduct;
                    }
                }
            }
        }
        return maxProduct;
    }
}

Complexity Analysis

Time Complexity: O(n^3), where n is the number of elements in the `nums` array. This is because of the three nested loops, each iterating up to n times.Space Complexity: O(1), as we only use a few variables to store the maximum product and loop indices, regardless of the input size.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Very inefficient and will likely result in a 'Time Limit Exceeded' error for large inputs, as its complexity is cubic.

Code Solutions

Checking out 3 solutions in different languages for Maximum Product of Three Numbers. Click on different languages to view the code.

class Solution {
public
  int maximumProduct(int[] nums) {
    final int inf = 1 << 30;
    int mi1 = inf, mi2 = inf;
    int mx1 = -inf, mx2 = -inf, mx3 = -inf;
    for (int x : nums) {
      if (x < mi1) {
        mi2 = mi1;
        mi1 = x;
      } else if (x < mi2) {
        mi2 = x;
      }
      if (x > mx1) {
        mx3 = mx2;
        mx2 = mx1;
        mx1 = x;
      } else if (x > mx2) {
        mx3 = mx2;
        mx2 = x;
      } else if (x > mx3) {
        mx3 = x;
      }
    }
    return Math.max(mi1 * mi2 * mx1, mx1 * mx2 * mx3);
  }
}

Video Solution

Watch the video walkthrough for Maximum Product of Three Numbers

Algorithms:

Sorting

Patterns:

Math

Data Structures:

Array

Companies:

FreshWorks |Infosys |Intuit |Nutanix |