Hi, everyone.
So in this lesson, we are going to solve this question, remove duplicates, inanity, so this example.
So this is basically and ready and what we have to do.
So basically we have to return a veteran of integers and in this kind of integers.
So this is the vector.
So in this integers element will appear only once.
They will be all unique elements inside this vector.
So let me show you.
I would put one it here then to.
Then three.
Then, too, is coming again, so, too, is already present inside the Taketo then when so when it
already present, take five.
You're going to take for.
You cannot take one because one is already present and you cannot take three because he's already poisoned,
so this will be my output.
OK, so one, two, three, five and four.
So if you will notice.
So this vector is basically containing all unique elements.
So that is the meaning of removing duplicates, so in this area, duplicates are present, but it will
see the vector.
All elements are unique elements.
And one more thing to notice, elements are appearing in the same order by same order.
I mean, so one is coming before two in the original also.
So one was before two.
Similarly, five is coming before four because in the original Eddie five was coming before four.
So that is the meaning of same order.
So what we have to do so given this integer Eddie.
We have to find this vector, we have to generate this vector that will contain all the unique elements
and in the same order.
Now let's see how we can solve this question.
So when you're solving this question is very simple.
So what do you do?
You pick one element and then you will search whether this element or not.
If it is not present, then you will push.
Similarly, the second element check it is present inside the vector.
Not if it is not present, then you can push a device, not push similarly.
But the third element.
And then I read all the vector and check whether it is present or not present.
So in this we will be able to solve this question now with the time complexity, if we will use this
approach.
So.
So this is my indigeneity, this input, so this is an area.
And if you will follow the above approach, so whatever time complexity, so this is my vector, so
initiate the vector is containing zero elements.
So you pick the first element, you will check that is empty so you can push this element.
So when work is done now, pick the second element.
So you will like to order Vector to check whether this element is present or not.
So basically.
The amount of Ogborn, similarly, you will pick the third element, so you will agree to whatever it
is, pleasant or not.
Similarly for the net element, so.
For the entertainment, what do you have to read over the computer to check whether the element is present
or not so invoke, you have to perform and work because you have to write it or the computer actor to
check whether this element is present or not.
So what does the time complexity.
So if you will add all this.
So and plus and minus one, plus and minus two, it will go until one and we know.
So this is basically off and square and big off and square.
So time complexities.
Big off and square.
Now, how can we optimize our time complexity?
So basically what we are doing, we are picking one element and then we are searching over the computer
vector to check whether the element is present or not.
So if we can perform the searching in Question Time.
If he can perform this routine constant, then our time complexity will become so picking every element
and then checking whether it is present or not so and multiply one.
So that means the time complexity will become linear if we can do the searching in the vector in constant
time.
So here, what is it?
Time, complexity.
So you are picking each and every element and then you have to search inside the vector so and multiply.
And so this is for picking every element and this is for searching inside the vector.
But I am saying if we can perform the search in Question Time so the time complexity will become linear
because and and how we can check in Question Time, basically we can use we can take the help of MAP
because in map searching is constraint time and certainly search.
All three operations are constant in an order to map.
If you will use the map, then insert, delete, search, all your patients will take longer time.
So in this question, what do we lose?
We will lose in order to map.
Now many people can say, why does it matter?
We can also solve this question with the help of Eddie, so how we can solve this question with the
help of Eddie.
So consider this example only.
So what do you do, you will find out the maximum, so five is the maximum element.
And now what you'll do after find out the maximum element, you will make an array of size five plus
one.
So five is the maximum element to make an area of size five plus one.
So the size of that, it will be five, six.
This is five.
And this is zero.
And basically this area will be a bowling alley roof area.
Now, what do you do?
You will check when it's present.
So inside when initially this area will be initialized with false.
So I will check when I go to one.
It is false.
So basically you can push it inside the vector and make it through.
No, if the next time when will come, you will see here you will check or Wennerstrom.
So do not push inside the vector.
So definitely you can use this approach.
Let's take one more example, for example, three, so I will check, you will go to three.
So initially, this building that is initialized with force, you will check all three is false.
So you will push three.
But the next time three will appear and we will also make it through.
We will also make it through after pushing inside the vector, we will make it through.
So when the next time things are coming, you will go to the next three and you will check No.
Three, Drew.
So basically you will not push inside the vector again.
So we can definitely use this approach.
We can definitely take the help of Belinelli, but the problem is considered you had in error is basically
of this size.
It is containing elements of this type then then then to power three then then to power six then then
to power seven and so on.
So what you have to do.
If you will follow this approach, what is the maximum limit, so 10 to the power seven is the maximum
limit and obviously the elements are debating.
So then the power three, then to power six, then again, tend to power seven.
Obviously, there are duplicates now in order to you.
So I'll just caution using this method, this is the maximum limit.
So basically the size of the area, the billionaire will be able to sustain to power seven plus one.
So this will be your alley now.
This is very huge.
Speace, very, very huge, huge space.
OK, so this is wrong.
Now, one more thing.
The elements can be negative also.
Integer can be negative, so I can have minus 10.
So how can you store minus 10 here, minus 10 index does not exist, minus 10 index will not exist.
So that means this approach has a lot of limitations.
If that is basically off, if there is containing elements of these types and also if that is containing
negative element, then you cannot use this approach.
So basically we have to use map in this case.
Now, if you are using map, you can definitely do something like this.
My map of minus five is true.
You can definitely do something like this.
Similarly, you can do my map of to power seven is true, not my map of 10000.
Doesn't mean that your map is often to power seven sites.
We will see the implementation map will take very, very small space maps will take very, very small
space.
So it doesn't mean the size of the map will return to power.
So no, it will be very, very, very, very large as compared to the areas.
And one more thing.
So this is in digit area.
So we are talking about indigeneity now in the question if there was connectivity.
If there was crack berry, for example, if there was characters like it, then C, C, then D, B,
so if instead of a degenerate character it was given, then definitely what can do.
You can make an array of size 256.
And obviously, this area will be a billionaire.
And you can use this approach, for example.
So go to index 97, so initially this was false.
What you will do, so you will see false.
You will push inside the vector and then you will make it through.
Similarly, when you will come again, you will go to index 97.
So this is true.
Then do not push it again, see?
So go to index ninety seven ninety nine and it will check.
It is false.
So you will make it through, you will push AC and so on.
So basically if the correct area was given you can definitely use this boolean area approach.
But since we have in beta that an integer can be very big and indeed it can be negative also.
So we have to use map in this question so that our time complexity can be linear.
OK, so how can we use map?
So it is very, very simple, so considered a very small example.
So consider above an example.
So what we will do so I have this goes like this in your area.
So one, two, three, then two, then one, then let's say five for one and three.
So what will do?
I am going to construct a map.
So let's say the name of map is my map.
Give a key will be element and there will be basically true or false.
So what we will do so pick the first element.
Not so initially.
My map is empty.
So this is map.
So initially, members is empty, no check, so one percent inside the map, no, it is not present.
So what you will do, you will push one and one or two.
So the value of one is true and it will push one inside the vector now, too.
So to present inside the map.
No.
So push two and make it through now three.
So three plus inside the map.
No.
Then push inside the map and make it through.
So obviously when you will push inside the map we will also push inside the vector.
So you will also push inside the vector.
So this is the vector that we have to return.
OK, now again, two is coming.
So two is already present inside the map.
So do not do anything one.
So one is already inside the map.
Do not do anything.
Five five is not president.
Then you will push five inside the map and you will also push five inside the vector then four.
So far it is not pleasant inside the map, so you will make it through and they will push for inside
the vector.
Then again, one so one is present then three.
So Ts present and this will be your answer.
This will be, Warren said, OK, so searching in map, so we will use dart count function as discussed
in the previous video.
So this time complexity of current function is constant.
If you are using an order to map and if you are using map, then the time complexity will be log-in.
So we will use on our road map so that time complexity is constrained, so with the help of MAP, we
can solve this question in linear time.
Now, let us write the code for discussion.
A piece of code is going to look very, very simple.
So what we have to do, we have to return our function will return basically vector of integers and
let's say the name of the function is basically remove duplicates.
So what will take so this function will take and that is input and obviously it will take size also.
And then do you have to do so, let us first create our vector of.
So first, let us create our output vector of integers and output so it will contain all the unique
elements and in the same order.
And now let us also create an order to map.
So key will be element.
It will be deja.
And they will be basically boolean value, true or false?
And let's see the name of my is my map.
So you can see yourself, so the structure of my map is very simple, give a loopier.
So she's going to be element and element as integer and this is going to be true or false.
So basically, boolean value key and integer and boolean.
Initially my map is empty, then you have to do so.
Now let us over the so I equals zero.
I understand and I placeless.
Now, first, let us search whether this element is present or not, so I will use common functions
so my map does not count.
So what it will take, it will take as input.
Basically, Miss Element element is integer.
So if if I equals equals zero.
So I told you can't function will only return to things zero one zero means not present.
So if the element is not present inside the map that means it is coming for the first time.
So if it is coming for the first time, you will push it inside your vector because it is coming for
the first time.
So output push pushback.
And also you will push it inside the map.
So my map dart bush.
--, my Amapa, and that's great because so Alphie.
Is basically true.
OK, so this is key and this is value, so Elfy is key and this is value.
So if is true.
And finally, what you can do, you can return your vector.
So return output.
Simple, now let us create an error here and let us do our program.
So let's give the elemental.
So this is the.
Edit And now let us call the function.
Selecter and outpoured.
So the name of the function is remove duplicates.
This function will take at as input and what is the size of the area?
So two, one, two, three, four, five, six, seven, eight, nine, 10, 11 and 12.
So they are total 12 element.
So size of that is 12.
And now let us bring our vector so that we can see the output so close to zero.
I listin.
Outpoured says.
I placeless.
No, first, before running this program, let's see what our output should be.
So when when is coming for the first time, then five is going for the first time, two is coming for
the first time, for what is coming for the first time, will not take this four, then three is coming
for the first time.
So we will not take this three, we will take six, we will also take seven, we will not take one and
we will not take one, we will not take two.
So they should be our answer.
When five to four to six, seven one, five to four to six, seven Solarte.
Yurtseven Applebaum.
OK, so basically we have to include Victor, we have to include an order to map, so instead of including
these two, we can write.
So now let's on the program.
OK, so my blood count.
What is the idea?
So if my map.
Not Count Elfy.
OK, so the name of that is.
So let's change the name.
The name is Enno.
So this is the output when five, 246, seven, so our output is right as discussed when five to four
to six, seven.
So all the elements are unique and elements are appearing in the same order.
Now, let us discuss what is the time complexity of a solution.
Now, what we are doing here, so we are just editing all the data and basically the scoring function
will be constrained by this pushback will take time and this inspection will take constant time.
So our time complexity is basically linear.
Now, if you are using map, so instead of using an order to map, if you will use map, then what will
happen?
So this current function will take a long time and social function will also take longer time.
So time complexity will become and login.
So this is the time complexity, if you will, use map, and this is the time complexity, if you will
use an online map.
And this is my output, so all the elements are unique and elements are appearing in the same order.
So you can see when five, then two, then four and then three, six and seven.
So one, five to four, three, six, seven.
So I hope you understood this code.
I hope you understood this question also.
I will see you in the next one, and if you have any doubt, you can ask me.
Thank you.