Easy to follow C++ solution using a priority_queue


  • 0
    G

    Maintain a min heap of size k iterating through all pairs.

        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<pair<int, int>> ret;
            struct mySmaller {
                bool operator() (const pair<int, int>& p1, const pair<int, int>& p2) {
                    return (p1.first + p1.second <= p2.first + p2.second);
                }
            };
            priority_queue<pair<int, int>, vector<pair<int, int>>, mySmaller> pq;
            for (int i = 0; i < nums1.size(); i++) {
                for (int j = 0; j < nums2.size(); j++) {
                    pq.push(make_pair(nums1[i], nums2[j]));
                    if (k-- <= 0) {
                        pq.pop();
                    }
                }
            }
            while (!pq.empty()) {
                ret.push_back(pq.top());
                pq.pop();
            }
            return ret;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.