Table of Contents: Dissing A Binder I Found 0:00 - 0:08 The Problem Introduction 0:08 - 1:06 Merge 2 Sorted Arrays (The Intuition) 1:06 - 3:18 Merge K Sorted Arrays (The Intuition Scaled) 3:18 - 5:11 Cool but...How Do We Code This? 5:11 - 6:09 Walkthrough With A Min Heap 6:09 - 8:47 Time Complexity 8:47 - 10:26 Space Complexity 10:26 - 10:44 Subscriber Begging 10:44 - 11:05 The code for this solution is in the description. Although for arrays, it can easily be adapted and applied to work on any type of list (like a Linked List).
@Trinitrophenylnitramine Yeah I'm a student right now and yeah you learn algorithms and data structures very fast but for me pretty much all of these questions are from self studying. And great, I wish you luck!
People would actually think of either Merge sort or Heap sort which would result into N*log(N) complexity but this technique actually made use of the sorted arrays, implemented both sorting techniques and reduced the complexity to N*log(K). Amazing tutor. Thank you!
I'm slowly learning to teach better. I think the key to these questions is just that. The solution will not come often. You must build on what you know to get there. That is how I wanted to teach this problem and how I approach all my teachings. Thanks for dropping by.
excellent explanation!!!! u r amazing This sure will be the largest and the best resource for all the programmers in the coming years. Cant believe two morons disliked this video.I am so angry at them.
Awww you have helped me a lot, was exploring this solution for a long time but didn't find a preety clear and explained vdo on RU-vid, then I got your vdo really awesome man:) You deserve my subscribe 🙌🏻
@@BackToBackSWE Yes I am preparing for an internship but I am afraiding of lots, I would get it or not 😐 also create a video on how to get a referral for product companies plz 🙃
thanks for the video , one small suggestion: dont move rapidly in front of camera , specially when the focus is too close . that will blur the images and kind of discomfort to viewer .
My first lazy approach was to merge them without giving a fuck and then just quicksorting, which allowed me to reuse the quicksort function the interviewer already asked for previously.
yes, but you want it to be iterative, inserting all n items and removing each would be n log(n) insertions then n log(n) removals so O(n * logn) vs O(n * log(k)) where k is the total arrays to be merged. When k
Great explaination. Merge sort algorithm internally uses 2 pointer algorithm for 2 sorted arrays. For K arrays use min heap concept which is an extension to 2 pointer algorithm for getting the least element from the heap . Thats what you have told correct ? Thanks :D
shouldn't the time complexity be O(k + 2n*log(k)), where the additional k accounts for the time it takes to build the initial min-heap structure? because the video only accounts for the insertion and deletion of each element from the heap. unless of course you are assuming that k is dominated by 2n*log(k) in which case you can omit it...
@@BackToBackSWE 7:05 how does the heap know from which array we got the element? Should we keep array of k pointers each point to the current element which we are comparing and then incrementing like kpointer[0]++ to check next element of that array?
class Element { int value; int row; int index; public Element(int value, int row, int index) { this.value = value; this.row = row; this.index = index; } } class Solution { //Function to merge k sorted arrays. public static ArrayList mergeKArrays(int[][] arr,int K) { // Write your code here. ArrayList res = new ArrayList(); //Declaration of Min Heap, which sorts based on its value PriorityQueue min_heap = new PriorityQueue(new Comparator() { public int compare(Element a, Element b) { // if both the values are same then compare on the basis of their index if((a.value - b.value) == 0) return a.index - b.index; return a.value - b.value; } }); //Basis Step -> The first element of each row must be added to the min heap from where we can perform our calculation for(int i = 0; i < arr.length; i++) { if(arr[i].length > 0) { min_heap.add(new Element(arr[i][0], i, 0)); } } /*From each iteration we select the minimum element present in the heap, and whichever element we selected, we pop it from heap and then we need to add the next element from that array from which we selected an element (from the 2D array) into our heap*/ while(!min_heap.isEmpty()) { Element t = min_heap.poll(); res.add(t.value); int newIndex = t.index + 1; if(newIndex != arr[t.row].length) { min_heap.add(new Element(arr[t.row][newIndex], t.row, newIndex)); } } return res; } }
