Heap: Given an array, find the kth smallest pair sum

Problem Statement:

You are given an array and an integer k, you need to find the kth smallest pair sum

Example:

Input arr = [1, 2, 4, 3] k = 2

Output: 4

Explanation:

possible sum: 
1 + 2 = 3
1 + 3 = 4
1 + 4 = 5
2 + 3 = 5
2 + 4 = 6
3 + 4 = 7

2nd smallest sum is 4

Solution Explanation:

We will use max heap to solve the problem.

Take a maxHeap of size k.

Take a nested loop and then get the sum of the pair and insert into the heap.

If the heap is full and if the top element is greater than the current sum, replace with new sum and arrive at the result.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int solution(vector<int>& arr, int K)
{
    priority_queue<int> pq;

    for (int i = 0; i < arr.size() - 1; i++) 
    {
        for (int j = i + 1; j < arr.size(); j++) 
        {

            int temp = arr[i] + arr[j];

            if (pq.size() == K) 
            {

                if (pq.top() > temp) 
                {
                    pq.pop();
                    pq.push(temp);
                }
            }
            else
                pq.push(temp);
        }
    }

    return pq.top();
}

int main()
{
    vector<int> arr = { 1, 2, 4, 3 };
    int K = 2;

    cout << solution(arr, K);
    return 0;
}

Output

4