Merge K Sorted Arrays - Min Heap Algorithm ("Merge K Sorted Lists" on LeetCode)

Key Takeaways

yeah that's a note from me dog Jose no from me alright so in today's video we're going to cover how to merge k sorted arrays so it could be it could be any kind of list an array a linked list all that will change is how we deal with the structure it's not going to change how we solve the problem our input is going to be three sorted arrays this is key it's not a coincidence they're sorted they're going to be three sorted arrays and what we're going to do is we're going to calculate the union between these sorted arrays as another sorted sequence so we're going to output a sorted array from the three sorted arrays we get we're going to get K sorted arrays K is three in this case right there how are we going to approach this problem as always we start with the intuition we do not try to just jump straight into a problem attack it we see what do we already know what do we already understand how to do and how can we apply that to a problem generalized to K arrays so let's start with something you probably already know how to do right now so do we know how to merge two sorted lists if you're familiar with the merge sort algorithm this is something you should be able to do so how do we merge two sorted lists what is a best interest to us this is what we we create a pointer on the smallest item notice how we only care about the smallest item in each array that's for a reason and we're going to see how that generalizes to solve the case ordered array problem so now we have a point on each of these and what do we do we make a comparison between the two numbers that we have pointed to zero is less than three so zero gets the first placement and I want you to notice what I just did what I just did is I advanced the pointer to the six why did I do that I just extracted an item from the second array and now the next least item in the array we're comparing against is going to be six there's a reason we do that because we want to compare the least items between these two arrays because those are the comparisons that matter now we compare 3 and 6 which is less which gets placed 3 wins so now grab five five is next so so five is less than six five gets the placement and now we're comparing six and seven six gets the placement it is less and notice that we've out of bounced on the second array we have nothing to compare the other value to so we know every value in the array that has items left is going to be greater than the greatest value in the second array we've exhausted the second array now all we do is just add the values from the first array and now our iteration is finished we've merged two sorted arrays so now what did we notice let's not worry about how this is a small example let's worry about what we were thinking let's worry about what mattered to us what mattered to us was the smallest element in each array once we extracted that smallest element we moved on to the next element that we extracted that smallest element from we moved on to the next element in that array so how are we going to generalize this to K arrays let's look at how we're going to think about this and remember when you're in a high-pressure interview situation you won't be able to think to your fullest capacity this is just human nature like you cannot stress will dumb you down and make you think worse than you normally do but if you start with what you know we started with what we know two arrays and now we see where our brain went and now we can generalize our approach to three arrays these case ordered arrays so now what did we do we placed a pointer on all of the smallest elements in each array nothing different from sorting two arrays so now what do we do we take the smallest item between all three of these arrays which item is that zero we could take it from array two or three it doesn't really matter we could take it from array 2 so now again we're comparing the smallest items that have not been processed in every rate look at where our point is the pointer pointer pointer now what is the smallest item here it's zero in our eight three and now we're comparing three in our a 1 6 7 or 8 2 6 in our a 3 when we pull an item from an array because it's our smallest item we advance the next item in the array not different from what we already knew so now we take three from array1 it's the smallest item in our comparison now we're comparing five six and six five is the small site now we're comparing seven six and six six is the smallest item we can take it from a rate to or three let's take it from a rate and so now we have a ran out of elements in array - that's fine we're just comparing two elements now we need the smallest of these two elements six and seven we're going to take six from array three and now seven vs. 28 we take 7 from array 1 and now we have one element left and the smallest element compared against only one element is that element let's take it wait we just got an answer from what we already knew we already knew how to merge two sorted arrays we just generalize that approach the case order trades so we haven't done anything different we've just generalized what we already know to solve this problem generalize decay but there's a problem when I'm coding this I wonder when I have two sorted arrays yeah I can use pointers but there's a problem when we have a generalized amount okay how are we going to know these smallest elements between these arrays how are we even going to know how to advance ourselves the key here is to know our data structures and know we can use a min-heap to extract the smallest elements between these arrays a min heap will hold K elements at maximum you're gonna see how that plays into complexities but it will hold K elements at maximum we want these smallest elements between the arrays that's what our min heap will do and we're also going to use an iterator of sorts if this is a linked list you can easily grab the next value if these are arrays you need to create an abstraction where you can remember what array you pulled the item from when you put it into your min heap so let's see how the min heap approach would work now we have a min heap to work with we have our same arrays and we're gonna see how a min heap helps us with this problem we're going to do the exact same walkthrough but we're gonna see how the min heap is going to help us with this walkthrough to begin this algorithm we add the first items in all of the arrays to the min heap and the min heap gives us access to the smallest item between the K items we're going to insert you might not insert all K items because an array might be empty but we're going to have a max that's going to be our upper balance space for the mini so now let's do that insertion so now we see that the mini past three elements three zero and zero we're just gonna fetch the smallest element and grab the next element in the array on the mini we annotates the items we put in so we remember what array they came from if this is a linked list you're gonna have instant access to your next node you don't need to annotate anything but this is an array then you're going to have to do that what we do is we grab one of the zeros we're gonna grab a rate too we remove it from the min-heap added to our entry and now we remember that our item came from array two so now we can look at the next element in array two we see that it is 6 so we add 6 to the mini for remembering that is former a - and actually we won't even need those red arrows we're just gonna be working from the heap because those arrows were just to show that we are pointing to the stuff but heaped is going to handle everything for us because we annotate where the item came from now we pull the smallest item what is the smallest item 0 what array did it come from array 3 we add it to our answer it's removed from the heap we removed from the heap added to our answer and then we add the next element which is again we pull small sytem from the heap add the next item in that array small sytem is 3 or he comes from array what and so notice this is all we're doing we're pulling the smallest element our min-heap gives us that access is going to be a log K insertion because we're holding K elements and we're going to have to traverse the depth of the heap we pull 5 next from the min heap is from array 1 the next item is 7 so now we pull a 6 let's pull it from array to the next item in array 2 is nothing our min heap now has two elements we cannot add another element here so now all we do no trouble extract the smallest element from a mini the next item in our array 3 is 28 no trouble here extract the next smallest element 7 do we have another item in array 1 no we don't our min heap has 1 item now all we can do is extract that one item it is the min that's what we pull out and notice something we ran out of elements in all of the arrays our min heap is now empty what does that mean we have placed all the items and notice we have an answer now so that is how this algorithm works that is how you merge K sorted arrays let's look at the time and space complexity for this problem so let's go into that now we're going to assume we have eight Neri heap in a binary heap or it balanced any kind of binary tree structure we are going to have one plus the floor of a log number of items in the tree levels in this case we have K elements at maximum in our binary heap so we're going to have one plus the four of a log K levels okay is the amount of sorted arrays we're given and n is the total items across all case ordered array for all the elements across the case ordered arrays which is n items we're going to perform insertion insertion into a binary heap is going to cost us log K time log in time why because we have 1 plus the floor of law cave levels we're going to do that one so we're going to go across we're going to add all of the items and we're going to remove all of the items once from the binary heat so we know that we're going to do two times the work insertion is going to be log K and removal is going to be log K and the reason for that is when we remove an item from a binary heap we're going to replace that item with the farthest down and right left item you can search how how this is done but it's going to be log K because we need to bubble down that item to restore the heap property after an item is replaced you should probably research into that how insertion and deletion from a heap works but let's continue we're going to do that twice and the elements are going to be inserted and elements are going to be new and this is across our whole algorithm so we're going to do that twice constant factor out and our complexity becomes n log K for each element we do log K work and this is how the complexity pans out we drop constants this space at maximum we're going to hold K items in the heap we're going to hold the smallest item in every array at maximum how many arrays do we have k so what max our heap is going to hold K items that is o of K space that is our upper bound on space so this is time and space for this solution if you liked this video if this helped you with this question subscribe to the channel like this video I want to do more videos like this anyone that's this helps them that really encourages me to do more of these and I see this channel as a way of giving back for them subscribe like this video and [Music]