Skip to content

628. Maximum Product of Three Numbers

Description

You are 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

Explanation:

The only three numbers are 1, 2, and 3, so the maximum product is 1 * 2 * 3 = 6.

Example 2:

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

Output: 24

Explanation:

The largest product comes from the three greatest numbers: 2 * 3 * 4 = 24.

Example 3:

Input: nums = [-1,-2,-3]

Output: -6

Explanation:

The only three numbers are -1, -2, and -3, so the maximum product is (-1) * (-2) * (-3) = -6.

 

Constraints:

  • 3 <= nums.length <= 104
  • -1000 <= nums[i] <= 1000

Solutions

Solution 1: Sorting + Case Analysis

Thinking

The maximum product of three numbers is either the three largest values or the two smallest (possibly negative) times the largest. Sorting is cheap for \(n\le 10^4\).

After sorting, compare \(nums[-1]\times nums[-2]\times nums[-3]\) with \(nums[-1]\times nums[0]\times nums[1]\).

First, we sort the array \(\textit{nums}\), and then discuss two cases:

  • If \(\textit{nums}\) contains all non-negative or all non-positive numbers, the answer is the product of the last three numbers, i.e., \(\textit{nums}[n-1] \times \textit{nums}[n-2] \times \textit{nums}[n-3]\);
  • If \(\textit{nums}\) contains both positive and negative numbers, the answer could be the product of the two smallest negative numbers and the largest positive number, i.e., \(\textit{nums}[n-1] \times \textit{nums}[0] \times \textit{nums}[1]\), or the product of the last three numbers, i.e., \(\textit{nums}[n-1] \times \textit{nums}[n-2] \times \textit{nums}[n-3]\).

Finally, return the maximum of the two cases.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
5
6
class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        a = nums[-1] * nums[-2] * nums[-3]
        b = nums[-1] * nums[0] * nums[1]
        return max(a, b)

1
2
3
4
5
6
7
8
9
class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int a = nums[n - 1] * nums[n - 2] * nums[n - 3];
        int b = nums[n - 1] * nums[0] * nums[1];
        return Math.max(a, b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int a = nums[n - 1] * nums[n - 2] * nums[n - 3];
        int b = nums[n - 1] * nums[0] * nums[1];
        return max(a, b);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func maximumProduct(nums []int) int {
    sort.Ints(nums)
    n := len(nums)
    a := nums[n-1] * nums[n-2] * nums[n-3]
    b := nums[n-1] * nums[0] * nums[1]
    if a > b {
        return a
    }
    return b
}

1
2
3
4
5
6
7
function maximumProduct(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const a = nums[n - 1] * nums[n - 2] * nums[n - 3];
    const b = nums[n - 1] * nums[0] * nums[1];
    return Math.max(a, b);
}

Solution 2: Single Pass

Thinking

Sorting is more than we need: only the two smallest and three largest values matter. A linear pass (or nlargest) keeps those five extrema.

We can avoid sorting the array by maintaining five variables: \(\textit{mi1}\) and \(\textit{mi2}\) represent the two smallest numbers in the array, while \(\textit{mx1}\), \(\textit{mx2}\), and \(\textit{mx3}\) represent the three largest numbers in the array.

Finally, return \(\max(\textit{mi1} \times \textit{mi2} \times \textit{mx1}, \textit{mx1} \times \textit{mx2} \times \textit{mx3})\).

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

1
2
3
4
5
class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        top3 = nlargest(3, nums)
        bottom2 = nlargest(2, nums, key=lambda x: -x)
        return max(top3[0] * top3[1] * top3[2], top3[0] * bottom2[0] * bottom2[1])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        const 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 max(mi1 * mi2 * mx1, mx1 * mx2 * mx3);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func maximumProduct(nums []int) int {
    const inf = 1 << 30
    mi1, mi2 := inf, inf
    mx1, mx2, mx3 := -inf, -inf, -inf
    for _, x := range nums {
        if x < mi1 {
            mi1, mi2 = x, mi1
        } else if x < mi2 {
            mi2 = x
        }
        if x > mx1 {
            mx1, mx2, mx3 = x, mx1, mx2
        } else if x > mx2 {
            mx2, mx3 = x, mx2
        } else if x > mx3 {
            mx3 = x
        }
    }
    return max(mi1*mi2*mx1, mx1*mx2*mx3)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function maximumProduct(nums: number[]): number {
    const inf = 1 << 30;
    let mi1 = inf,
        mi2 = inf;
    let mx1 = -inf,
        mx2 = -inf,
        mx3 = -inf;
    for (const x of 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);
}

Comments