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(N² log(N²))

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

Space Complexity: O(N²) 

since the total possible pairs are ^NC₂ = N(N-1)/2 so the size of the pairs array is of the range O(N²)

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(N² log(K))

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

Space Complexity: O(K) 

Because we only need a heap of maximum size K.

Frequently Asked Questions

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.

If you wish to learn more about priority queue you can click here Learn Priority Queues.

Happy Coding!