[MUSIC] So we've worked through this example and now we really understand the task at hand. And so it's good before we do the solution to just reaffirm what the assumptions that we're making are. And at this point, we know that our array is given to us without any information about how it's organized and it may have some duplicate elements. But we're allowed to change the array as we proceed with the algorithm. And so, we're looking for the kth smallest element. And what we might want to do is build up to the kth smallest element by looking for the smallest element and then the next smallest element and then the next smallest element after that and then keep on going until we've gone to the kth one. We notice that that's somewhat similar to the procedure that we have to do for selection sort. And with selection sort, we find the smallest element and we swap that to a first position of the array so that we can think about ignoring it afterwards or discarding it in some sense. And then we focus on the rest of the list and find the smallest element among those remaining elements, swap that to the beginning, and then just keep on focusing on the remaining elements. And this would give us an algorithm that's a variant of selection sort that we already know. And so it's always nice when we can use our previous knowledge to inform design of future algorithms. But before we go ahead and code this solution, let's analyze it to see if it's worth coding. Because it was just our first hunch at how we might solve this problem. And so it's good to stop and think and evaluate before we go further any one direction. And so if we evaluate the performance of this approach, what we're doing at each point is finding the minimum element of an array of numbers. And if we wanted to find the minimum amongst an array of elements, what we have to do is look at each one of those elements. And that takes linear time. And so even though the number of elements that we're considering each time decreases by one, we still might be doing this, we still are doing this k many times. And so, for really small k, if we just need to find the very smallest element or the second smallest element, in that situation, this would give a linear algorithm. But in the more general situation, where k maybe is n/ 2, and we're finding the element that is right in the middle, the median, then if we have to do this approach, say n/2 many times or any O(n)many times, then all of a sudden our algorithm becomes quadratic. And that's a problem. Because quadratic algorithms, they're kind of slow, especially if our problem has something to do with sorting. And so we've already seen how the algorithm that were devising is related to sorting, in the sense that it's related to the selection sort algorithm. And so maybe we can use that insight to come up with a better solution. And so what if we sorted the array before doing anything in terms of finding the kth element? And as a preprocessing step, let's just apply our favorite sorting algorithm and organize all the elements from smallest to biggest. And the advantage of doing that is that, at this point, the element that we care about, the kth smallest element, is in position k in the array. And accessing an element in a particular position in the array is a constant time operation. So overall, we've now come up with an algorithm that takes however long a sorting takes for the preprocessing step. And then O(1) time for the second step which is retrieving that kth smallest element. And the advantage of having these two separate steps is that sorting is a really well studied problem and we know that in the worst case there are still algorithms out there that solve sorting with n log n time. And so that's a really big improvement to quadratic time. And so we're feeling pretty good that we've made a pretty dramatic improvement to our original naive approach to solving the problem, and now we have a slightly less naive approach. And at this point, we might be feeling comfortable enough with this approach to go and code it on the whiteboard. And so that's what we'll be doing next.