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.