Scale Engineer

Maximum Product of Three Numbers

Easy
#0582Time: 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: O(1), as we only use a few variables to store the maximum product and loop indices, regardless of the input size.7 companies
Patterns
Math
Algorithms
Sorting
Data structures
Array
Companies
FreshWorksInfosysIntuitNutanix

Prompt

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 <= 104
  • -1000 <= nums[i] <= 1000

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1), as we only use a few variables to store the maximum product and loop indices, regardless of the input size.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem