Hi everyone, let's do this question.
You are given an array of integers sorted in non-decreasing order.
Now non-decreasing means it can be increasing or equal when you go from left to right.
All right.
Now it says find the starting and ending position of a given target value.
If the target value is not found in the array, return minus one comma minus one.
You must write an algorithm with O of log n runtime complexity.
So this is the question.
Now let's say this is the array which is given to you.
And the target is equal to two.
So you can see that we have two in this part right.
So the first two is occurring at index one.
So that's why the left extreme over here is one.
And the last two is occurring at three.
So we are returning three over here.
So the output should be one comma three.
So this is the question.
And then the caveat is it's mentioned that we have to write an algorithm with O of log n runtime complexity.
So that's the question.
Now again let's go ahead and write a few test cases.
And remember over here you have log n and there are a few indications that this is actually a variation
of binary search.
So that's one indication over here the time complexity has to be O of log n.
And we know that the time complexity for binary search is O of log n.
And then it's given that the array is non-decreasing it's sorted and it's non-decreasing.
So when something is sorted always remember try to use binary search.
In that case.
Now we have understood the question.
Let's go ahead and write a few test cases.
And remember when you're doing this in the interview you can always ask the interviewer if it's okay
whether you and he or she can come up with a few test cases together.
So this will help you ensure that you have understood the question properly, and are well aware of
the expectation to go ahead and solve the question.
So over here, let's go ahead and write a few test cases.
Now let's say the array is 12345 and the target is three.
So you can see that it's only occurring once.
So we just have to return this index over here which is two right.
This is 0123 and four.
So the first index and the last index where three is occurring is two itself.
So the output has to be two comma two.
Now what if the array is empty and the target is one.
So in this case one is not there in this array.
So the output has to be minus one comma minus one.
Now similarly let's say we have another array 57789 and the target is seven.
So in this case this index over here is one.
And this index is two.
Right.
So this is 0123 and four.
So that's why the output has to be one comma two.
Now if over here the target was let's say ten then we would have to return minus one comma minus one
because ten is not there in this array.
So this is the question.
All right.
So we have understood the question.
And we have formulated a few test cases.
Now we are ready to go ahead and think about solving this question.
So let's do that in the next video.