# Java Priority Queue or without Priority Queue

1. With Priority Queue. Scan [k+1, 2K] pair. Heap size is [2, k]. O(klogk) time, O(k) space
2. Without Priority Queue. O(N^2) time, O(1) space
``````    final int[][] neighbors = {{0, 1}, {1, 0}};

public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> sPairs = new ArrayList<>();
if (nums1 == null || nums1.length == 0 || nums2 == null
|| nums2.length == 0 || k == 0) return sPairs;

int len1 = nums1.length, len2 = nums2.length;
boolean[][] visited = new boolean[len1][len2];
visited[0][0] = true;
PriorityQueue<int[]> pq = new PriorityQueue<>((int[] pair1, int[] pair2)->
(nums1[pair1[0]] + nums2[pair1[1]]) - (nums1[pair2[0]] + nums2[pair2[1]]));
pq.offer(new int[]{0, 0});

while (sPairs.size() < k && !pq.isEmpty()) {
int[] currPair = pq.poll();

for (int[] neighbor : neighbors) {
int nums1pos = currPair[0] + neighbor[0];
int nums2pos = currPair[1] + neighbor[1];
if (nums1pos < 0 || nums1pos == len1 || nums2pos < 0 || nums2pos == len2 || visited[nums1pos][nums2pos]) {
continue;
}
visited[nums1pos][nums2pos] = true;
pq.offer(new int[]{nums1pos, nums2pos});
}
}

return sPairs;
}

public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> sPairs = new ArrayList<>();
if (nums1 == null || nums1.length == 0 || nums2 == null
|| nums2.length == 0 || k == 0) return sPairs;

int len1 = nums1.length, len2 = nums2.length;
int[] nums2idx = new int[len1]; // map to last used element in nums2
while (sPairs.size() < k) {
int minSoFar = Integer.MAX_VALUE;
int nums1pos = -1;
// find smallest pair
for (int i = 0; i < len1; i++) {
if (nums2idx[i] >= len2) {
continue;
}
if (nums1[i] + nums2[nums2idx[i]] <= minSoFar) {
minSoFar = nums1[i] + nums2[nums2idx[i]];
nums1pos = i;
}
}

if (nums1pos == -1) {
break;
}

nums2idx[nums1pos]++;
}

return sPairs;
}
``````

• Priority Queue

PriorityQueue is a Heap, you can use heapsort to sort the k max/min elements without creating new O(k) space.

• @nasacj Correct! Updating original post.

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