Maximum Product of Three Numbers

Easy
370.

Maximum Product of Three Numbers

Maximum Product of Three Numbers is an easy coding problem on arrays, math and sorting, asked in Amazon, Meta, Bloomberg and Intuit interviews.

Given an integer array nums, find three numbers whose product is maximum and return that product.

Example 1

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

Example 2

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

Example 3

Input
nums = [-100,-98,-1,2,3,4]
Output
39200
Explanation
Two large negatives multiply to a large positive.

Constraints

  • 3 <= nums.length <= 40
  • -1000 <= nums[i] <= 1000
  • The answer fits in a signed 32-bit integer.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumProduct = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Product of Three Numbers — Problem & Solution

Maximum Product of Three Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Maximum Product of Three Numbers is an easy coding problem on arrays, math and sorting, asked in Amazon, Meta, Bloomberg and Intuit interviews.

  • Difficulty: Easy
  • Topics: Arrays, Math, Sorting
  • Asked at: Amazon, Meta, Bloomberg, Intuit
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer array nums, find three numbers whose product is maximum and return that product.

Example 1

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

Example 2

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

Example 3

Input: nums = [-100,-98,-1,2,3,4]
Output: 39200
Explanation: Two large negatives multiply to a large positive.

Constraints

  • 3 <= nums.length <= 40
  • -1000 <= nums[i] <= 1000
  • The answer fits in a signed 32-bit integer.

Hints for Maximum Product of Three Numbers

  1. Hint 1

    Sorting makes both candidates obvious.

  2. Hint 2

    Either the three largest values win, or the two most negative values pair with the single largest.

  3. Hint 3

    Take the maximum of those two products — nothing else can beat them.

How to solve Maximum Product of Three Numbers

Either the three largest values or the two most negative with the largest; take the bigger product.

Approach

  1. Sort.
  2. Return max(a[-1]·a[-2]·a[-3], a[0]·a[1]·a[-1]).

Why it works

A maximum product uses either zero or two negatives; with zero negatives the three largest win, with two negatives the most negative pair times the largest positive wins. No other combination can exceed both.

Complexity

  • Time — O(n log n)
  • Space — O(1) beyond the sort

Pitfalls

  • Tracking the top three and bottom two in one pass makes it O(n).

Reference solution

Python

def maximumProduct(nums) -> int:
    a = sorted(nums)
    return max(a[-1] * a[-2] * a[-3], a[0] * a[1] * a[-1])

Java

public static int maximumProduct(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int n = a.length;
    return Math.max(a[n - 1] * a[n - 2] * a[n - 3], a[0] * a[1] * a[n - 1]);
}

C++

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

JavaScript

var maximumProduct = function(nums) {
    const a = nums.slice().sort(function(x, y) { return x - y; });
    const n = a.length;
    const highThree = a[n - 1] * a[n - 2] * a[n - 3];
    const twoLow = a[0] * a[1] * a[n - 1];
    return Math.max(highThree, twoLow);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms