Maximum Product of Three Numbers

Given an array of at least three integers, positive and negative, return the largest product of any three of them.

LeetCode: 628. Maximum Product of Three Numbers

Example

Text

Input:  [-5, -7, 4, 2, 1, 9]    Output: 315   (-5 × -7 × 9)
Input:  [4, 5, -19, 3]          Output: 60    (4 × 5 × 3)

The best product is one of two candidates:

the three largest values, or
the two smallest (most negative) values times the largest: two negatives make a positive.

Brute force: every triple

Java

public class Main {
    static long maxProduct(long[] nums) {
        int n = nums.length;
        long best = Long.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    best = Math.max(best, nums[i] * nums[j] * nums[k]);
                }
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxProduct(new long[]{-5, -7, 4, 2, 1, 9}) + " " + maxProduct(new long[]{4, 5, -19, 3}));
    }
}

Output

315 60

Time: O(n³). Space: O(1).

Better: sort

After sorting, both candidates can be read from the ends of the array.

Java

import java.util.Arrays;

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

    public static void main(String[] args) {
        System.out.println(maxProduct(new long[]{-5, -7, 4, 2, 1, 9}) + " " + maxProduct(new long[]{4, 5, -19, 3}));
    }
}

Output

315 60

Time: O(n log n). Space: O(n) for the copy. clone() copies the array so the caller's array is not reordered; Arrays.sort on a long[] sorts in place.

Optimal: one pass

Only five values matter: the three largest and the two smallest. Track them in one pass, shifting values down when a new one arrives. The starting values are Long.MIN_VALUE and Long.MAX_VALUE, so any input value replaces them.

Java

public class Main {
    static long maxProduct(long[] nums) {
        long max1 = Long.MIN_VALUE, max2 = Long.MIN_VALUE, max3 = Long.MIN_VALUE; // max1 >= max2 >= max3
        long min1 = Long.MAX_VALUE, min2 = Long.MAX_VALUE;                        // min1 <= min2
        for (long x : nums) {
            if (x > max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            } else if (x > max2) {
                max3 = max2;
                max2 = x;
            } else if (x > max3) {
                max3 = x;
            }
            if (x < min1) {
                min2 = min1;
                min1 = x;
            } else if (x < min2) {
                min2 = x;
            }
        }
        return Math.max(max1 * max2 * max3, min1 * min2 * max1);
    }

    public static void main(String[] args) {
        System.out.println(maxProduct(new long[]{-5, -7, 4, 2, 1, 9}) + " " + maxProduct(new long[]{4, 5, -19, 3}));
        System.out.println(maxProduct(new long[]{-1, -2, -3}) + " " + maxProduct(new long[]{-10, -10, 1, 3, 2}));
    }
}

Output

315 60
-6 300

Time: O(n). Space: O(1).

With exactly three numbers, the same values fill both groups, and both candidates are the product of all three, so the answer is correct even when it's negative.

Edge cases

All negative: the three largest (closest to zero) give the largest, least negative product: [-1, -2, -3] gives -6.
Zeros: handled like any other value; a 0 can be the best when the alternatives are negative.
Overflow: products of three int values can overflow int, and Java wraps silently, so the examples use long. Math.multiplyExact throws ArithmeticException instead of wrapping.