[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.