# Java, compare the time between minPQ(n1 + n2) vs minPQ(k)

• intuitively, we can use minPQ to store all the sum from nums1 and nums2, and then output the minimum K pairs (43 ms)

``````class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}

public int getSum() {
return x + y;
}
}

public class Solution {

public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> res = new ArrayList<int[]>();

if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
return res;
}

PriorityQueue<Pair> minPQ = new PriorityQueue<Pair>(nums1.length * nums2.length, new Comparator<Pair>(){
@Override
public int compare(Pair a, Pair b) {
return a.getSum() - b.getSum();
}
});

for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
Pair cur = new Pair(nums1[i], nums2[j]);
}
}

for (int i = 0; i < k && !minPQ.isEmpty(); i++) {
int[] arr = new int[2];
Pair cur = minPQ.poll();
arr[0] = cur.x;
arr[1] = cur.y;
}
return res;
}
}
``````

thanks to @bbccyy1 , we can use minPQ(size k) to store the information, and the running time is 8 ms

``````class Pair {
int x;
int y;
int index;

public Pair(int x, int y, int i) {
this.x = x;
this.y = y;
this.index = i;
}

public int getSum() {
return x + y;
}
}

public class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> res = new ArrayList<int[]>();

if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
return res;
}

PriorityQueue<Pair> minPQ = new PriorityQueue<Pair>(k, new Comparator<Pair>(){
@Override
public int compare(Pair a, Pair b) {
return a.getSum() - b.getSum();
}
});

for (int i = 0; i < nums1.length; i++) {
Pair cur = new Pair(nums1[i], nums2[0], 0);
}

while (k > 0 && !minPQ.isEmpty()) {
k--;
Pair cur = minPQ.poll();
if (cur.index == nums2.length - 1) {
continue;
}
else {
minPQ.add(new Pair(cur.x, nums2[cur.index + 1], cur.index + 1));
}
}
return res;
}
}
``````

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