SPEAKER 1: This is the first problem that we're going to be working on.
I'll read it out.
"Let's define a rotated array as assorted array
where the numbers have all been rotated to the right some number of places,
with numbers wrapping around when they reach the end."
For instance, if you've got the array 1, 2, 3, 4, 5 and you rotate that three
times, you're going to get 3, 4, 5, 1, 2.
The problem here, is given a rotated array,
find the number of times it was rotated.
SPEAKER 2: All right.
Well, hi, Tommy.
How are you doing?
I'm Connor.
SPEAKER 1: Good.
Nice to meet you, Connor.
How's your day going?
SPEAKER 2: It's going pretty well.
And yours?
SPEAKER 1: Awesome.
Not too bad.
It's pretty sunny out here in San Francisco,
which doesn't happen too often.
SPEAKER 2: That's great.
Yeah, it's pretty warm out here for October in Cambridge.
SPEAKER 1: Nice.
All right, well, thanks for taking the time.
Let's jump right into the question.
You've got the Replit open.
That's great.
Notice that you've selected Python there.
Is that the language that you want to use for this?
SPEAKER 2: Yes, it is.
SPEAKER 1: Perfect.
That works for me.
Here's the question that I'd like you to solve.
"Let's define a rotated array as a sorted array
where the numbers have all been rotated to the right some number of places,
with numbers wrapping around when they reach the end."
For instance, if I give you the input 1, 2, 3, 4, 5,
you should return back 3, since--
or, sorry, when I rotate that three times,
you should return back 3, basically, as you've written in the comment there.
That's the question that I'd like you to solve.
SPEAKER 2: OK, yeah.
That sounds good.
I'll start out by asking some clarifying questions, if that sounds good to you.
SPEAKER 1: Yeah.
SPEAKER 2: Just to make sure, it does say "given a rotated array" here.
I just want to clarify that something like this right
here would be our input.
So I don't get this original array at all,
I just get the rotated array as input?
SPEAKER 1: Yep, that's right.
SPEAKER 2: All right.
And then my other clarifying question is, in this one,
all of these are consecutive integers--
1, 2, 3, 4, 5 all right next to each other.
Can I assume that that will be the case, or might there
be a case where my original array is, like, 1, 3, 4, 7, 10?
SPEAKER 1: Yeah.
That could exist.
They're not necessarily consecutive, but they are sorted.
SPEAKER 2: OK.
Yeah, that's good to know.
In that case, let me just look at a couple of examples,
just so I can see if we can start to see a pattern here.
We see, when we get this first example, we want that to map to 3,
because we're rotating that one three times.
Let me see, if I were to rotate that one more time,
then it would look like 2, 3, 4, 5, 1.
That would be as if I had rotated it four times.
And then I'll try some ones with different numbers.
If my original array has some different numbers in it,
a rotated one might look like 6, 8, 12, 1, 3.
In this case, we would have rotated it--
1 would have been the original one.
We've rotated it 1, 2, 3 times.
So we would also want this one to return 3.
And then just one more kind of edge-ish case is, if it's not sorted at all,
I'm assuming that we would want to say that that was rotated zero times.
SPEAKER 1: Yes, that's right.
SPEAKER 2: Just to check in, do all of those cases seem good to you?
SPEAKER 1: Yeah.
Nothing else you'll probably run into here.
SPEAKER 2: All right.
Great.
In that case, let me go ahead and run through looking for patterns.
I can see just how I would figure this out,
if I was looking through this as a human, is I would go to the first one--
and I guess the important thing I'm looking for is, all of these numbers
are increasing.
And I want to look for the first time that they decrease,
so they start going down.
In this case, I go to 0.
I go to 1.
It's increasing.
I go to 2.
It's increasing.
And then when I get to element 3, it's decreasing,
which means it's rotated three times.
And then just to verify that, I'll go through this one.
In this one, I start at element 0.
Then 1.
It's still increasing.
2, still increasing.
3, still increasing.
But at 4, it decreases again.
I think that is a pretty good pattern to use there,
is that when we get to an index, when it starts decreasing,
that's the index that we want to return.
SPEAKER 1: Yeah.
That looks exactly right to me.
Yeah, that point where it goes from increasing to decreasing is the index.
That tells you the number of times it's been rotated.
SPEAKER 2: All right.
Perfect.
In that case, I think I'll go into writing
some code if that sounds good to you.
SPEAKER 1: Yeah, let's do that.
SPEAKER 2: All right.
I'll go ahead and define a function here.
I guess I'll just say get_rotate_number.
SPEAKER 1: Sure.
Sounds good.
SPEAKER 2: And it's going to take in this array.
Ah, that looks like it might be reserved.
So I'll take in a list ls.
And now, I want to go through all of the elements in ls.
And the index is important here.
So I guess I'll go ahead and say, for i in range ls.
And now, what I want to do is, for each i--
when I'm here, i is 2.
I want to compare it to the one before that and see if it's less than that.
Let me-- I guess I would say something like,
if ls bracket i is less than ls bracket i minus 1--
we're saying, if my current element is less than the element
before that, then I would go ahead and--
I know that that's the place that I want to stop.
So I can go ahead and say, return i.
And now, looking at this special case here where nothing happens,
I guess I would go through this entire list and never get to that point.
I guess, if I finish this whole thing--
so I don't find any point where an element is less than its predecessor--
I'm going to go ahead and return 0, since I know
that the list is not rotated at all.
Now, just as a sanity check, I'm going to go through this
with this first example here.
Acting as the computer, I take in ls, which is this list I've highlighted.
And then I go ahead and say, for i in range ls--
that's going to start me off at 0.
And I'm going to say, if ls bracket 0, which is 3, is less than ls 0 minus 1
is going to be ls bracket negative 1, which is this 2 here, which
I guess will not be a problem here.
Because if 3-- the only case when this first element
is going to be less than the last element
is when the array is not rotated at all.
So I would want to return 0 in that case.
That actually makes me think that I may not need this "return 0" at the end
here--
just kind of a peculiarity of Python indexing,
where if I say ls bracket negative 1, it's
going to be the last element of the list, instead of giving me an error,
like it might in C, or Java, or some other programming language.
SPEAKER 1: Yeah, [? think so. ?] Hadn't thought of that,
but I think you're right.
SPEAKER 2: All right.
And then finishing going through that example, for this one,
it would start out at 0 and see that 3 is, in fact, greater than 2.
So it'll continue.
It'll get to this one.
It'll say that 4 is greater than 3, so it will continue.
It'll get to 5, say 5 is greater than 4, so it'll continue.
But then, when i is 3, we'll see that ls bracket i is, in fact,
less than ls bracket i minus 1.
So we'll go ahead and return i, which is 3, which is as expected.
Just running through it as a human, that seems to work.
Now, let's move on to writing some tests.
I can go ahead and say--
I'll just print one out first to verify.
I'll go ahead and say, print get_rotate_numbers
of our first list here.
And hopefully, this will end up with 3, so I can go ahead and run my code here.
And we've got a problem here where I'm saying,
"list object cannot be interpreted as an integer."
Oh, OK.
And I think what's going on here is, I can't just say for i in range lists,
because range has to take in an integer.
So I actually have to look at the length of the list--
SPEAKER 1: Yeah, that's right.
SPEAKER 2: --instead.
Now, I'll go ahead and try that again.
All right.
Nice.
That's looking pretty good.
That's looking like it's printing 3.
And then I'll just go ahead and try with our other lists here.
Hopefully, this second one should translate to 4,
this third one should translate to 3, and this last one
should translate to 0.
And we'll go ahead and run that.
And it looks like I added--
oh, I forgot a
SPEAKER 1: Yeah, just [INAUDIBLE] open bracket there.
SPEAKER 2: --bracket here.
I'll run that.
And it looks like--
SPEAKER 1: [INAUDIBLE] Looks right.
SPEAKER 2: --that has given us the result we want.
That's looking pretty good to me.
I guess I'll check in at this point and see
if there's anything that you notice about this,
or any other corner cases you think I should try out.
SPEAKER 1: Yeah, this looks right to me.
What is the runtime of this?
SPEAKER 2: Yeah, of course.
Going through the runtime, since I'm going through i in range length of ls,
I'm going to go through this loop a maximum of n times if there's
n elements in ls.
And then just accessing elements of a list in Python is O of 1,
and comparing to integers in Python is going to be O of 1
in terms of the size of the list.
This whole operation inside the "for" loop is going to be constant time.
So I'm going to say that the entire runtime is going to be O of n.
If there are n elements in the list, it will take a maximum of n times.
SPEAKER 1: Yeah, I think that's right.
Can you think of any ways to make it faster?
SPEAKER 2: Yeah, let's see.
If I'm working on making it faster, I wonder--
I guess any way that we could make it faster would be to--
hmm.
I'm actually a little bit unsure, because going through it as a human,
I can't think of anything else I would do than go through each element.
So I I'd love know if you have any hints, if you could nudge me
in the right direction a little bit.
SPEAKER 1: Yeah.
Keep in mind that the list is sorted.
Even though it's rotated, we have this property that it's sorted.
Is there any search we could use that leverages the fact that it's sorted?
SPEAKER 2: We could use--
generally, with the sorted list, we could use just a binary search.
If we're going through and doing that, then how
would I apply a binary search to this problem?
I guess I could--
let's see.
If I go through kind of the motions of doing
a binary search with a problem like this, I would start in the middle
and see that I've got of size 5 here.
I guess I would have to look at the first element first,
see that my first element is a 3.
And then when I head to the middle, I see that I'm
at size 5, which means that when--
it's been increasing since then.
Which means-- I guess, at that point, I can go ahead and narrow my search down
to the latter half of the list after I've checked that one.
And vice versa.
If I, let's say for-- what's a good example?
For this one, if I start at--
or I guess a better--
I guess I don't have a great example for that one.
But if I were to get to a point where I was checking this 3 here,
then I would know if I'm checking at this 3,
I know I can just look at everything before the 3.
Yeah, I think a binary search would be able to help us out there.
Just want to check in time-wise.
Is it all right if I go ahead and try and implement that,
or do you think we should move on?
SPEAKER 1: Yeah, let's try to implement it quickly,
and then if we run out of time, that's totally fine.
SPEAKER 2: Yeah, sure.
Let me leave this other one here, just to have something to reference.
And now, this newer version here.
I don't necessarily want to go through each i in this range.
I want to go ahead and say my--
let's see.
I only care about when I'm going from a high number to a lower number.
So I'll go ahead and say that my highest number that I've seen so far
is going to be the first element in the list, is ls bracket 0.
And then I can go ahead and say that my lowest element that I've seen so far
is--
we can go ahead and look at the last element of the list,
because I know it's going to be somewhere in between--
or I guess we don't necessarily know that's the lowest.
Let me think about how we would want to initialize those.
5.
If that is the lowest, then--
yeah, I guess I'll just start out with 0 and go
through kind of the logic of this.
Although, I think I'm going to actually want--
if I'm looking for an item that is lower here,
I'm also going to want to keep track of the indices that I'm working with.
Does that seem like it's going to be on the right track?
SPEAKER 1: Yeah.
I think, in general, you'll probably want to look at the left--
keep track of the left and right endpoints of the search
so then you can compare wherever you land on in the middle
to those left and right endpoints.
SPEAKER 2: Yeah, that's a good point.
Let me go ahead and say that left, for now, is going to be 0, the first index.
And then since we're starting our search with the full list,
our right is going to be the length of the list minus 1.
And then what I can go ahead and say--
I can go ahead and, instead of having this whole "for" loop here,
I can say while right is greater than left--
so while we're still working on converging in--
then I'll go ahead and say that my current index is
going to be equal to right plus left divided by 2.
Let me get some parentheses in there.
That will take the middle element.
And then since we're working in Python, I
realize I should probably do some integer division here.
That will get us our current index that we're working with.
And then I can go ahead and say--
and let me look at this example to see what we should do.
In this example, if our current index is greater than the index on the left,
then I know I can narrow my search to the right half.
If ls bracket current--
if that current number is greater than ls bracket left,
is greater than the left number, then I can go ahead
and I can narrow down the search to this right half of the list.
I can go ahead and say that left equals current.
And then I can go ahead and say, otherwise,
if ls bracket current is less than ls bracket left,
then I can go ahead and say right equals current.
I know that we are going ahead and changing our rightmost there.
And let me-- now, we just kind of have to work
on what happens after we do narrow in on that case.
Let's go through the example with this top one again.
We get to this point with this 5 here.
And so now we know that our difference is going to be between 5 and 2.
And actually, now that I'm thinking of--
yes.
We're looking between 5 and 2 here.
So our left, at this point, is going to be 2, and our right is going to be 4.
Now, our central one is going to be 1 here.
Now, since 1 is less than 5, we would hit this case.
And so we would say right equals current.
Now, our left is going to be 5 and our right is going to be 1.
We know that we're ending here when our right one is just 1
more than our left one.
Let me go through what the example would do in this if left is 2,
as we have here, and right is 3.
When left is 2 and right is 3, our current is going to be 3.
This is going to say, if current is greater than the left one-- which isn't
true, because they're the same thing.
And then we'll say, if current is less than the left one, which
isn't going to be true because they're the same,
then we can have an "else" statement here.
And if it's an "else," then we know that this current one
is kind of 1 below where we want to do.
We can try and return our right here.
Now, just running through another example as kind of a sanity check,
we'll take this one here.
Let's say-- our left is 0 to start.
Right is 4.
We can find the one in the middle, which is going to be element 2.
And then we're going to see that 2 is greater than our left.
That means that we're going to narrow our search down to these last three
elements here.
And now, we're going to go ahead and say that--
yeah.
Now, we're going to go ahead and find the middle element here, which is 1.
And we'll say that left--
yeah.
This is our current.
And then we're checking, is current greater than left?
No, that's not true.
Is current less than left?
Yes, that is true.
So we're changing our current to this--
or, we're changing our right to this.
Now, we're just looking at this section here.
These are our left and right.
And when we compare left to current and right to current,
they're both going to be the same thing.
We get this "else" here, and we return what's
on the right, which is 1, which should be correct.
Just basic conceptually-wise, it looks like things are working out here.
Let me run through it real quick with the un-rotated array
to see how things are going there.
In this case, we're going to get to this middle one.
We're going to see that right is greater than--
or yeah, the current is greater than the left.
We'll get to this one here now, and we'll
see that the right is still greater than the left.
Our current is still greater than the left, so our left is becoming this one.
And now, we're going to go ahead and say the left is still going to be this one.
So that's not going to give us the right answer here, it looks like.
SPEAKER 1: Yeah, I think the stop condition you're looking for,
sort of in that first example, you can see, with the 1, the number to the left
is bigger and the number to the right is bigger.
That's kind of the stop condition for your search.
Otherwise, though, I think the binary search is right.
SPEAKER 2: Oh, OK.
Yeah, that makes sense.
Maybe I can go ahead and check that condition.
If we're looking at our current one, we would--
would we-- do you think, for each time, we would look at our current and check
if it's smaller than the left one and greater--
smaller than the left one and smaller than the right one?
SPEAKER 1: Yeah, that seems right.
SPEAKER 2: And then it--
OK, sure.
We're already checking if our current is smaller than the left one here.
I can go ahead and nest a little bit of "ifs"
here and say, if our current is also smaller than the one--
oh, OK.
Sorry, sorry.
But we're not looking at direct neighbors there.
So let's look at direct neighbors up here.
That would look like if ls bracket current minus 1
is less ls bracket current, which is less than ls bracket current plus 1--
which is a nice thing we can do in Python,
is just combine these different inequalities.
And I'll take away those parentheses for now.
In this case, we know that current is the one that we want to return.
So we can go ahead and return current here.
And then let me just do another sanity check.
Would these--
SPEAKER 1: Yeah, I think this looks this looks basically right.
Just for time, we're basically at time.
But yeah, overall, this search looks pretty good.
SPEAKER 2: All right.
SPEAKER 1: Awesome.
Well, thanks for taking the time for chatting with me today,
and have a great rest of your day.
SPEAKER 2: Yeah, thanks.
It was great to meet you.
SPEAKER 1: Awesome.
See you later.