Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1: Brute Force
3.1.
Code
3.2.
Complexity Analysis
3.2.1.
Time Complexity: O(N2 log(N2))
3.2.2.
Space Complexity: O(N2) 
4.
Approach 2: Using Heap / Priority Queue
4.1.
Code
4.2.
Complexity Analysis
4.2.1.
Time Complexity: O(N2 log(K))
4.2.2.
Space Complexity: O(K) 
5.
Frequently Asked Questions
5.1.
What is the time complexity of push() ,pop() and top() operations in heap/priority queue ?
5.2.
How can we implement a Binary Heap?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

K-th Smallest Pair Sum in The Given Array

Author Rhythm Jain
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Heap and Priority Queue

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.

Also see, Data Structures

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

Also Read, Prefix Sum Array

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 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:

  1. The root element is 0
  2. Left child : (2*i)+1
  3. Right child : (2*i)+2
  4. 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!

Live masterclass