QFind K Pairs with Smallest Sums - LeetCode
Mon Jan 30 2023 06:07:38 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
//make a priorityQ and add either first K elements or till < nums.length
//also add the index of the element with which all combinations have been made
PriorityQueue<int[]> minheap = new PriorityQueue<>(
//making comparator for pq
(a,b) -> ((a[0]+a[1]) - (b[0] + b[1]))
//this will make a minheap PQ
);
//add first k elements or till elements
//if k requires us to print every element this will add all combinations with first element and if condition in 2nd loop will handle for printing all the pairs
for(int i = 0 ; i < k && i < nums1.length ; i++){
//making k combinations and also storing the index of nums2 with which
//combinations have been made
int temp[] = {nums1[i] , nums2[0] , 0};
minheap.add(temp);
}
List<List<Integer>> res = new ArrayList<>();
//now iterating k times or till minheap is empty
for(int i =0 ; i <k && !minheap.isEmpty() ; i++){
//removing smallest sum and adding to answer
int[] curr = minheap.remove();
res.add(List.of(curr[0],curr[1])); //List.of will create a list
int index_nums2 = curr[2];
//now adding combination with current smallest element in nums1 and next
//element of nums2
if(index_nums2 < nums2.length-1){
int[] temp = {curr[0] , nums2[index_nums2+1] , index_nums2+1};
minheap.add(temp);
}
}
return res;
}
}
content_copyCOPY
https://leetcode.com/problems/find-k-pairs-with-smallest-sums/solutions/?orderBy
Comments