Compute the Max Product of Two Numbers in a Given List of Integers

justyy (82)in #programming • 4 years ago

Given a list of integers, find the largest product of two distinct elements.
Example 1
Input
nums = [5, 1, 7]
Output
35
Explanation
35 is the largest product that can be made from 5 * 7

Example 2
Input
nums = [7, 1, 7]
Output
49
Explanation
49 is the largest product that can be made from 7 * 7. The values can be the same but they must be separate elements.

Example 3
Input
nums = [-5, 1, -7]
Output
35
Explanation
35 is the largest product that can be made from -5 * -7.

Hints:
We can do it in O(N) by calculating the smallest two numbers and the largest two numbers and calculating the maximum products.

Sort and Compute the Max Product

We can sort the list of numbers in O(NLogN) time. Then we just need to compare the product of the biggest two numbers and the one computed from the smallest two numbers (could be negative).

int solve(vector<int>& nums) {
    sort(begin(nums), end(nums));
    return max(nums[0] * nums[1], 
               nums.back() * nums[nums.size() - 2]);
}

Linear Algorithm to Compute the Max Product

We can find the minimum and maximum two numbers in Linear time. And the max product would be the maximum of product from the smallest two numbers and the ones from the largest two numbers.

int solve(vector<int>& nums) {
    int c = INT_MAX, d = c;
    int a = -INT_MAX - 1, b = a;
    for (const auto &n: nums) {
        if (n >= a) {
            b = a;
            a = n;
        } else if (n >= b) {
            b = n;
        }
        if (n <= d) {
            c = d;
            d = n;
        } else if (n <= c) {
            c = n;
        }
    }
    return max(a * b, c * d);
}

The space complexity is O(1) constant.

--EOF (The Ultimate Computing & Technology Blog) --

Reposted to Computing and Technology

Follow me for topics of Algorithms, Blockchain and Cloud.
I am @justyy - a Steem Witness
https://steemyy.com