# K-th Smallest Pair Sum in The Given Array

## Introduction

Array-based problems are very commonly asked in programming interviews so it becomes increasingly necessary to practice array problems that include various techniques and algorithms.

Let’s solve one such problem that uses a different approach.

## Problem Statement

We have an array of integers arr[] of size N and an integer K. Our task is to find the K-th smallest pair sum in the given array.

Example:

Assume we have the following input -

Input:

arr[] = {5, 2, 1,3}

K = 4

Output:

6

Explanation:

The Sum of all the pairs are -

5+2=7

5+1=6

5+3=8

2+1=3

2+3=5

1+3=4

So if we arrange them in increasing order we have-

3,4,5,6,7,8

So the 4th Smallest Pair Sum is 6.

## Approach 1: Brute Force

The most obvious approach is that we store the sum of all the pairs in the array( no duplicates) and then sort the array in increasing order and then return the kth element from the array.

This Naive approach can be called a Greedy choice.

Algorithm:

• Initialize an array of int called pairs.
• Initialize a for loop from i=0 to t=N
• Initialize another for loop from j=i+1 to N so that we can get each pair
• sum=arr[i]+arr[j]
• Insert sum into pairs
• Sort the array pairs and remove duplicates(We can also use hashmap for the same to keep track of duplicate elements)
• Return kth element from the pairs array.

### Code

``````#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int KPairSum(vector<int> arr,int K){
vector<int> pairs;
unordered_map<int,int> umap;
int N=arr.size();
int sum;

for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++){
sum=arr[i]+arr[j];

//if sum not in pairs array already
if(umap.count(sum)==0){
umap[sum]=1;
pairs.push_back(sum);
}
}
}
//sorting array
sort(pairs.begin(),pairs.end());

//return kth element
return pairs[K-1];
}
int main()
{
vector<int> arr={5,2,1,3};
int K = 4;
cout<<KPairSum(arr,K);
return 0;
}``````

Output

``6``

### Complexity Analysis

#### Time Complexity: O(N2 log(N2))

Because for an array of size N sorting takes O(NlogN) time. But since the total possible pairs are NC2 = N(N-1)/2 so the size of the pairs array is of the range O(N2). So for an array of size N2 sorting will take O(N2 log(N2)) time complexity.

#### Space Complexity: O(N2)

since the total possible pairs are NC2 = N(N-1)/2 so the size of the pairs array is of the range O(N2)

## Approach 2: Using Heap / Priority Queue

We can use a heap and maintain its size to be K at max.

Algorithm:

• Iterate over the array starting at I = 0 and ending at I = N-2.
• Iterate from j = i+1 to j = N-1 for each i.
• Insert the sum of this I j) pair into the max heap.
• Compare the top element of the heap to this total if the heap is full.
• If the top element's value is higher, the new sum should be used instead.
• When the iteration is finished, the K-th smallest pair sum is the topmost member of the max-heap. So return the top element of the heap.

### Code

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

int kPairSum(vector<int>& arr, int K)
{
int N = arr.size();

// Priority queue to implement heap
priority_queue<int> pq;
int sum;

for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {

// Variable to store the sum
sum = arr[i] + arr[j];

// If the heap is full
if (pq.size() == K) {

// If the top element is greater
if (pq.top() > sum) {
pq.pop();
pq.push(sum);
}
}
else
pq.push(sum);
}
}

// Return the Kth smallest value
return pq.top();
}

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

cout << kPairSum(arr, K);
return 0;
}``````

Output

``6``

### Complexity Analysis

#### Time Complexity: O(N2 log(K))

Because for a heap of size K insertion and deletion takes O(log K) time. But since the total possible pairs are NC2 = N(N-1)/2 so the size of the pairs array is of the range O(N2). So for N2 iterations and heap of size K at each iteration, time complexity becomes O(N2 log K)

#### Space Complexity: O(K)

Because we only need a heap of maximum size K.

1. What is the time complexity of push() ,pop() and top() operations in heap/priority queue ?
In a priority queue, the complexity of push(), pop(), and top() operations depends upon the implementation of the heap. For the inbuilt STL priority_queue, the complexity of all the three functions, push() and pop() is O(logN) where N is the size of the heap whereas top() is O(1). That’s because the heap is organized in the form of a balanced tree.

2. How can we implement a Binary Heap?
An array is widely used to implement binary heaps. Any binary tree may be stored in an array, but a binary heap can be stored compactly since it is always a complete binary tree. Pointers don't take up any space; instead, arithmetic on array indices may be used to get the parent and children of each node:
1. The root element is 0
2. Left child : (2*i)+1
3. Right child : (2*i)+2
4. Parent : (i-1)/2

## Key Takeaways

Array Questions are very commonly asked in a coding interview and it is a topic that must not be left behind. To practice more questions on array please visit Top Array Coding Interview Questions.

Priority Queue or we can say heap is of two types typically called max heap and min-heap. 