K-pairs with smallest sum in 2 arrays in C++
K-pairs with smallest sum in two arrays
In this page we will look into a coding question where we will learn how to find the K-pairs with smallest sum in two arrays in C++ such that one element of a pair belongs to arr1[ ] and another element belongs to arr2[ ] .
There might be different approach to solve this question, one you will find here. If your approach is bit different post it onto the comment section.
K-pairs with smallest sum in two arrays in C++
The problem of finding k pairs with the smallest sum in two arrays, A and B, involves selecting k pairs of numbers, one from each array, such that the sum of each pair (ai, bi) is minimized. The constraint is that each pair must consist of one element from A and one element from B.
For instance, given arrays A = [1, 3, 11] and B = [2, 4, 8], with k = 4, the smallest sum pairs would be (1, 2), (3, 2), (1, 4), and (3, 4), with sums of 3, 5, 5, and 7, respectively.
On this page we will discuss two different methods for this-
- Brute Force Approach
- Min Heap Approach
- Brute Force approach: The brute force method for finding k pairs with the smallest sum in two arrays involves iterating over all possible pairs of indices from both arrays and calculating the sum of each pair. The steps for the brute force method are as follows:
Algorithm:
- Initialize a result vector to hold k pairs with the smallest sum.
- Iterate over all pairs of indices (i, j) such that i is between 0 and the size of the first array minus 1, and j is between 0 and the size of the second array minus 1.
- Calculate the sum of the ith element in the first array (A[i]) and the jth element in the second array (B[j]).
- If the result vector is not yet full (i.e., its size is less than k), add the current pair (i, j) and its sum to the result vector.
- If the result vector is full (i.e., its size is equal to k), and the current sum is smaller than the sum of the largest pair in the result vector:
i. Remove the largest pair from the result vector.
ii. Add the current pair (i, j) and its sum to the result vector. - Repeat steps 3-5 for all pairs of indices.
- After processing all pairs, the result vector will contain the k pairs with the smallest sum.
- Return the result vector.
Note
The time complexity of this brute force method is O(n1 * n2), where n1 and n2 are the sizes of the two input arrays A and B, respectively, since we need to iterate over all possible pairs of indices.
C++ Code for Brute Force approach
Run
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector < pair < int, int >> kSmallestPairs (vector < int >&A, vector < int >&B, int k)
{
vector < pair < int, int >>result; // to store k pairs with smallest sum
int n1 = A.size ();
int n2 = B.size ();
// Nested loop to iterate over all pairs of indices
for (int i = 0; i < n1; ++i)
{
for (int j = 0; j < n2; ++j)
{
int sum = A[i] + B[j]; // calculate the sum
if (result.size () < k)
{
result.push_back (make_pair (A[i], B[j]));
}
else if (sum < result.back ().first + result.back ().second)
{
result.pop_back (); // remove the largest pair
result.push_back (make_pair (A[i], B[j]));
}
// Sort the result vector in ascending order based on the sum
sort (result.begin (), result.end (),
[](const pair < int, int >&a, const pair < int, int >&b)
{
return a.first + a.second < b.first + b.second;
}
);
}
}
return result;
}
int main ()
{
vector < int >A = { 1, 3, 11 };
vector < int >B = { 2, 4, 8 };
int k = 4;
vector < pair < int, int >>result = kSmallestPairs (A, B, k);
cout << "K pairs with smallest sum: " << endl;
for (const auto & pair:result)
{
cout << "(" << pair.first << ", " << pair.second << ") ";
}
return 0;
}
Output
K pairs with smallest sum: (1, 2) (1, 4) (3, 2) (3, 4)
- Min Heap Method:This algorithm outlines a more optimized approach using a min heap to
find k pairs with the smallest sum in two arrays. The steps for this
approach are as follows:
Algorithm:
- Create a min heap of pairs where each pair consists of an element from the first array and an element from the second array, along with their sum.
- Initialize heap size to 0.
- For each element in the second array: a. Create a pair with the first element from the first array and the current element from the second array. b. Add this pair to the min heap and increment heap size.
- While k is greater than 0: a. Extract the minimum element from the heap. b. Print it as one of the k pairs. c. Decrement k. d. If the extracted pair was from the first array: i. Create a new pair with the next element from the first array and the same element from the second array. ii. Add this new pair to the heap.
- Repeat steps 4a-4d until k pairs have been extracted or the heap becomes empty.
Note
This approach has a time complexity of O(k log(min(n1, n2))), where n1 and n2 are the sizes of the two input arrays A and B, respectively, as we are iterating through the elements in the second array and maintaining a min heap of size k.
C++ Code for Min Heap approach
Run
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// Define a custom comparator for pairs in the min heap
struct PairComparator
{
bool operator () (const pair < int, int >&p1, const pair < int, int >&p2)
{
return p1.first + p1.second > p2.first + p2.second;
}
};
vector < pair < int, int >>
kSmallestPairs (vector < int >&nums1, vector < int >&nums2, int k)
{
int n1 = nums1.size ();
int n2 = nums2.size ();
vector < pair < int, int >>result;
// Create a min heap with custom comparator
priority_queue < pair < int, int >, vector < pair < int, int >>,
PairComparator > minHeap;
for (int i = 0; i < n1 && i < k; i++)
{
minHeap.push (make_pair (nums1[i], nums2[0]));
}
// Loop until k pairs have been extracted or heap becomes empty
while (k > 0 && !minHeap.empty ())
{
pair < int, int >currPair = minHeap.top ();
minHeap.pop ();
result.push_back (currPair);
k--;
if (currPair.second < n2 - 1)
{
minHeap.
push (make_pair (currPair.first, nums2[currPair.second + 1]));
}
}
return result;
}
int main ()
{
vector < int >nums1 = { 1, 3, 11 };
vector < int >nums2 = { 2, 4, 8 };
int k = 4;
vector < pair < int, int >>result = kSmallestPairs (nums1, nums2, k);
cout << "K pairs with smallest sum: ";
for (auto pair:result)
{
cout << "(" << pair.first << ", " << pair.second << ") ";
}
return 0;
}
Output
K pairs with smallest sum: (1, 2) (3, 2) (11, 2)
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
Login/Signup to comment