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 the 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;
}

You can also try this code with Online C++ Compiler
Run Code
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.
Check out this problem - Next Smaller Element
Frequently Asked Questions
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 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.
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:
- The root element is 0
- Left child : (2*i)+1
- Right child : (2*i)+2
- Parent : (i-1)/2
Conclusion
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 the priority queues you can click here Learn Priority Queues.
Recommended Readings:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Happy Coding!