[MUSIC] All right, let's dive into an example where we need to solve some problem and so by the end of this video series you're going to have worked through a full example using the strategy that we talked about last video. All right, so here's the question. We're given an array of integers and we would like to find the kth smallest integer. All right, that's it. That's the problem, now we have to solve it. So our first step is to ask lots of questions. Try to understand as much as we can about the task at hand. And so I'm going to leave it to you. In the next quiz, please try to think of however many relevant questions you might have that would clarify this problem, take it from there. Welcome back. I hope the quiz gave you an opportunity to think about which questions would be useful to you in solving the problem. And it's a bit of an art form trying to understand which questions you want to ask, that will clarify the problem but still be relevant and useful to you once you learn about the answers. So here are a few that I came up with. When we want to think about finding the kth smallest element of an array, we want to make sure that we are on the same page about what smallest means. Do we mean smallest magnitude or do we mean smallest on the number line? And this is relevant if we have negative integers in the array. So for example, if we have negative a thousand, that's got a very high magnitude but it's very much lower on the number line than say the integer one. So we want to just make sure that we're on the same page with the interviewer about what they're intending from the question. We also want to ask things about the structure of the array and what we're allowed to do with it. Are we given the array as a pre-sorted collection of elements, are they already organized? Or is that maybe up to us to decide how to to organize these elements? And speaking of which, when we're deciding what to do with those elements, are we allowed to change the array as given to us? Is it mutable, are we allowed to change it in place or do we need to make a copy of it? And then manipulate it as we see fit. Also about the array, it's useful to know if there are duplicate entries. Do we need to think about possibly some array elements having the same value? In that case, what do we exactly mean about kth smallest? Do we mean the kth smallest distinct value? Or do we mean the position sorry, the number in the case position when we order all the array elements including duplicates? And so this is something we would want to clarify with the interviewer. Going along with that question when we're talking about kth smallest, we want to make sure that we understand how k behaves. Are we starting the indexing at 0 or 1? And so we want to look at each of the words in the questions being asked. And really dig dip onto that word and understand how it's going to relate to the solution that we worked. So now that we've understood the problem very well, it's usual to work through an example with not too few but not too many array elements so that we really confirm all the answers to the clarifying questions that we've asked. So it's good to think of an array example that has some of the possible strange behavior that you would expect if you want to maybe take into account negative integers. You might want to take into account 0, some positive integers. And this example is going to assume that our interviewer said there are no duplicate entries. But if he or she said that there might be duplicate entries, then you definitely want to take that into account, in the example that you work through. But right now, we're going to assume that there's no duplicates in our array. So we plop down a few numbers and now we ask ourselves, what would the solution, the expected response to our algorithm be if k were to be, say, 1 in this array of integers? And if k is 1, then we're looking for the smallest array element in this given array. And so we scan through the array elements and we see that the smallest value is -3. And so that would be our expected response. And then we could ask well what if k was 2? Well then, our problem is asking for the second smallest element and so we don't want to output -3 anymore, we want to output the next smallest which is 0. And one thing that's useful to do as you're working through this example is think about how you as the human is solving the problem for the small example. And keep in the back of your mind how would you generalize this strategy and write it down systematically, so that an algorithm could perform the same tasks. And then last but not least, we also want to think about some edge cases in this example. What would be the highest value of k that would make sense? And the highest value of k that would make sense would be the number of elements that we're given to begin with. Because if we ask for the eighth smallest array element in this collection, then what we are really asking for is the biggest element and so that would be 42 for this small example. And so as we're thinking through these cases, we might recognize it to ask for the eight smallest element is really asking for a symmetric problem about the largest. And so that might already get your wheels turning about a possible optimization later on in our algorithm. And we'll come back to that later, but first we're going to do the next step in our strategy which is just the naive implementation of brute force solution to the problem. So that's coming up next.