Find K Pairs with Smallest Sums | OPTIMAL | GOOGLE | Leetcode-373 | Live Code

This is the 11th 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)

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.

In Video-10, We already solved it using :
1. Brute Force - TLE
2. Improved Brute Force - ACCEPTED

In this video, we will go with an Optimal and another better approach.

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

[kishan.]

Love u bro super understanding ❤️..pls keep making videos ❤❤❤

[udaytewary]

Some body have great knowledge and some body have great teaching skills

But u have the both really thankyou bhaiya for ur so smooth and easy teaching

[Raj]

Optimal solution se BFS ka vive aa rha :) nice solution and explanation Optimal one is really good generally hum yhi sochte hai heap ke question me ki smallest nikalna hai to max heap use karenge lekin ye thoda diff tha

[AlishaKhan-wwio]

You are the best YouTube teacher I have every found

[prajwalshaw]

Hello sir. Please add sliding window median(leetcode 480) to your list. It's a hard problem combining the concepts of fixed sliding window and two heaps pattern. The solution in the leetcode discuss section is very confusing. Would love your explaination of this tricky question. Thanks for your videos though...they are really helpful:)

[prajwalshaw]

sir leetcode 621 ..task scheduler plz. It's a confusing one.

[FARMAAN]

Bhai mai Codeforces pr 1700 hu lekin mai sirf aapki awaaz ka fam hu konsa mike use krte ho itni bdiya awaaz aati h

[ridj]

the examples weren't clear in this video like teh earlier one, had me confused ina lot of examples

[ugcwithaddi]

I am ready to pay. Teach me everything 😅

[surajsidar]

I wrote above code using java
All the test cases are not passing (but same code written in C++ is working)


class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {

PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
int m = nums1.length;
int n = nums2.length;

Set<int[]> visited = new HashSet<>();
int sum = nums1[0] + nums2[0];
pq.add(new int[] { sum, 0, 0 });
visited.add(new int[] { 0, 0 });
List<List<Integer>> result = new ArrayList<>();

while (k > 0 && !pq.isEmpty()) {
int[] r = pq.poll();
int i = r[1];
int j = r[2];
result.add(Arrays.asList(nums1[i], nums2[j]));

if (j + 1 < n && !visited.contains(new int[] { i, j + 1 })) {
sum = nums1[i] + nums2[j + 1];
pq.add(new int[] { sum, i, j + 1 });
visited.add(new int[] { i, j + 1 });
}

if (i + 1 < m && !visited.contains(new int[] { i + 1, j })) {
sum = nums1[i + 1] + nums2[j];
pq.add(new int[] { sum, i + 1, j });
visited.add(new int[] { i + 1, j });
}
k--;

}

// result.sort((a, b) -> Integer.compare(a.get(0), b.get(0)));

return result;

}
}