O(k log(n) ) solution ,using priority queues.


  • 0
    A

    Some observations,

    Since the arrays are sorted.
    nums1[i] + nums2[j1] < nums1[i] + nums2[j2] , for j1< j2
    This problem is similar to merging n linked list into one , or the same way n arrays should be merged,

    class mycomp{
      public:
        bool operator()(pair<int,int> x ,pair<int,int> y)
        {
            return x.second > y.second;
        }
    };
    class Solution {
    public:
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            int i,j,l1,l2;
            l1 = nums1.size();
            l2 = nums2.size();
            vector<pair<int,int> > ans;
            k = min(k,l1*l2);
            if(k==0)
                return ans;
            int dp[l1];
            for(i=0;i<l1;i++)
                dp[i] = 0;
            priority_queue < pair<int,int> ,vector<pair<int,int> > , mycomp > small;
            pair<int,int> temp;
            for(i=0;i<l1;i++)
            {
                small.push(make_pair(i,nums1[i]+nums2[0]));
            }
            while(ans.size() != k)
            {
                temp = small.top();
                small.pop();
                ans.push_back(make_pair(nums1[temp.first],nums2[dp[temp.first]]));
                dp[temp.first]++;
                if(dp[temp.first]< l2)
                    {
                        small.push(make_pair(temp.first,nums1[temp.first]+nums2[dp[temp.first]]));
                    }
            }
            return ans;
        }
    };
    

    Time Complexity : O ( k log(n) )
    Space Complexity : O(k)


Log in to reply
 

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