Imagine you have two sorted arrays, arr1 and arr2, and you need to find the k pairs with the smallest sums, where one element of a pair comes from arr1 and the other element comes from arr2. This problem is not only an interesting algorithmic challenge but also has practical applications in various domains, such as data analysis, recommendation systems, and optimization problems.
Understanding the Problem
Given two integer arrays arr1 and arr2, both sorted in ascending order, and an integer k, the task is to find the k pairs with the smallest sums, where one element of a pair belongs to arr1 and the other element belongs to arr2.
For example, let‘s say we have:
arr1 = [1, 7, 11]
arr2 = [2, 4, 6]
k = 3The output should be the first 3 pairs with the smallest sums:
[1, 2], [1, 4], [1, 6]The pairs are sorted in ascending order based on their sums. In this case, the first 3 pairs with the smallest sums are [1, 2], [1, 4], and [1, 6].
Brute Force Approach
The most straightforward approach to solve this problem is the brute force method. The idea is to generate all possible pairs of elements from arr1 and arr2, calculate their sums, and then sort the pairs based on their sums. Finally, we can return the first k pairs with the smallest sums.
Here‘s the pseudocode for the brute force approach:
function kSmallestPair(arr1, arr2, k):
create an empty list to store the pairs
for each element x in arr1:
for each element y in arr2:
add the pair (x, y) to the list
sort the list based on the sum of the pairs
return the first k pairs from the sorted listThe time complexity of this approach is O(n1 n2 log(n1 n2)), where n1 and n2 are the sizes of arr1 and arr2, respectively. This is because we need to generate all possible pairs (O(n1 n2)) and then sort the list (O(n1 n2 log(n1 n2))). The space complexity is O(n1 n2), as we need to store all the pairs.
While the brute force approach is straightforward to implement, it becomes inefficient for large arrays, as it needs to generate and sort all possible pairs. We can do better by using a more efficient approach.
Efficient Approach using Min-Heap and Set
To optimize the solution, we can use a min-heap (priority queue) to keep track of the pairs with the smallest sums. We‘ll also use a set to avoid generating duplicate pairs.
The idea is as follows:
- Initialize the min-heap with the pair
(arr1[0] + arr2[0], 0, 0), where the first element is the sum, and the second and third elements are the indices of the elements fromarr1andarr2, respectively. - Initialize a set to keep track of the pairs we‘ve already processed.
- Iterate
ktimes:
a. Pop the pair with the smallest sum from the min-heap.
b. Add the pair to the output.
c. If the index of the first element in the pair is less than the length ofarr1minus 1, add the pair(arr1[index + 1] + arr2[index], index + 1, index)to the min-heap and the set, as long as the pair is not already in the set.
d. If the index of the second element in the pair is less than the length ofarr2minus 1, add the pair(arr1[index] + arr2[index + 1], index, index + 1)to the min-heap and the set, as long as the pair is not already in the set.
Here‘s the pseudocode for the efficient approach:
function kSmallestPair(arr1, arr2, k):
create a min-heap to store the pairs
create a set to store the pairs we‘ve already processed
add the pair (arr1[0] + arr2[0], 0, 0) to the min-heap and the set
for i from 1 to k:
pop the pair (sum, i1, i2) with the smallest sum from the min-heap
add the pair (i1, i2) to the output
if i1 + 1 < length of arr1:
add the pair (arr1[i1 + 1] + arr2[i2], i1 + 1, i2) to the min-heap and the set, if it‘s not already in the set
if i2 + 1 < length of arr2:
add the pair (arr1[i1] + arr2[i2 + 1], i1, i2 + 1) to the min-heap and the set, if it‘s not already in the set
return the outputThe time complexity of this approach is O(k * log k), as we need to perform k operations on the min-heap, each of which takes O(log k) time. The space complexity is O(k), as we need to store up to k pairs in the min-heap and the set.
This approach is more efficient than the brute force method, especially when k is much smaller than the product of the sizes of arr1 and arr2.
Implementation in Different Programming Languages
Here‘s the implementation of the efficient approach in various programming languages:
Python
import heapq
def kSmallestPair(arr1, arr2, k):
n1, n2 = len(arr1), len(arr2)
pq = [(arr1[0] + arr2[0], 0, 0)]
seen = set()
seen.add((0, 0))
result = []
for _ in range(k):
if not pq:
break
sum, i1, i2 = heapq.heappop(pq)
result.append((arr1[i1], arr2[i2]))
if i1 + 1 < n1:
next_sum = arr1[i1 + 1] + arr2[i2]
if (i1 + 1, i2) not in seen:
heapq.heappush(pq, (next_sum, i1 + 1, i2))
seen.add((i1 + 1, i2))
if i2 + 1 < n2:
next_sum = arr1[i1] + arr2[i2 + 1]
if (i1, i2 + 1) not in seen:
heapq.heappush(pq, (next_sum, i1, i2 + 1))
seen.add((i1, i2 + 1))
return resultJava
import java.util.*;
public class Main {
public static List<int[]> kSmallestPair(int[] arr1, int[] arr2, int k) {
int n1 = arr1.length, n2 = arr2.length;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
Set<String> seen = new HashSet<>();
List<int[]> result = new ArrayList<>();
pq.offer(new int[] {arr1[0] + arr2[0], 0, 0});
seen.add("0,0");
for (int i = 0; i < k; i++) {
if (pq.isEmpty()) {
break;
}
int[] pair = pq.poll();
result.add(new int[] {arr1[pair[1]], arr2[pair[2]]});
if (pair[1] + 1 < n1) {
int nextSum = arr1[pair[1] + 1] + arr2[pair[2]];
String key = (pair[1] + 1) + "," + pair[2];
if (!seen.contains(key)) {
pq.offer(new int[] {nextSum, pair[1] + 1, pair[2]});
seen.add(key);
}
}
if (pair[2] + 1 < n2) {
int nextSum = arr1[pair[1]] + arr2[pair[2] + 1];
String key = pair[1] + "," + (pair[2] + 1);
if (!seen.contains(key)) {
pq.offer(new int[] {nextSum, pair[1], pair[2] + 1});
seen.add(key);
}
}
}
return result;
}
public static void main(String[] args) {
int[] arr1 = {1, 7, 11};
int[] arr2 = {2, 4, 6};
int k = 3;
List<int[]> result = kSmallestPair(arr1, arr2, k);
for (int[] pair : result) {
System.out.println(Arrays.toString(pair));
}
}
}C++
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> kSmallestPair(vector<int>& arr1, vector<int>& arr2, int k) {
int n1 = arr1.size(), n2 = arr2.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>> seen;
vector<pair<int, int>> result;
pq.push({arr1[0] + arr2[0], {0, 0}});
seen.insert({0, 0});
for (int i = 0; i < k; i++) {
if (pq.empty()) {
break;
}
auto [sum, indices] = pq.top();
pq.pop();
result.emplace_back(arr1[indices.first], arr2[indices.second]);
if (indices.first + 1 < n1) {
int nextSum = arr1[indices.first + 1] + arr2[indices.second];
if (seen.find({indices.first + 1, indices.second}) == seen.end()) {
pq.push({nextSum, {indices.first + 1, indices.second}});
seen.insert({indices.first + 1, indices.second});
}
}
if (indices.second + 1 < n2) {
int nextSum = arr1[indices.first] + arr2[indices.second + 1];
if (seen.find({indices.first, indices.second + 1}) == seen.end()) {
pq.push({nextSum, {indices.first, indices.second + 1}});
seen.insert({indices.first, indices.second + 1});
}
}
}
return result;
}
int main() {
vector<int> arr1 = {1, 7, 11};
vector<int> arr2 = {2, 4, 6};
int k = 3;
vector<pair<int, int>> result = kSmallestPair(arr1, arr2, k);
for (auto [x, y] : result) {
cout << "(" << x << ", " << y << ")" << endl;
}
return 0;
}JavaScript
class PriorityQueue {
constructor(comparator = (a, b) => a[0] - b[0]) {
this.heap = [];
this.comparator = comparator;
}
enqueue(value) {
this.heap.push(value);
this.bubbleUp();
}
dequeue() {
const root = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this.sinkDown();
}
return root;
}
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.comparator(this.heap[index], this.heap[parentIndex]) < 0) {
this.swap(index, parentIndex);
index = parentIndex;
} else {
break;
}
}
}
sinkDown() {
let index = 0;
const length = this.heap.length;
const root = this.heap[0];
while (true) {
const leftChildIndex = 2 * index + 1;
const rightChildIndex = 2 * index + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (this.comparator(leftChild, root) < 0) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if (
(swap === null && this.comparator(rightChild, root) < 0) ||
(swap !== null && this.comparator(rightChild, leftChild) < 0)
) {
swap = rightChildIndex;
}
}
if (swap === null) {
break;
}
this.swap(index, swap);
index = swap;
}
}
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
}
function kSmallestPair(arr1, arr2, k) {
const n1 = arr1.length, n2 = arr2.length;
const pq = new PriorityQueue();
const seen = new Set();
const result = [];
pq.enqueue([arr1[0] + arr2[0], 0, 0]);
seen.add(`0,0`);
for (let i = 0; i < k; i++) {
if (pq.heap.length === 0) {
break;
}
const [sum, i1, i2] = pq.dequeue();
result.push([arr1[i1], arr2[i