Find K Pairs with Smallest Sums | BRUTE FORCE ACCEPTED | GOOGLE | Leetcode-373 | Live Code

This is the 10th Video on our Heap Playlist.
In this video we will try to solve a very good Heap Problem "Find K Pairs with Smallest Sums" (Leetcode - 373)

Share your learnings on LinkedIn, Twitter (X), Instagram, Facebook(Meta) with hashtag hashtag #codestorywithmik & feel free to tag me.

Trust me, this will no longer be a MEDIUM Problem. I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.

We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Find K Pairs with Smallest Sums
Company Tags : GOOGLE

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[souravjoshi]

I wish you were in my college bro. We need teachers like you 😥

[NamanSharma-zxgq]

Bhaiya I regularly watch your videos and my problem solving is also increasing because of your tutorials, please start posting leetcode weekly and bi-weekly contest solutions as well 🙏

[jayantmishra]

Bro kya samjhaya hai yrr, ek no., love you.

[Raj]

such a nice explanation tysm => i coded it own and passed all testcases

[Shawarmaseem]

Very nice explanation! I just had this question in a coding assesment yesterday. Weird coincidence that you uploaded the soln for it yesterday too. Cheers!

[shohanur_rifat]

Thank you so much vi ! Crystal clear explanation.
Subscribed from Bangladesh.

[agarwalyashhh]

I used this approach only at the beginning but it gave tle after 29/30 cases

[raisanjeeb]

Improved bruteforce ka time complexity kya hoga ??0(n*m*logk) se kam hoga ye to smjh aya par exactly kya hoga ye kaise pta krenge ??


PS:- Mainr brute force try nhi kiya kyuki lga o(n2) tle aajyega but Thank you for explaining ki ye bhi ek optimization hai

[kshitijpandey]

The JAVA code:

class Solution {
class Data {
int a;
int b;
int sum;

public Data(int a, int b, int sum) {
this.a = a;
this.b = b;
this.sum = sum;
}
}
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<Data> maxHeap = new PriorityQueue<>((a, b) -> b.sum - a.sum);
for(int i=0; i< nums1.length; i++) {
for(int j=0; j< nums2.length; j++) {
Data data = new Data(nums1[i], nums2[j], nums1[i]+nums2[j]);
if(maxHeap.size() < k) {
maxHeap.offer(data);
}
else if(maxHeap.peek().sum > data.sum) {
maxHeap.poll();
maxHeap.offer(data);
}
else {
break; // This must be noted that the once the sum exceeds the heap top we dont want to traverse completly till the j pointer till the end..
}
}
}
List<List<Integer>> ans = new ArrayList<>();

while(!maxHeap.isEmpty()) {
Data polledData = maxHeap.poll();
List<Integer> list = new ArrayList<>();
list.add(polledData.a);
list.add(polledData.b);
ans.add(new ArrayList<>(list));
}
return ans;
}
}

[aayushranjan]

APKO VIDEO KE TITAL ME PART 1 MENTION KAR DEN CHAHEY THA

[ugcwithaddi]

Cleanest solution . Better than leetcode

[FARMAAN]

Bhai i am 1700 at Codeforces mai tumari yha awaaz sunne aata hu konsa microphone use krte ho

[aswithasai]

efforts🤌thank you for such clear explanation

[lakshsinghania]

bhaiya, now this approach is failing on 29/3- test cases
optimized sol dimaag mei aa hi nai rha

[FreeFire-rdfy]

Only 26/35 case passed in java is there any faster way

[animesh]

```
class compare{
public:
bool operator()(const pair<int, int>& p1, const pair<int, int>& p2){
return
}
};
class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
for(int i=0;i<nums1.size();i++){
for(int j=0;j<nums2.size();j++){

if(pq.size()<k){
pq.push({nums1[i], nums2[j]});
}
else
pq.pop();
pq.push({nums1[i], nums2[j]});

}
else{
break;
}
}
}
vector<vector<int>> ans;
while(!pq.empty()){
ans.push_back({pq.top().first, pq.top().second});
pq.pop();
}

return ans;
}
};
```

[ridj]

aapki explnation acchi hai but bohot lengthy videos hoti hai iss problem ki saari approach k liye 45 mins dene pade.

[santoshmore]

Hey can u please tell me is it possible to apply same logic in javascript

[xiaoshen]

Maine 2 pointer se kiya, galat h kya?

[bssuhin]

Could u please provide JAVA solution for the same in description, if possible?