373. Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u1, v1), (u2, v2), …, (uk, vk) with the smallest sums.

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<vector<int>> res;
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
        for(int i = 0; i < nums2.size(); ++i)
            pq.push({nums1[0] + nums2[i], 0, i});
        while(k-- && !pq.empty()) {
            auto tp = pq.top();
            pq.pop();
            int idx1(get<1>(tp)), idx2(get<2>(tp));
            res.push_back({nums1[idx1], nums2[idx2]});
            if(idx1 < nums1.size() - 1) pq.push({nums1[idx1 + 1] + nums2[idx2], idx1 + 1, idx2});
        }
        return res;
    }
};