628. Maximum Product of Three Numbers

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

Solutions

Solution 1: Sorting + Case Analysis

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}\).

Python3JavaC++GoTypeScript

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)

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);
    }
}

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);
    }
};

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
}

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

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)\).

Python3JavaC++GoTypeScript

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])

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);
    }
}

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);
    }
};

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)
}

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