max-prod-three-nums.md

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:

Input: [1,2,3]
Output: 6

Example 2:

Input: [1,2,3,4]
Output: 24


Note:

    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.

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
28
29
30
31
32
33
34
35
3 * 2 = 3 + 3  OR 2 + 2 + 2

0 * num -> 0
1 * num -> num

big num * num2 * num3

num * -big num * -num

order of input not sorted

can we sort it?
yes

allows us to pick large positive numbers and small negative numbers

[-345, -23, 0, 0, 23, 245, 1000]


what about 2 numbers?
-345, -23 ?
245, 1000 ?

what if you have

[-345, -23, 0, 0, 1000] ?

[-345, 0, 0, , 1, 1000]


we need to avoid any zeroes?
but zero is larger than negative....so could be valid in some cases
ex: [-30, -20, 0 , 0, 4] - here 0 is biggest we can have? no... -30*-20*4 is

[1, 2, 100, 1000, 100000] --> in this case we only need to look at the end of array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int maximumProduct(vector<int>& nums) {
    if (nums.size() == 3) return (nums[0]*nums[1]*nums[2]);

    // sort the vector in asc order
    std::sort(nums.begin(), nums.end());
    int res = 0;
    int last = nums.size() - 1;
    // if first two elements negative then we need to check the product
    if ((nums[0] < 0) && (nums[1] < 0)) {
        int next_index;

        if ((nums[0]*nums[1]) > (nums[last] * nums[last - 1])) {
            res = nums[0]*nums[1];
            next_index = last;
        } else {
            res = nums[last] * nums[last - 1];
            next_index = last - 2;
        }
        res *= nums[next_index];
    } else {
        res = (nums[last] * nums[last - 1] * nums[last - 2]);
    }
    return res;
}

This solution is longer than it needs to be (and also seems to fail for some corner test cases).

A simpler approach is as follows:

1
2
3
4
5
6
7
8
9
10
if (nums.size() == 3) return (nums[0]*nums[1]*nums[2]);
// sort the vector in asc order
std::sort(nums.begin(), nums.end());
int res = 0;
int last = nums.size() - 1;

int prod1 = nums[0]*nums[1]*nums[last];
int prod2 = nums[last]*nums[last-1]*nums[last -2];

return max(prod1, prod2);

This is a nlog(n) approach.
It is possible to do this in O(n).