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 the smallest sum 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
K-pairs with smallest sum in 2 arrays is a problem that involves finding the k pairs of numbers, one from each of two given arrays, that have the smallest possible sum. The problem statement can be stated as follows:
Given two arrays A and B of length n1 and n2, respectively, find k pairs (a1, b1), (a2, b2), …, (ak, bk) such that the sum ai + bi is minimized, subject to the constraint that each pair (ai, bi) must consist of one element from A and one element from B.
For example, consider the arrays A = [1, 3, 11] and B = [2, 4, 8], and k = 4. The k pairs with smallest sum are (1, 2), (3, 2), (1, 4), and (3, 4), with sum 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: One way to solve the problem of finding K pairs with the smallest sum in two arrays is to use a brute force approach. Here, we can generate all possible pairs of elements from the two arrays and then sort them based on their sum. Finally, we can return the first K pairs from the sorted list.
Algorithm:
- Initialize a result array to hold k pairs with smallest sum.
- For each pair 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 and the jth element in the second array.
- If the result array is not yet full, add the current pair (i, j) and its sum to the result array.
- If the result array is full, and the current sum is smaller than the sum of the largest pair in the result array: i. Remove the largest pair from the result array. ii. Add the current pair (i, j) and its sum to the result array.
- Return the result array.
Note
The time complexity of this algorithm is O(m * n * k), where m and n are the sizes of the two input arrays
C Code for Brute Force approach
Run
#include <stdio.h>
#include <stdlib.h>
int cmpfunc (const void *a, const void *b)
{
int *ptr1 = (int *) a;
int *ptr2 = (int *) b;
return (ptr1[0] + ptr1[1]) - (ptr2[0] + ptr2[1]);
}
void kSmallestPairs (int *arr1, int m, int *arr2, int n, int k)
{
int pairs[m * n][2], i, j, count = 0;
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
pairs[count][0] = arr1[i];
pairs[count][1] = arr2[j];
count++;
}
}
qsort (pairs, m * n, sizeof (int) * 2, cmpfunc);
for (i = 0; i < k && i < m * n; i++)
{
printf ("(%d, %d) ", pairs[i][0], pairs[i][1]);
}
}
int main ()
{
int arr1[] = { 1, 7, 11 };
int m = sizeof (arr1) / sizeof (arr1[0]);
int arr2[] = { 2, 4, 6 };
int n = sizeof (arr2) / sizeof (arr2[0]);
int k = 3;
kSmallestPairs (arr1, m, arr2, n, k);
return 0;
}
Output
(1, 2) (1, 4) (1, 6)
- Min Heap Method:The min heap method is an efficient way to find k pairs with the smallest sum in two arrays. Here’s a algorithm for this approach
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, create a pair with the first element from the first array and the current element from the second array. Add this pair to the min heap and increment heap size.
- While k is greater than 0, extract the minimum element from the heap, print it, and decrement k.
- If the extracted pair was from the first array, create a new pair with the next element from the first array and the same element from the second array. Add this new pair to the heap.
- Repeat steps 4-5 until k pairs have been extracted or the heap becomes empty.
Note
The time complexity of this algorithm is O(k log k) as it involves extracting k elements from a heap of size k
C Code for Min Heap approach
Run
#include <stdio.h>
#include <stdlib.h>
struct Pair
{
int x;
int y;
int sum;
};
void swap (struct Pair *a, struct Pair *b)
{
struct Pair t = *a;
*a = *b;
*b = t;
}
void minHeapify (struct Pair arr[], int n, int i)
{
int smallest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l].sum < arr[smallest].sum)
{
smallest = l;
}
if (r < n && arr[r].sum < arr[smallest].sum)
{
smallest = r;
}
if (smallest != i)
{
swap (&arr[i], &arr[smallest]);
minHeapify (arr, n, smallest);
}
}
void buildMinHeap (struct Pair arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
{
minHeapify (arr, n, i);
}
}
struct Pair minHeapExtractMin (struct Pair arr[], int *n)
{
struct Pair min = arr[0];
arr[0] = arr[*n - 1];
(*n)--;
minHeapify (arr, *n, 0);
return min;
}
void minHeapInsert (struct Pair arr[], int *n, struct Pair key)
{
(*n)++;
int i = *n - 1;
arr[i] = key;
while (i != 0 && arr[(i - 1) / 2].sum > arr[i].sum)
{
swap (&arr[i], &arr[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
void kSmallestPairs (int arr1[], int m, int arr2[], int n, int k)
{
if (m <= 0 || n <= 0 || k <= 0)
{
return;
}
if (k > m * n)
{
k = m * n;
}
struct Pair heap[m];
int heapSize = 0;
for (int j = 0; j < n; j++)
{
struct Pair p = { arr1[0], arr2[j], arr1[0] + arr2[j] };
minHeapInsert (heap, &heapSize, p);
}
for (int i = 0; i < k; i++)
{
struct Pair p = minHeapExtractMin (heap, &heapSize);
printf ("(%d, %d) ", p.x, p.y);
if (p.x < m - 1)
{
struct Pair next = { arr1[p.x + 1], p.y, arr1[p.x + 1] + p.y };
minHeapInsert (heap, &heapSize, next);
}
}
}
int main ()
{
int arr1[] = { 1, 7, 11 };
int m = sizeof (arr1) / sizeof (arr1[0]);
int arr2[] = { 2, 4, 6 };
int n = sizeof (arr2) / sizeof (arr2[0]);
int k = 3;
kSmallestPairs (arr1, m, arr2, n, k);
return 0;
}
Output
(1, 2) (1, 4) (1, 6)
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