Find K Pairs with Smallest Sum

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and two integers k and target. Find k pairs (a, b) from the arrays such that a + b is the smallest possible value, and a + b is less than or equal to target. Return the pairs in sorted order.

Sample Input/Output:

Let’s consider a sample input:

nums1 = [1, 7, 11]
nums2 = [2, 4, 6]
k = 3
target = 15

Expected Output:

[[1, 2], [1, 4], [1, 6]]

Explanation:
For the given input nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3, and target = 15, we need to find 3 pairs with the smallest sum that is less than or equal to 15. The possible pairs are:

1. [1, 2]: sum = 3
2. [1, 4]: sum = 5
3. [1, 6]: sum = 7

Time and Space Complexity:

The time complexity of the solution will be O(k log k), where k is the value of k. We use a min-heap to store the k smallest pairs, and each insertion into the heap takes log k time.

The space complexity will be O(k) to store the k smallest pairs in the min-heap.

Solution:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k, int target) {
    vector<vector<int>> result;
    priority_queue<pair<int, vector<int>>, vector<pair<int, vector<int>>>, greater<pair<int, vector<int>>>> minHeap;

    for (int num1 : nums1) {
        for (int num2 : nums2) {
            int sum = num1 + num2;
            if (sum <= target) {
                minHeap.push({sum, {num1, num2}});
                if (minHeap.size() > k) {
                    minHeap.pop(); // Keep the minHeap size <= k
                }
            } else {
                break; // Since the arrays are sorted, there's no need to continue further
            }
        }
    }

    while (!minHeap.empty()) {
        result.push_back(minHeap.top().second);
        minHeap.pop();
    }

    return result;
}

int main() {
    vector<int> nums1 = {1, 7, 11};
    vector<int> nums2 = {2, 4, 6};
    int k = 3;
    int target = 15;

    vector<vector<int>> result = kSmallestPairs(nums1, nums2, k, target);

    cout << "K Pairs with Smallest Sum:\n";
    for (const auto& pair : result) {
        cout << "[" << pair[0] << ", " << pair[1] << "] ";
    }
    cout << endl;

    return 0;
}

In this implementation, we use a min-heap to find the k pairs with the smallest sum. The minHeap stores pairs of sum and corresponding vectors [num1, num2]. We iterate through all pairs of num1 and num2, calculate their sum, and add it to the minHeap. We keep the size of the minHeap <= k, and whenever the size exceeds k, we pop the smallest pair. This ensures that we always have the k smallest pairs in the minHeap.

The main function demonstrates the usage of kSmallestPairs by finding k pairs with the smallest sum for the given input nums1, nums2, k, and target.

The output will be:

K Pairs with Smallest Sum:
[1, 2] [1, 4] [1, 6]