Cover Image for C++ Program for Find k pairs with Smallest Sums in Two Arrays
78 views

C++ Program for Find k pairs with Smallest Sums in Two Arrays

To find k pairs with the smallest sums in two arrays in C++, you can use a priority queue (min-heap). You’ll create pairs from the two arrays, calculate their sums, and keep track of the k smallest sums using the priority queue. Here’s a C++ program to do that:

C++
#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

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

    if (nums1.empty() || nums2.empty() || k <= 0) {
        return result;
    }

    auto compare = [&](pair<int, int>& a, pair<int, int>& b) {
        return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
    };

    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compare)> min_heap(compare);

    // Start with pairs (0, 0), (1, 0), ..., (k-1, 0) if possible
    for (int i = 0; i < min(k, static_cast<int>(nums1.size())); i++) {
        min_heap.emplace(i, 0);
    }

    while (k-- > 0 && !min_heap.empty()) {
        auto idx_pair = min_heap.top();
        min_heap.pop();
        int i = idx_pair.first;
        int j = idx_pair.second;
        result.emplace_back(nums1[i], nums2[j]);

        // Add the next pair (i, j+1) if j+1 is within bounds
        if (j + 1 < nums2.size()) {
            min_heap.emplace(i, j + 1);
        }
    }

    return result;
}

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

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

    cout << "K pairs with smallest sums: " << endl;
    for (const auto& pair : result) {
        cout << "(" << pair.first << ", " << pair.second << ") ";
    }
    cout << endl;

    return 0;
}

In this program:

  • The kSmallestPairs function takes two input arrays nums1 and nums2, as well as an integer k representing the number of pairs to find.
  • We use a priority queue (min_heap) to store pairs, where each pair consists of indices (i, j) from nums1 and nums2, respectively.
  • We define a custom comparison function (compare) that compares pairs based on their sum.
  • We start with pairs (0, 0), (1, 0), …, (k-1, 0) if possible, pushing them into the priority queue.
  • In each iteration, we pop the pair with the smallest sum from the priority queue, add it to the result vector, and consider the next pair (i, j+1) if j+1 is within bounds.
  • Finally, we return the k smallest pairs found.

This program will find and print the k pairs with the smallest sums from the two input arrays nums1 and nums2.

YOU MAY ALSO LIKE...

The Tech Thunder

The Tech Thunder

The Tech Thunder


COMMENTS