<p>You are given two integer arrays <code>nums1</code> and <code>nums2</code> sorted in <strong>non-decreasing&nbsp;order</strong> and an integer <code>k</code>.</p>

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

<p>Return <em>the</em> <code>k</code> <em>pairs</em> <code>(u<sub>1</sub>, v<sub>1</sub>), (u<sub>2</sub>, v<sub>2</sub>), ..., (u<sub>k</sub>, v<sub>k</sub>)</code> <em>with the smallest sums</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,7,11], nums2 = [2,4,6], k = 3
<strong>Output:</strong> [[1,2],[1,4],[1,6]]
<strong>Explanation:</strong> The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,1,2], nums2 = [1,2,3], k = 2
<strong>Output:</strong> [[1,1],[1,1]]
<strong>Explanation:</strong> The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums1.length, nums2.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums1[i], nums2[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>nums1</code> and <code>nums2</code> both are sorted in <strong>non-decreasing order</strong>.</li>
	<li><code>1 &lt;= k &lt;= 10<sup>4</sup></code></li>
	<li><code>k &lt;=&nbsp;nums1.length *&nbsp;nums2.length</code></li>
</ul>

int lower(int x,vector<int>& arr){
    int l=0;
    int r=arr.size()-1;
    while(l<=r){
        int m=l+(r-l)/2;
        if(arr[m] <= x){
            l = m+1;
        }
        else{
            r=m-1;
        }
    }
    return r;
}
bool check(int s,int k,vector<int>& nums1, vector<int>& nums2){
        int n1 = nums1.size();
        int n2 = nums2.size();
        long long cnt = 0;
        for(int i=0;i<n1;i++){
            int x = nums1[i];
            int l = lower(s-x,nums2);
            if(l == -1){break;}
            cnt = cnt + (l+1);
        }
        if(cnt >= k){
            return true;
        }
        else{
            return false;
        }
}

bool compare(const vector<int>& p1,const vector<int>& p2){
     if(p1[2] < p2[2]){
        return true;
     }
     else if(p1[2] == p2[2]){
        if(p1[0] < p2[0]){
            return true;
        }
        else if(p1[0] == p2[0]){
            return p1[1]<p2[1];
        }
        else return false;
     }
     else return false;
}

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int n1 = nums1.size();
        int n2 = nums2.size();      
        // if(n1 > n2){
        //     return kSmallestPairs(nums2,nums1,k);
        // }
        // vector<int> arr(n1+n2-1,0);
        // for(int i=0;i<n1+n2-1;i++){
        //     if(i<n1){
        //         arr[i]=i+1;
        //     }
        //     else if(i>=n1 && i<n2){
        //         arr[i]=arr[i-1];
        //     }
        //     else{
        //         arr[i]=arr[i-1]-1;
        //     }
        // }
        // int sz = arr.size();
        // int sum = 0;
        // for(int i=0;i<sz;i++){
        //     sum = sum + arr[i];
        //     arr[i]=sum;
        // }
        // int idx = lower(k,arr);
        int l=nums1[0]+nums2[0];
        int r = nums1[n1-1]+nums2[n2-1];
        while(l<=r){
            int m=l+(r-l)/2;
            if(check(m,k,nums1,nums2)){
               r=m-1;
            }
            else{
               l=m+1;
            }
        }
        int sum = l;
        vector<vector<int>> ans;
        // priority_queue<vector<int>,vector<vector<int>>,Compare> pq;
        int i=0;
        int j=0;
        while(i<n1 && j<n2){
            if(nums1[i]+nums2[j] < sum){
                ans.push_back({nums1[i],nums2[j],nums1[i]+nums2[j]});
                j++;
                if(j == n2){
                    j=0;i++;
                }
            }
            else{
                i++;
                j=0;
            }
        }
        unordered_map<int,int> mp;
        for(int u=0;u<n2;u++){
            mp[nums2[u]]++;
        }
        for(int u=0;u<n1;u++){
            int tar = sum - nums1[u];
            if(mp[tar]){
                int tempo = 0;
                while(ans.size()<k && tempo<mp[tar]){
                ans.push_back({nums1[u],tar,sum});
                tempo++;
                }
            }
        }
        sort(ans.begin(),ans.end(),compare);
        cout<<ans.size()<<endl;
        vector<vector<int>> final;
        for(int t=0;t<k;t++){
            final.push_back({ans[t][0],ans[t][1]});
        }
        // int z=k-1;
        // while(!pq.empty()){
        //      vector<int> top = pq.top();
        //      pq.pop();
        //      final[z]={top[0],top[1]};
        //      z--;
        // }
        return final;
    }
};
170888