Heap: Find the minimum product of k integers in an array

Problem Statement:

Given an array and a value k, you need to find the minimum product of k integers

Example:

Input: arr [] = [1, 5, 3, 2, 6] k = 3

Output = 6

[1, 2, 3] are the minimum k integers and the product is 6

Solution Explanation:

We will use max heap in the solution.

We will insert first k integers

Then compare the top of the heap and if its smaller, remove the top element and insert the current element.

Take the product of first k integers

Time Complexity: O(n * log k)
Space Complexity: O(k)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int>& arr, int k) 
{
    
    priority_queue<int> maxHeap;

    for (int i = 0; i < k; ++i) 
    {
        maxHeap.push(arr[i]);
    }
    
    for (int i = k; i < arr.size(); ++i) 
    {
        if (arr[i] < maxHeap.top()) 
        {
            maxHeap.pop();
            maxHeap.push(arr[i]);
        }
    }
    
    int result = 1;
    while (!maxHeap.empty()) {
        result *= maxHeap.top();
        maxHeap.pop();
    }
    
    return result;
}

int main() 
{
    vector<int> arr1 = {1, 5, 3, 2, 6};
    cout << solution(arr1, 3);

    return 0;
}

Output

6