# Share My Solution which beat 96.42%

• This problem is exactly the same as Leetcode378 Kth Smallest Element in a Sorted Matrix, the only difference is this problem give two array while 378 gives a matrix, but they are the same. You can check my previous post for 378 to see how it works.
https://discuss.leetcode.com/topic/52948/share-my-thoughts-and-solution

``````public class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
int m = nums1.length, n = nums2.length;
List<int[]> res = new ArrayList<int[]>();
if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0 || k <= 0) return res;
for(int j = 0; j <= n-1; j++) pq.offer(new Tuple(0, j, nums1[0]+nums2[j]));
for(int i = 0; i < Math.min(k, m *n); i++) {
Tuple t = pq.poll();
if(t.x == m - 1) continue;
pq.offer(new Tuple (t.x + 1, t.y, nums1[t.x + 1] + nums2[t.y]));
}
return res;
}
}

class Tuple implements Comparable<Tuple> {
int x, y, val;
public Tuple (int x, int y, int val) {
this.x = x;
this.y = y;
this.val = val;
}

@Override
public int compareTo (Tuple that) {
return this.val - that.val;
}
}
``````

• Clear solution!
Just a small detail: As there are `int m = nums1.length, n = nums2.length`, the checking of `num1 == null` and `num2 == null` is useless.

• In the line `for(int i = 0; i < Math.min(k, m *n); i++)`

Could you explain this condition `Math.min(k, m *n)`? I'm not exactly sure why we need to compare the minimum of k and m*n

• @aoben10 m * n is a maximum number of tuples that can be generated from two arrays. If k is greater than this number, the loop will go beyond arrays. `Math.min(k, m * n)` picks up the loop limitation accordingly.

• Nice and clear solution. Thanks for sharing!
One small question: how to explain its time complexity in an interview? Suppose the length of nums1 and nums2 are m and n, should the time complexity be O((n+k)*logn) when k < m*n, otherwise O((n+m*n)*logn)?

• great solution! this is k-way merge sort.

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