K Pairs with Smallest Sums
Introduction
“K Pairs with Smallest Sums” is a problem in computer science and algorithm design that involves finding the K pairs of elements with the smallest sums from two given arrays. The problem typically provides two sorted arrays, and the goal is to identify the K pairs formed by selecting one element from each array in such a way that the sum of the selected elements is minimized.
What is K Pairs with Smallest Sums?
“K Pairs with Smallest Sums” is a specific algorithmic problem that involves finding K pairs of elements with the smallest sums from two given arrays.
Objective :
The objective of the “K Pairs with Smallest Sums” problem is to find and return K pairs of elements, where each pair consists of one element from the first given array (nums1) and one element from the second given array (nums2). The pairs should be chosen in such a way that their sums are minimized.
Example :
Example 1:
The “K pairs smallest sums” problem is a common algorithmic problem where you are given two integer arrays, nums1 and nums2, and are asked to find K pairs (u1, v1), (u2, v2), …, (uK, vK) such that u1 from nums1, u2 from nums2, v1 from nums1, and v2 from nums2, form the K pairs with the smallest sums.
Input: nums1 = [1,7,11] nums2 = [2,4,6] k = 3
Output:
[
[1,2],
[1,4],
[1,6]
]
Algorithm for K Pairs with Smallest Sums
- Declare a tuple
- Create a list of tuples
- Run a loop
- Generate all possible pairs
- Sort the pairs by their sum
- Return the first K pairs
- Initialize a heap
- Add the current pair to the result vector
- Here are some other steps:
- Compare the sums of the elements
- Print the minimum sum
- Increment the pointer
- Invert the two elements
K Pairs
using Naive Approach
The problem of finding k pairs with the smallest sums can be solved using a naive approach by generating all possible pairs and then selecting the k pairs with the smallest sums. Here’s a simple Python program demonstrating the naive approach:
def k_smallest_pairs(nums1, nums2, k):
# Generate all possible pairs
pairs = [(i, j) for i in nums1 for j in nums2]
# Sort pairs based on their sums
pairs.sort(key=lambda pair: pair[0] + pair[1])
# Return the first k pairs
return pairs[:k]
# Example usage:
nums1 = [1, 7, 11]
nums2 = [2, 4, 6]
k = 3
result = k_smallest_pairs(nums1, nums2, k)
print(result)
Output :
Output:
[
[1,2],
[1,4],
[1,6]
]
Explanation :
In this example, nums1 and nums2 are two lists of integers, and k is the number of pairs with the smallest sums that you want to find. The function k_smallest_pairs generates all possible pairs, sorts them based on their sums, and then returns the first k pairs.
K Pairs using Efficient Approach
An efficient approach to find k pairs with the smallest sums involves using a priority queue (heap) to keep track of the pairs with the smallest sums. Here’s an example program:
import heapq
def k_smallest_pairs(nums1, nums2, k):
if not nums1 or not nums2:
return []
result = []
heap = []
for i in range(min(k, len(nums1))):
# Store the pair (num1, num2, index of num2 in nums2) in the heap
heapq.heappush(heap, (nums1[i] + nums2[0], nums1[i], nums2[0], 0))
while k > 0 and heap:
# Pop the smallest sum pair from the heap
_, num1, num2, index = heapq.heappop(heap)
result.append([num1, num2])
# Move to the next element in nums2 for the same num1
if index + 1 < len(nums2):
heapq.heappush(heap, (num1 + nums2[index + 1], num1, nums2[index + 1], index + 1))
k -= 1
return result
# Example usage:
nums1 = [1, 7, 11]
nums2 = [2, 4, 6]
k = 3
result = k_smallest_pairs(nums1, nums2, k)
print(result)
Output :
Output: [ [1,2], [1,4], [1,6] ]
Explanation :
In this implementation, the priority queue is used to store tuples of the form (sum, num1, num2, index) where sum is the sum of the pair (num1, num2), and index is the index of num2 in nums2. We initially push the pairs formed with the first elements of nums1 and nums2 into the heap. In each iteration, we pop the pair with the smallest sum, add it to the result, and push the next pair with the same num1 and the next element from nums2. This process continues until we have found k pairs or the heap is empty.
K Pairs Using Sorting, Min heap, Map
The problem of finding k pairs with the smallest sums can be efficiently solved using a combination of sorting, a min heap, and a map. This approach avoids generating all possible pairs and leverages the properties of sorted arrays. Here’s a Python implementation:
import heapq
def k_smallest_pairs(nums1, nums2, k):
if not nums1 or not nums2:
return []
result = []
# Create a min heap to store tuples of the form (sum, num1, num2)
heap = []
# Initialize heap with pairs from the first element of nums1 and nums2
for i in range(min(k, len(nums1))):
heapq.heappush(heap, (nums1[i] + nums2[0], nums1[i], nums2[0], 0))
while k > 0 and heap:
# Pop the smallest sum pair from the heap
_, num1, num2, index = heapq.heappop(heap)
result.append([num1, num2])
# Move to the next element in nums2 for the same num1
if index + 1 < len(nums2):
heapq.heappush(heap, (num1 + nums2[index + 1], num1, nums2[index + 1], index + 1))
k -= 1
return result
# Example usage:
nums1 = [1, 7, 11]
nums2 = [2, 4, 6]
k = 3
result = k_smallest_pairs(nums1, nums2, k)
print(result)
Output :
Output: [ [1,2], [1,4], [1,6] ]
Explanation :
In this implementation, the min heap is used to maintain the pairs with the smallest sums. The heap is initially populated with pairs formed by the first element of nums1 and the elements of nums2. In each iteration, the smallest sum pair is popped from the heap, and the next pair with the same num1 and the next element from nums2 is pushed onto the heap.
Practical Applications
Following are the practical application :
To wrap it up:
As technology advances, algorithms tackling such optimization problems play a pivotal role in enhancing processes across domains like project management, supply chain logistics, biology, and recommender systems. The ability to identify pairs with the smallest differences paves the way for efficient and streamlined solutions in diverse applications.
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
Login/Signup to comment