10:I[13699,["/_next/static/chunks/6b91a202b724e571.js","/_next/static/chunks/6710f67d945945a1.js","/_next/static/chunks/bde5ef9330c4de2d.js"],"default"] 11:I[25152,["/_next/static/chunks/6b91a202b724e571.js","/_next/static/chunks/6710f67d945945a1.js","/_next/static/chunks/bde5ef9330c4de2d.js"],"default"] 12:T41f,class Solution { public List> kSmallestPairs(int[] nums1, int[] nums2, int k) { int m = nums1.length, n = nums2.length; List> ans = new ArrayList<>(); Set visited = new HashSet<>(); PriorityQueue minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]); minHeap.offer(new int[]{nums1[0] + nums2[0], 0, 0}); visited.add("0,0"); while (k-- > 0 && !minHeap.isEmpty()) { int[] top = minHeap.poll(); int i = top[1], j = top[2]; ans.add(Arrays.asList(nums1[i], nums2[j])); if (i + 1 < m && !visited.contains((i + 1) + "," + j)) { minHeap.offer(new int[]{nums1[i + 1] + nums2[j], i + 1, j}); visited.add((i + 1) + "," + j); } if (j + 1 < n && !visited.contains(i + "," + (j + 1))) { minHeap.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1}); visited.add(i + "," + (j + 1)); } } return ans; } }13:T483,class Solution { public: vector> kSmallestPairs(vector& nums1, vector& nums2, int k) { int m = nums1.size(), n = nums2.size(); vector> ans; set> visited; priority_queue>, vector>>, greater>>> minHeap; minHeap.push({nums1[0] + nums2[0], {0, 0}}); visited.insert({0, 0}); while (k-- > 0 && !minHeap.empty()) { auto top = minHeap.top(); minHeap.pop(); int i = top.second.first, j = top.second.second; ans.push_back({nums1[i], nums2[j]}); if (i + 1 < m && visited.find({i + 1, j}) == visited.end()) { minHeap.push({nums1[i + 1] + nums2[j], {i + 1, j}}); visited.insert({i + 1, j}); } if (j + 1 < n && visited.find({i, j + 1}) == visited.end()) { minHeap.push({nums1[i] + nums2[j + 1], {i, j + 1}}); visited.insert({i, j + 1}); } } return ans; } };

Time Complexity

Space Complexity