Find Maximum Product of Three Numbers

Title: Find Maximum Product of Three Numbers

Given an array of integers, you need to find three numbers whose product is the largest possible. This sounds straightforward until you remember that two negative numbers multiply into a positive one, which means the answer isn’t always the three biggest values in the array. In this guide, you’ll learn how to solve this classic array problem in a single pass, trace through the algorithm on a concrete example, and walk through the edge cases that interviewers love to probe.

We’ll start by understanding why sorting alone isn’t quite enough, then build an efficient O(n) Java solution that tracks the three largest and two smallest numbers as it scans the array once.

Understanding the Problem

The problem gives you an array numbers of at least three integers and asks for the maximum value obtainable by multiplying any three elements together. A naive approach checks every triplet, which costs O(n^3) time. Sorting the array first narrows this down to two candidates: the product of the three largest numbers, or the product of the two smallest numbers (which may both be negative) with the single largest number. The final answer is whichever of these two products is bigger.

Typical constraints state the array length is between 3 and 10^4, and each element fits within the standard 32-bit int range, which is why overflow deserves attention in the Additional Considerations section below.

Approach to Solve the Problem

1. Validate that numbers is not null and contains at least three elements, otherwise throw IllegalArgumentException.
2. Initialize three variables max1, max2, max3 to Integer.MIN_VALUE to track the three largest numbers seen so far.
3. Initialize two variables min1, min2 to Integer.MAX_VALUE to track the two smallest numbers seen so far.
4. Scan the array once. For each number, update max1, max2, max3 if it is larger than any of them, shifting the smaller ones down.
5. In the same pass, update min1, min2 if the number is smaller than either of them.
6. After the scan, compute two candidate products: max1 * max2 * max3 and min1 * min2 * max1.
7. Return the larger of the two candidate products as the final answer.

Java Program

public class MaximumProductOfThree {

    public static int maxProductOfThree(int[] numbers) {
        if (numbers == null || numbers.length < 3) {
            throw new IllegalArgumentException("Array must contain at least three elements");
        }

        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;

        for (int num : numbers) {
            if (num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                max3 = num;
            }

            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }

        int productOfThreeLargest = max1 * max2 * max3;
        int productOfTwoSmallestAndLargest = min1 * min2 * max1;

        return Math.max(productOfThreeLargest, productOfTwoSmallestAndLargest);
    }

    public static void main(String[] args) {
        int[] numbers = {-10, -10, 1, 3, 2};
        System.out.println("Maximum product of three numbers: " + maxProductOfThree(numbers));
    }
}

Explanation of the Program

The method maxProductOfThree begins with a guard clause that rejects null arrays and arrays with fewer than three elements, since no valid triplet exists in that case.

Inside the single for loop, each number is compared against the current top three maximums. If it beats max1, the old max1 and max2 shift down into max2 and max3. The same shifting logic applies when a number only beats max2 or max3.

The same loop iteration also checks the number against the two smallest values tracked so far, shifting min1 into min2 when a new smallest value appears.

Once the loop finishes, max1, max2, max3 hold the three largest numbers in the array and min1, min2 hold the two smallest. The method compares productOfThreeLargest against productOfTwoSmallestAndLargest and returns whichever is bigger with Math.max.

Step-by-Step Trace

Consider the input [-7, -3, 2, 4, 5], where the expected output is 105 (from -7 * -3 * 5).

At the end of each iteration, max1, max2, max3 hold the three largest numbers seen so far in descending order, and min1, min2 hold the two smallest numbers seen so far in ascending order.

Examples

Example 1: All Positive Numbers

int[] numbers = {1, 2, 3, 4};
// maxProductOfThree(numbers) -> 24 (4 * 3 * 2)
System.out.println(maxProductOfThree(numbers));

Example 2: Negative Numbers Present

int[] numbers = {-10, -10, 1, 3, 2};
// maxProductOfThree(numbers) -> 300 (-10 * -10 * 3)
System.out.println(maxProductOfThree(numbers));

Example 3: Array Containing Zero

int[] numbers = {-3, -2, 0, 2, 3};
// maxProductOfThree(numbers) -> 18 (-3 * -2 * 3)
System.out.println(maxProductOfThree(numbers));

Common Mistakes to Avoid

A few mistakes show up again and again when solving this problem, often because the negative-number case gets overlooked.

• Only multiplying the three largest numbers – returns the wrong answer on arrays like {-10, -10, 1, 3, 2}, where two large negative numbers multiplied by the largest positive number (300) beats the product of the three largest numbers (6). Always compare both candidate products and return the larger one.
• Initializing max1, max2, max3 to 0 – fails on arrays containing only negative numbers because 0 is wrongly treated as one of the three largest values. Initialize them to Integer.MIN_VALUE instead.
• Forgetting the array-length check – calling the method on an array with fewer than three elements, such as {1, 2}, silently returns a meaningless product instead of signaling that the input is invalid. Throw an IllegalArgumentException when numbers.length < 3.
• Letting the multiplication overflow - multiplying three numbers close to Integer.MAX_VALUE wraps around to a negative int and silently produces an incorrect result. Widen the intermediate product to long when the input range is not guaranteed to be small.

Edge Cases to Test

Walking through these boundary inputs out loud is exactly what an interviewer wants to see before you start coding.

• Fewer than three elements
• All negative numbers
• Two large negative numbers with one large positive number
• Array containing zero
• Duplicate values at the sorting boundary
• All identical elements
• Integer.MIN_VALUE / Integer.MAX_VALUE present
• Null array reference

Additional Considerations

The single-pass solution runs in O(n) time, since it scans the array exactly once and performs a constant amount of work per element.

It uses O(1) extra space, five int variables regardless of the input size, which makes it preferable to sorting-based solutions that need O(n log n) time even though they also use O(1) extra space when sorting in place.

The trade-off is readability. The sorting approach (Arrays.sort(numbers) followed by comparing the two candidate products) is easier to explain in an interview, while the single-pass version is the better answer when asked to optimize further.

Interview Follow-up Questions

Once you've nailed the base solution, expect an interviewer to push further with questions like these.

• What if the array is already sorted? - you can skip the tracking variables entirely and just compare numbers[n-1] * numbers[n-2] * numbers[n-3] against numbers[0] * numbers[1] * numbers[n-1].
• What if you need the maximum product of K numbers instead of three? - generalize by tracking the K largest and considering how many of the smallest (possibly negative) values to pair with them; the comparison space grows but the core idea stays the same.
• What if the input arrives as a stream of unknown length? - keep only the running max1, max2, max3, min1, min2 in memory and update them per element, since the algorithm never needs to revisit the full array.
• What if the input array is read-only and you cannot use extra arrays? - the single-pass version already satisfies this, since it only ever reads each element once and stores state in five scalar variables, never allocating or mutating the input.

Conclusion

Finding the maximum product of three numbers looks like a sorting problem at first glance, but the real insight is remembering that two negative numbers can multiply into a large positive one. Once you track both the three largest and two smallest values, a single pass through the array is all you need.

Try adapting the same two-candidate-product idea to find the maximum product of four numbers, or to handle inputs where overflow is a real concern. You can learn more about array-based interview problems on the Arrays category page.