Leetcode 373 Solution

This article provides solution to leetcode question 373 (find-k-pairs-with-smallest-sums)
Categories:
Tags:
Access this page by simply typing in "lcs 373" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/find-k-pairs-with-smallest-sums

Solution

class Solution {
public:
    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        multimap<int, pair<int, int>> m;



        for (int i = 0; i < nums1.size(); i++)
        {
            for (int j = 0; j < nums2.size(); j++)
            {
                m.insert(make_pair(nums1[i] + nums2[j], make_pair(nums1[i], nums2[j])));



                if (m.size() > k)
                    m.erase(--m.end());
            }
        }



        vector<pair<int, int>> res;



        for (auto it = m.begin(); it != m.end(); it++)
        {
            if (k == 0)
                break;



            res.push_back(it->second);



            k--;
        }



        return res;
    }
};