Identify the k pairs with the smallest sums by selecting one integer from arr1 and one integer from arr2 from two ascending integer arrays arr1 and arr2, respectively.
Examples:
Input : arr1[] = {1, 7, 11}
arr2[] = {2, 4, 6}
k = 3
Output : [1, 2],
[1, 4],
[1, 6]
Explanation: The first three pairs from the sequence [1, 2], [1, 4], [1, 6], [7, 2], [7, 4], [11, 2], [7, 6], [11, 4], [11, 6] are returned.
Method No. 1 (Simple)
Locate and list all pairs, then calculate the total of each pair. This process has a time complexity of O(n1 * n2), with n1 and n2 representing the dimensions of the input arrays.
Then arrange the pairs based on their total values. The time complexity for this operation is O(n1 n2 log (n1 * n2)).
The total time complexity is O(n1 n2 log (n1 * n2)).
The auxiliary space complexity is O(n1*n2).
Method 2 (Potent):
Beginning with the tiniest sum pair, we proceed to unveil k tiniest sum combinations step by step. The objective is to monitor all elements in array2 that have already undergone scrutiny for each specific element array1[i1], ensuring that in each cycle we move on to the subsequent element. To achieve this, we employ an index array indexno2 to store the positions of the upcoming elements in the alternate array. This array essentially specifies which element from the second array needs to be paired with the element from the first array during each iteration. As we identify the element contributing to the next lowest sum pair, we increment the corresponding value in the index array.
Implementation in C++:
#include<bits/stdc++.h>
using namespace std;
void kSmallestP(int array1[], int n1, int array2[],
int n2, int k)
{
if (k > n1*n2)
{
cout << "k pairs don't exist";
return ;
}
int indexno2[n1];
memset(indexno2, 0, sizeof(indexno2));
while (k > 0)
{
int minimum_sum = INT_MAX;
int minimum_index = 0;
for (int i1 = 0; i1 < n1; i1++)
{
if (indexno2[i1] < n2 &&
array1[i1] + array2[indexno2[i1]] < minimum_sum)
{
minimum_index = i1;
minimum_sum = array1[i1] + array2[indexno2[i1]];
}
}
cout << "(" << array1[minimum_index] << ", "
<< array2[indexno2[minimum_index]] << ") ";
indexno2[minimum_index]++;
k--;
}
}
int main()
{
int array1[] = {1, 3, 11};
int n1 = sizeof(array1) / sizeof(array1[0]);
int array2[] = {2, 4, 8};
int n2 = sizeof(array2) / sizeof(array2[0]);
int k = 4;
kSmallestP( array1, n1, array2, n2, k);
return 0;
}
Output:
(1, 2) (1, 4) (3, 2) (3, 4)
- Time Complexity will be O(k*n1).
- Auxiliary Space will be O(n1).
Method 3: Sorting, Min heap, and Map
Instead of brute forcing our way through all of the available sum combinations, we should develop a strategy to narrow our search space down to possible candidate sum combinations.
- In C++, create a min heap, i.e. priority_queue, to hold the sum combinations as well as the indices of the components from both arrays A and B that make up the sum. The sum is used to sort the heap.
- Initialize the heap with the indices of entries from both arrays and the smallest possible sum combination, i.e. (A[0] + B[0]) (0, 0). Inside the min heap, the tuple will be (A[0] + B[0], 0, 0). The heap is ordered by the first value, which is the sum of both items.
- Pop the heap to acquire the current smallest sum and the element indices that make up the sum. Allow the tuple to be (sum, i, j). Insert (A[i + 1] + B[j], I + 1, j) and (A[i + 1], I j + 1) into the min heap, but make sure that the pair of indices I + 1, j) and I j + 1) are not already present. In C++, we may use set to test this. Return to 4 till K times.
- Insert (A[i + 1] + B[j], I + 1, j) and (A[i + 1], I j + 1) into the min heap, but make sure that the pair of indices I + 1, j) and I j + 1) are not already present. In C++, we may use set to test this.
- Return to 4 till K times.
Implementation in C++:
#include <bits/stdc++.h>
using namespace std;
void kSmallestP(vector<int> A, vector<int> B, int K)
{
int n = A.size();
priority_queue<pair<int, pair<int, int> >,
vector<pair<int, pair<int, int> > >,
greater<pair<int, pair<int, int> > > >
pq;
set<pair<int, int> > my_set;
pq.push(make_pair(A[0] + B[0], make_pair(0, 0)));
my_set.insert(make_pair(0, 0));
int flag = 1;
for (int count = 0; count < K && flag; count++) {
pair<int, pair<int, int> > temp = pq.top();
pq.pop();
int i = temp.second.first;
int j = temp.second.second;
cout << "(" << A[i] << ", " << B[j] << ")"
<< endl;
flag = 0;
if (i + 1 < A.size()) {
int sum = A[i + 1] + B[j];
pair<int, int> temp1 = make_pair(i + 1, j);
if (my_set.find(temp1) == my_set.end()) {
pq.push(make_pair(sum, temp1));
my_set.insert(temp1);
}
flag = 1;
}
if (j + 1 < B.size()) {
int sum = A[i] + B[j + 1];
pair<int, int> temp1 = make_pair(i, j + 1);
if (my_set.find(temp1) == my_set.end()) {
pq.push(make_pair(sum, temp1));
my_set.insert(temp1);
}
flag = 1;
}
}
}
int main()
{
vector<int> A = { 1 };
vector<int> B = { 2, 4, 5, 9 };
int K = 8;
kSmallestP(A, B, K);
return 0;
}
Output:
(1, 2)
(1, 4)
(1, 5)
(1, 9)
- Auxiliary Space will be O(n) because we are utilising additional space .
- Time Complexity will be O(n*logn) assuming k<=n .
