Find Maximum Product Of Two Integers In An Array

Given an array with n elements, find the maximum product of two integers in this array.

Test Cases

Example Test Case 1

Sample Input: 4 6 1 9 8
Expected Output: 72
Because out of all the possible combinations of two integers in the array, 9*8 provides the maximum value.

Example Test Case 2

Sample Input: -2, 4, -50, 6, 1, 9, 8
Expected Outptut: 100
Because out of all the possible combinations of two integers in the array -2*-50 provides the highest value.

Solution

After going over few examples, it is clear that the maximum product will be either the product of two highest numbers or it will be the product of two lowest numbers (in case, both the numbers are negative as shown in the above example)

We can compute the two highest and two lowest number by sorting the full array in O(nlogn) time.

However, since we only have to compute the maximum and the minimum numbers we can do it in O(n) as well as shown below.

Implementation

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> vec = {-2, 4, -50, 6, 1, 9, 8};

    // Initializing the maxNum with the first two numbers
    int maxNum[2] = { max(vec[0], vec[1]), min(vec[0], vec[1]) };

    // Initializing minNum with the first two numbers
    int minNum[2] = { min(vec[0], vec[1]), max(vec[0], vec[1]) };

    for(int i = 2; i < vec.size(); i++) {
    // If vec[i] is more than the highest number so far, then second highest number = highest and highest = vec[i]
        if (vec[i] >= maxNum[0]) {
            maxNum[1] = maxNum[0];
            maxNum[0] = vec[i];
        }
        else if (vec[i] > maxNum[1]) {
            maxNum[1] = vec[i];
        }

// If vec[i] is less than the lowest number so far, then the second lowest = lowest and lowest = vec[i]
        if (vec[i] <= minNum[0]) {
            minNum[1] = minNum[0];
            minNum[0] = vec[i];
        }
        else if (vec[i] <= minNum[1]) {
            minNum[1] = vec[i];
        }
    }

    cout << max(maxNum[0]*maxNum[1], minNum[0]*minNum[1]) << "\n";

}