LeetCode | 373. Find K Pairs with Smallest Sums | Priority Queue | MaxHeap

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

#leetcode #dsa #priorityqueue #minheap

[nishadevi]

Please keep making videos like this! 🙌You explained so clearly.

[AkGautam_]

Time complexity would be maximum O((linear times)logk) as both the arrays are sorted so break condition will encounter very early.
dry run this case as this is the case where i guess the maximum number of comparisions will be there but still you can see it will break soon.
[1, 1, 1, 1]
[1, 2, 3, 4]

so i think it will be okay to say O(nlog(k)) in interview.
Please correct me if i am wrong.

[sidforreal]

you can avaoid more if else statements, Just keep pushing the emelents in PQ, when size become more than K, pop the top element
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
pq.push({a[i] + b[j], {a[i], b[j]}});
if(pq.size() > k) pq.pop();
}
}

[shivanshdwivedi]

what will be the time complexity of above code?

[kumarutkarsh]

The daily challenge today. I had thought of the same approach. Using max Heap... All I was missing was else break; It was giving TLE on test case 26 Thanks..

[sumitsinha]

explained well brother but put title using MaxHeap

[akshatkhandelwal]

Won't it print [[1, 6], [1, 4], [1, 2]] instead of [[1, 2], [1, 4], [1, 6]]? Since we're using max heap and for example 1 the top would be 1, 6 followed by 1, 4 followed by 1, 2

[aviralpruthi]

You are checking only top element, while inserting new pair and break the loop if sum greater than topmost element sum
But still that new sum can be less than some other elements sum present in heap