Hi, everyone.
So today we are going to solve this question, find the first and the last position of a given element
in a sartorially.
OK, so let us take example.
Let us consider example and try to understand this question.
OK, so this is basically our input.
So input will be added and that it will be Assad today.
OK, so input basically Assad today and we will be given a target element and we have to find this targeting.
We have to find the first and the last position of this element.
OK, so let us consider this example.
So five is the target value.
So what is the first position and what is the last position?
OK, so the first position.
So this is index zero.
One, two, three, four, five.
OK, so basically the first position is indexed to so first is two and the last is basically the next
five.
So last year and next five.
OK, now let us consider this example.
So the target value is basically seven.
So the first position of seven is zero.
One, two, three, four, five and six.
OK, so first position is six and last position is also six.
Now, let us consider this example.
OK, so the target value is basically eight, so zero one, two, three and four.
So basically the first position is three and the last position is basically food.
Now, let us consider this example.
OK, so the target value is basically six and we can see basically six is not present inside this area.
So first position is minus one and last position is also minus one.
Minus one basically means does not exist.
OK, so this is our coalition and this coalition is basically present only told.
OK, so this is the question that we are going to solve.
OK, now let's see how we can solve this question.
OK, so let's see how we can solve this question.
So let us bright in on this example.
OK, so what we will do.
So suppose I have a target value and this target value is that it will exist inside the.
And either it will not exist, there are two options.
OK, so if it doesn't exist, then my answer would be minus one first point and last point, also minus
one.
Now, if it exists now, there are two options.
It can be duplicates or they can be only one element or only one unique value.
So since the area sorted, so basically the first the very brute force approach for solving this question
is linear such.
OK, so what we will do, we will simply iterate over the area and we will check whether the target
exists or not.
OK, so what do the time complexity for using the linear search so that time complexity will be linear.
OK.
And space complexity will be open.
OK, so this is their time and this is the space, but the problem with linear is it does not consider
the fact that the given area started.
OK, so the given area is sorted since the governor is sorted.
So we can apply binary search.
We can apply binary search.
OK, now let's see how we can apply by new search.
So what Minnesota uses, for example, this is your already.
Now, first, let us think about simple binary search.
OK, so simple by necessity 2.0, start pointer and pointer, try to find the midpoint, which is basically
a start plus.
And why do now compare the midpoint with the target value.
And if you find and if you find the midpoint, which is the target value, you can simply return the
midpoint.
OK, so this is basically a simple binary search.
Now this question is basically a modification of binary search.
OK, so what will happen?
So if you let's say you want to find the first position.
OK, so if you want to find the first portion, let us consider an example.
So let's say there are some elements, then we have a target value.
Then let's say again, we have target value again, we have target value again, we have target value
and some more and some more elements inside the array.
OK, so we have to find the first position.
Basically, we have to find the index.
OK, so we have to find the index at this point.
So how we can solve this problem.
So again, will take 2.8, let's say this is my starting point and let's say this is my end point.
There again, we will find out the mid, which is and I think it will be simply start plus and by OK
again, we will do the same step.
We will compare mid and target.
So I'm comparing within Target, let's say this is my mid.
OK, so let's say this came out to be mid.
Now, in the simple binary search, I will return from here, but this is the modification of my research.
So what we will do so if this is made, I will store my answer here.
OK, so I will temporarily stole my answer.
So let's say I have another variable.
So I'm suddenly close to the middle, which is basically the index.
So I will store the index, but I will not return anything.
OK, so I will not return anything here.
What I will do, I will remove and from here and I will put end here, OK.
And I will do one more operation and equals minus one.
OK, since we have to find the first position.
So obviously if I came here that means this can be our answer.
OK, but we have to find the first portion.
That means I have to consider the left part.
OK, I have to search in the left part.
OK, so I have to do this operation and the climate minus one.
Now, if you want to find the last position, OK, consider this one example only.
So you have some elements, then you have target value, then you have target value, then you have
target value, then you have target value and similarly some more elements.
OK, so suppose this is start and this is basically end and you came out with this one.
OK, so again, what I will do, you will find out the method, which is nothing.
It is basically start plus and bitou again.
You will compare it with Target.
So I am comparing what with I'm comparing like with Target and then also what you will do, you will
store your answer.
So answer the question.
And one last thing.
So since I have to find the last Oaklands, so basically the last Oaklands will be present at the right
hand side of the mid value.
OK, so what I will do, I will do start equals murder plus one.
OK, now one thing, I am storing the answer.
OK, so I am storing the answer basically.
Suppose there does not exist.
There is only one value.
OK, so there is only one target value.
There are not duplicates.
So what will happen at this point.
Suppose you are here.
So basically you will store your answer in the variable answer and then you are searching in the right
and say, OK, I'm searching in the right hand side.
And obviously we have only one value.
So in the right hand side we will not be able to find any value.
So that's why I have stored my answer in a variable answer.
And finally, what will do?
We will return answer.
When development and similarly, I hear I will return answer when my wife Lupin's.
OK, so that's how I will be able to find the first and the last occurrence.
OK, so now let us write the code for this, OK?
So let us write the code.
So you can implement yourself, but there is no need to implement a so let us basically implement the
binary such approach.
OK, so by search there will be an index, there will be integer because I Willetton Index, basically.
OK, and let's say the name of the function is get first, get first position.
OK, so get first.
What it will take, so it will take basically a week Peres input and obviously our target value.
So that bears input and it will take our target value.
OK, so first, let us write the simple binary search approach so I have to take two point to start
engines to start is basically zero and we have and pointer, which is basically a start size minus one.
Then our standard by such gold, so while the start is less than our request to end, would have to
rule, you have to find the midpoint.
So my point is basically start plus and buy to what you can.
Right.
I have told you that another way.
So that either way is very simple.
So and plus start plus and minus start by doing OK.
So this is basically same as start plus and by two.
OK, so this one is better because in this case, in digital jihad, we did OK.
So after calculating them, it would have to do I have to compare the mood of the target value.
OK, so let's compare.
So if basically Nimsoft murder equals equals target.
It was staggered then what I have to do so in the original by such I will return it from here.
OK, so first I am writing the original my new search, then I will modify the by search.
OK, and the elusive part.
So if.
Mid.
So if murder is basically less than target.
Then what I have to do, so if the murders Lester Target, so what I have to do, I have to start Goldschmid
plus one, so I have to search in the right hand side.
OK, so we start Goldschmid plus one.
And India, the part of what I will do, so I will write and equals minus one.
OK, so this is our standard by Newswatch, now we have to modify our binary search and how we can modify.
So what I have to do, I have to.
So when I get the call condition for finding the first position, I think the first finding the first
version I will do.
And the ultimate minus one.
OK, I have to search in the left hand side.
I have to search in the left hand side for the first document.
OK, so and I also need one variable answer.
OK, so let's create a variable answer.
So I have a variable answer, which is initially minus one.
OK, now I will not return.
OK, so this is the modification.
I cannot return.
I will first save my answer.
So I'm saving my answer made.
And then I have to search in the left hand side for the first position.
So I will do an equal number to minus one.
OK, so we have to search in the left hand side for the first version.
OK, allergist's left hand side for the first position.
And finally, what I will do so when the loop ends, I will return my answer, I will attend the first
operation and now let us write the code for the.
Last also.
OK, so I'm writing the code, so get first, then the function will be get lost.
Get lost position, it will also take no target and what will the condition so.
The only difference will be so instead of searching the left hand side, I will search in the right
hand side for the last position.
So basically, I will start equals less one.
I will start equals plus one.
OK.
Now, let us call these functions body functions from here.
So what I have to return, you can see I have to return a vector.
OK, so Vector will contain two values.
The first operation and the last portion you can see I have to return a vector of two elements.
First position and the last version.
OK.
So let us create a vector.
So, Victor, of integers, let's say, why it has to be a size two and let us initialize with minus
one.
OK, so I'm initializing our vector with minus one.
Now, let us call this function.
Get first.
OK.
So I'm calling the function get first, so in less time storing the indexing variable first, so I have
a function.
Get first, it will take vectorized input and it will take the target as input.
OK, so.
If first equals equals minus one.
So basically, element does not exist.
OK, so in this case, if the target is six, you can see the element will not be present.
So our answer will be minus one.
OK, so first is minus one.
That means the first politician is minus one.
That means the element does not exist.
So you can simply return later.
You can simply return.
OK, otherwise what you have to do, we will call, we will get to the last position.
So last is basically get lost.
It will also take.
That bears input and obviously the target value.
OK, and finally, I will put I will update my so zero to perdition will contain the first.
And the first petition will contain the last and finally I can return my answer so that be OK.
So I hope I have done everything correctly.
Now let us now accord and then we will try to submit our code, OK?
OK, so now let us try to submit our good.
OK, so our goal is working fine.
OK, now let's see how it is working.
OK, so I have a function get first position, so it will take a week, but as important, it will also
take the target value.
And then this is the standard code.
I will take this dart pointer.
I will take the pointer.
OK, so what I am doing here, so I will I am taking the start pointer, which is the next zero.
I am taking the end point which is index and minus one.
Then I'm calculating which is a start position by two.
Now I'm comparing with the target value.
OK, so after comparing it with the target value to this target and let's say this is our mode, OK,
so let's target then what I'm doing.
So I'm taking a variable answer, which is initially minus one.
Minus one means basically the element does not exist.
OK, so answer is basically, let's say this index is two, so answer will store two and then what I
am doing, I am doing and equals minus one so and remove and so and will be here so and equals basically
with minus one and then the binary search will be applied in this part.
So in this part we will apply the binary search.
OK, and suppose we have only one target value.
So in this part we will not be able to find any target value and this value will end.
And then I am returning my answer.
OK, so I return to.
Now, suppose if there is a target value present in the left hand side.
OK, so let's say this is a target, target, target, then what will happen?
So I will to my mother, basically this one.
OK, let's say this is the.
Then what I'm going to do here is so I will update my answer again to this Medders basically index.
But what I will do.
So this answer very well will be updated.
It will become one and then I will do an equal number minus one so and will be here and then I will
apply the bonus on this part.
OK, basically the only modification that we have to do with the bin searches do not return directly,
OK, after finding the target value, do not return directly searching the left hand side, searching
the left hand side and similarly for finding the last position, OK, for finding the last position,
do not return directly.
So if the method is basically cultural target value, then do not return anything.
OK, first store the temporary answer and then search on the right hand side.
And for searching the return site, I have to do start equiptment plus one.
OK, search on the right hand side for the last value.
So basically do not directly return.
OK, so what do we the time and the space complexity since we are using binary search.
So the time complexity is basically logoff in and our space complexity is basically outdraw one.
OK, so this space complexity is basically order of one.
Now, in this part where we are calling the function, so what I'm doing here is so basically.
So basically, at this point, what will happen, but this land will lose, it will create a vector
with the Navy and Vector can store only two elements.
So the first and they are initialized with minus one.
So it is minus one and minus one.
OK, and then I'm calling our function.
Get first.
So get first.
Will I get it done.
Minus one.
That means the element does not exist or it will return the first position of the target value.
So if it is returning minus one, ok, if it is returning minus one, that means the dagger does not
exist.
So there is no need to call in this function because it will also return minus one.
So that's why I am returning V from here and which is basically minus one and minus one.
OK, so if this is not the case, that means the target element is better inside the array.
And then I'm getting I'm calling the function get lost.
It will return me the last position.
It will return with the last position and then I am updating my vector.
OK, so this will contain this is V of zero.
So this is indexical, this is the next one.
So this will contain the first position and this will contain the last position.
And then I am returning V OK vs basically vector and you can see the return type of the function, this
vector.
So that's why I am returning vector.
OK, so what you can do here is so you can see this function, get lost function and get first function,
so the only difference between these two function is this line and the consumer minus one.
And here I am doing start a quantum replacement.
OK, so this is the only difference between these two functions.
So what we can do is write a general code.
So let me show you first.
What I'm going to do here is.
So let us come and let us copy this part and then I will come and dirtball dysfunctions.
And then let me show you how we can write this code in a better way.
OK.
So this is basically the gold and I want one function and that one function will return me the first
position and the last position.
So let's say the name of the function is good index.
OK, so it will take one more argument and that argument is basically a boolean value.
Basically search for first or let's get first.
Get first.
OK, so and let's say by default, this value is so if you know about the default value, you can ride
through here.
But let's say you do not know about default arguments.
So what we can do here is so instead of calling on end of minus one, so I will check first.
So I have to write if condition here, so what I'm going to do if.
Get first, basically this variable, so you've got first is true.
If great first is true, what I'm going to do, I will do and equals minus one.
Symbol in the old part.
What I will do, so I will do that article, smart person.
OK, so search on the left hand side for first position.
Now, if the first is false, what I will do, I will search on the right hand side for last position.
And instead of calling these two different function, I have one function only then able to function
is to get index.
And I will start arguing.
OK, so if I want to find the first valuate, I will pass, I will pass through and here, since I do
not want to find the first value, I will pass false.
OK, I want to find the lost value.
So as you can see here, we have only one function get indexed.
OK, so I have to change the name of the function here.
The name of the function is get indexed, it is taking vector, it is taking a target value and it is
taking a third argument which will be true or false.
OK, so that argument is basically true or false.
So if the third argument is basically true, what I will do, I will do.
And a classmate of mine, this one, because we have to find the first portion.
And if the third argument is false, basically you can see if the argument is false, we have to find
the last position.
So we're finding the last person I will do start equals my plus one.
OK, so let's try to separate alcalde.
OK, so compilation of.
OK, so there will be when Brexiteer.
No, legitimate.
OK, so our goal is working fine.
OK, so with the help of this third argument, we do not need to write to functions.
So here we have written two functions and the only defense is basically this line between these two
functions.
So to avoid writing two functions, what we can do, we can pass a third argument.
And with the help of third argument, we can write a health condition and then.
We can't go like this, OK, so this is a better way to write the code.
OK, so what is the time in the space complexity?
So basically, since we are using the brain research time, complexity is basically log in and the space
complexity, we are not using any extra space.
So it is our draughtsman.
OK, so this is basically binary search for linear search.
The time complexity was when and this vast complexity was 01.
OK, so this is linear search.
OK, so if you have any doubt in this question or do you have any doubt in the court, you can ask me,
OK, thank you.