Maximum Product of Three Numbers

Problem

Given an integer array, find three numbers whose product is maximum and output the maximum product. Note:

• The array can have negative numbers
• The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
• Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

Solution

Sorting Solution: O(nlgn) time and O(1) space

public class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        return nums[len - 1] * Math.max(nums[len - 2] * nums[len - 3], nums[0] * nums[1]);
    }
}

Single Scanning Solution: O(n) time and O(1) space

public class Solution {
    public int maximumProduct(int[] nums) {
        int max1 = Integer.MIN_VALUE, max2 = max1, max3 = max1;
        int min1 = Integer.MAX_VALUE, min2 = min1;
        for (int num : nums) {
            if (num <= min1) {
                min2 = min1;
                min1 = num;
            } else if (num <= min2) min2 = num;

            if (num >= max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num >= max2) {
                max3 = max2;
                max2 = num;
            } else if (num >= max3) max3 = num;
        }
        return max1 * Math.max(max2 * max3, min1 * min2);
    }
}

Analysis

The tricky part of this problem is that there might be negative number in the given array
However, in any case the product must contain the max number in array
For example, if max is negative, then the result must be negative, so after getting a product of two negative numbers, we need to multiply a number whose absolute value is minimum, which will be the max
If max is positive, then we need to get a maximum product of previous two numbers and multiply the max
Therefore, the problem becomes finding the max product of two numbers except the max
If we sort the array, it has to be the first two or last two numbers (except the max)
Or we don't have to sort the array, just find the max and two other max and two other min numbers ;)