[MUSIC] So, at this point we're going to switch to slides, but I don't want you to switch the computer. And so what I mean by that is that when you're thinking about practicing these algorithmic problem solving on the fly, it's really important to try to make the situation as realistic as possible. And white boarding is something that we as programmers don't do very naturally. We don't often write out code on the whiteboard when we're developing a new program. And for the future practice problems that we invite you to do, we really, really, really encourage you to be as far away from a computer as you can. Be at a whiteboard or at a piece of paper taped up on the wall, and actually write out what you would be doing as though you were in the interview situation with someone next to you, helping you practice. Or role playing in a room, making sure that you have that authentic experience that will get you prepared. Okay, so at this point what we're going to do now is go further in the algorithm that we're developing. And, if you think back to what we did, we sorted the whole array before picking out the kth smallest element. Can we probe the solution, and can we really think about optimizations? And for example, maybe we don't need to sort the whole array, maybe the array is a huge chunk of memory, but we only care about k that is on the order of millions, not billions. And so what could we do if we were in that sort of a situation? And so at this point, you want to brainstorm and see what are other strategies we have for coming at that kth smallest element. And one data structure that we have that helps us keep elements in a somewhat organized fashion is a max-heap. And so, we know that in a max-heap, we have this tree structure whose root is the maximum element. And so, if we're looking for the kth smallest element in a group, and we have all k smallest elements arranged in a heap, then the root of that heap will be the kth smallest. It will be the biggest amongst the k smallest. And so maybe what we can do is build a heap of size k, where we want to make sure that the elements in that heap are the k smallest overall. And so let's think about how that would work with an example. We don't want to have all of the elements in our array in that heap. That heap would be too big. We just want to focus on the k smallest, and we're really taking advantage over here of the difference in magnitude between k, which is the rank that we're looking for, and the overall size of the array. And so if we restrict our heap to just three elements, say if k = 3. Than we might walk along our array and insert elements into the heap. And so we insert 17, that first element, into the heap. And then we insert the next element 42. And of course 42 becomes the root because it's bigger than 17. And then we insert 0 as well because we need three elements in our heap. And now we go ahead and look at 5. And we want 5 to be in our heap as well because it's smaller than 42, it's smaller than 17. And so it is a candidate for being one of the three smallest elements and that's what the heap is trying to capture, the three smallest elements overall that we've seen so far. And so what we're going to do is to swap out the current maximum element in the heap, remove it from the heap and put 5 in instead. And so 5 goes in and it has to go in, in its correct location so we still have a heap structure. And the advantage of that is now the 17 gets put to the root and so if we find some small element later on then we know that we're going to remove the biggest element in our current heap and put in the smallest element. So that at each stage we have, the heap is containing the three smallest elements that we've seen so far, and the root is the maximum of those. And so, we continue, we look at 10, and it's gotta go in instead of 17. We look at -3, it's gotta go in, but now 5 becomes the root, and we keep on going with 2 and with 9. And at this point we notice that our heap has three elements and so the third smallest element in our whole array is going to be the root of that heap, and that's beautiful because we can just read off the root of the heap. And,so, what we've done here is we've used a somewhat fancy data structure, but a very standard one that we have in our back pocket that we're prepared for. And we've used this property that the root is the maximum element of all of the elements in the heap. And that's helping us to solve this problem. And so this is a nice strategy. It's nice also that we're demonstrating some creative problem solving, some flexibility. So we're not focused on one particular problem solving strategy, but we're demonstrating that we're thinking about different avenues. And at this point, we might go ahead and code up this strategy. Now, this is a lot of code, and it would probably take us a few minutes to develop it on the whiteboard. What I want to focus on is that as we develop this code, we notice that we're using some data structures. And in those data structures, we're demonstrating that we're familiar with some Java libraries like the Collections library, like PriorityQueue. In particular, when implementing a max-heap, we need to reverse the order of the competitor and so we're demonstrating that we are relatively sophisticated programmers. We also wanted to test and analyze our new strategy. It's great that we are creative and came up with a new one, but we also want to see if we made any progress, if it performs any better than our very, very simple sort and then pick off the kth element strategy. And so, we can look through our code and look for where do we have function calls that take some time and how does the performance depend on k and on n. And what we notice is that at the beginning stage for the first k elements of the array, we're just adding each one of them into the heap. Add, add, add, put them into the heap. And then afterwards, we're only adding into the heap if the current array element that we're looking at is really smaller than the maximum element at the root of the heap. And only at that point do we swap the current element into the heap. Now in each of those situations, we have to do some heap operations we're adding into the heap and we're removing the root of the heap as well. And so here it's important to know that heap operations like insert and remove take time that's logarithmic in the size of the heap. Because we might have to traverse all the way down to the bottom of a path and the maximum length path, it could be at worse log the size of the heap log, the size of the tree. And so we see that we're doing these operations. We're doing a constant number of these operations for each array element that we're looking at and so all in all, this algorithm is going to have performance that's O( n log k). And that's interesting because we can compare this performance to what we had before. And again, we're demonstrating our critical thinking, our analysis of the two algorithmic approaches that we have. And before we had an algorithm that was O(n log n), and now we have O(n log k). And so we've made some improvement if, in particular, k is going to be much smaller than n but still grows, and so we still want to take that into account. So this is a very very different problem solving strategy from the first one we saw. And we might go even further and that's what we'll do next.
