Hi everyone.
So in this lesson we are going to solve this question remove duplicates in entity.
So consider this example.
So this is basically alien Deja ready.
And what we have to do so basically we have to write down a vector of integers and in this vector often
digits.
So consider this is the vector.
So in this vector often teachers element will appear only once they will be all unique elements inside
this vector.
So let me show you what I would put one push ahead then two then three then two is coming again.
So two is already present inside the red pencil will not take two then one.
So one is already present.
Take five you're going to take four.
You can not take one because one is already present and you cannot take three because he's already present.
So this will be my output.
Okay 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 added obligates at present.
But if will see the vector all elements are unique elements.
And one more thing to notice elements that are appearing in the same order might seem or that I mean.
So one is coming before two in the original also.
So one was before two similarly five is coming before forward because in the original Eddy five was
coming before four.
So that is the meaning of the 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 we were solving this question is very simple.
So what do we do.
You pick one element and then you will search whether this element this peasant vector 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 otherwise do not push.
Similarly the third element and then I did or the vector and check whether this president does not present.
So in this we will be able to solve this question.
Now where did the time complexity if we will use this approach.
So so this is my DNA the input.
So this is an very and if you will follow the above approach.
So whatever time complexity so this is my vector.
So if you view the vectors containing zero elements.
So you pick the first element you will check that base and pretty so you can push this element.
So one bug has been no big.
The second element so you will activate all the vector to check whether this element is present or not.
So basically the amount of Ogden then similarly you will pick the third element so you will hydrate
or whatever triple check it is present or not.
Similarly for the net element.
So for the entertainment what we have to do you have to hydrate or the compute the vector to check whether
the element is present or not.
So invoke you have to perform and work because you have to edit it or the compute vector to check whether
this element is present or not.
So what is the time complexity.
So if you will add all this so N plus and minus one plus and minus two it will go on till 1 and we know
it.
So this is basically off and square and big off and square.
So time complexities big golf 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 compute
vector to check whether the element is present or not.
So if we can perform the searching in constant time if we can't perform this searching in constant time
then our time complexity will become.
So picking every element and then checking whether it is present or not so and multiply when.
So that means that time complexity will become linear if we can do the searching in the vector in constant
time.
So here what is the time complexity so you are picking each and every element and then you have to search
inside the vector so n 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 constant time so their time complexity will become Linear
B golf in and how we can check in constant time.
Basically we can use.
We can take the help of the map because in map searching is constant time insert delete search all three
operations are constant in and on the map if you will use the map then insert delete search all your
patients will take log time.
So in this question where do we lose we will use on a road map.
Now many people can see why use our road map.
We can also sort discussion with the help of Eddie.
So how against all this question with the help of Eddie.
So consider this example only.
So what do you do.
You will find out the maxim element.
So five is the maxim element and now what do 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 it will be a billionaire.
True False Eddie.
Now what do you do.
You will check when this present.
So inside one initially this ad it will be initialized with false.
So I will check one go to one.
It is false.
So basically you can push it inside the vector and make it through know if the next time one will come
you will see here.
You will check or when is true.
So do not push inside the vector.
So definitely you can use this approach.
Let's take one more example for example three so will check.
You will go to three.
So initially this billion that is initialized with force you will check.
Oh please false.
So you will push three but the next time t will appear and we will also make it through.
We will also make it true.
After pushing inside the vector we will make it through.
So when the next time ts are coming you will go to index three and you will check.
No trees true.
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 consider you are a clause that your
input error is basically of this size it is containing elements of this type then then turned to poetry
then then to power six then then two power seven and so on.
So what do you have to do if you really follow this approach what is the maximum element so 10 to the
power 7 is the maximum element and obviously the elements that are beating so tend to power to you then
tend to power sticks then again tend to power seven.
Obviously there are duplicates.
Now in order to do so I'll just caution using this method.
This is the maximum element.
So basically the size of the added the boolean that it will be of the size ten to power seven plus one.
So this will be your Belinelli.
Now this is very huge space very very huge huge space.
Okay so this is wrong.
Now one more thing.
The elements can be negative.
Also Indonesia can be negative so I can have minus 10.
So how can you store in minus 10 here minus 10 index does not exist minus 10 in next will not exist.
So that means this approach has a lot of limitations.
If that is basically of if that is containing elements of these types and also if that is containing
negative elements 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 5 is true.
You can definitely do something like this similarly you can do my map off tend to power 7 is true.
No my map of 10 about 7 desert means that your map is often 2 power seven cities.
We will see the implementation so map will take very very small space.
Map will take very very small space so 10 12 7 doesn't mean the size of the map will return to power
so no it will be very very loose very very loose as compared to that is.
And one more thing.
So this is in digit Eddie.
So we are talking about in digit Eddie now in the ocean.
If there was correct that Eddie if there was correct bet if for example if there was characters like
it then c c then the B.
So if instead of think digit edit correct that it was given then definitely what you can do.
You can make an array of size 256 and obviously this added will be a boolean Eddie and you can use this
approach for example.
So go to next 97.
So initially this was false.
What do you will do.
So you will see false you will push inside the vector and then you will make it true.
Similarly won't even come again.
You will go to index 97.
So this is true then do not push E again.
See.
So go to index 97 seven ninety nine and it will check it is false so you will make it through you will
push it C and so on.
So basically if the character was given you can definitely use this boolean idea approach.
But since we have a beta today and indeed it can be very big and indeed can be negative also.
So we have to use map in this equation so that our time complexity can be linear.
Okay so how can we use map.
So it is very very simple.
So consider it a very small example.
So considered above an example.
So what do we lose.
So I have this construct this integer area so one two three then two then one.
Then let's say 5 4 1 and 3.
So what will I do.
I am going to construct a map.
So let's say the name of map is my map.
Give a loop.
Key will be element and value will be basically true or false.
So what do we do.
So pick the first element no check.
So initially my map is empty.
So this is map so it usually map is empty no check.
So 1 percent inside the map.
No it is not present.
So what you will do you will push 1 and one adult 2 so the value of 1 is true and you will push a button
inside of it but no 2.
So to present inside the map no.
So push 2 and make it through no 3.
So 3 pleasantly inside the map.
No.
Then push 3 inside the map and make it through.
So obviously then you will push inside the map you will also push inside the vector so you will also
push inside director.
So this is the vector that we have to return.
Okay.
Now again 2 is coming.
So two is already present inside the map.
So do not do anything.
1 so 1 is already present inside the map.
Do not do anything.
5 5 is not president.
Then you will push 5 inside the map and you will also push 5 inside.
Direct but then forward.
So far it is not present inside the map.
So you will make it through and you will push forward inside the vector then again.
1 so 1 is present then 3.
So to use present and this will be your answer.
This will be your own set okay.
So searching in map so we will use guard 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 constraint.
So with the help of map begins all discussion in linear time.
Now let us write the code for this question.
A case of code is going to look very very simple.
So what we have to do we have to return our function will done.
Basically vector of integers and let's say the name of the function is basically remove duplicates so
what this function will take.
So this function will take an integer that is input and obviously it will take size also and then ready
have to do what it does first create our vector of so first let us cleared our output vector of integers
and output.
So it will contain all the unique elements and in the same order.
And now let us all to create an order to map so key will be element started given three digit and value
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 loop here.
So key is going to be element and element is integer and this is going to be true or false.
So basically boolean value so key and integer 10 billion.
Initially my map is empty.
Then what we have to do so now let us outraged over the array.
So I equals zero.
I list in a plus plus now.
Let us search whether this element is president or not.
So I will use common function.
So my map.
Dot com.
So what it will take it will take as inputs.
Key basically means element element is indigent.
So if if I equals equals zero.
So I told you can't function will only return two things.
0 and 1 0 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 not pushback.
If I and also you will push it inside the map.
So my map dart push slightly my map and this grid backwards.
So if I is basically true.
Okay so this is key.
And this is value.
So EFI is key and this is value so my map of EFI is true.
And finally where you can do you can get done.
You get a vector so it done.
Output
simple.
Now let us create an edit here and let us just start program.
So let's give the elements so.
So this is the edit and now let us call the function
selector and output so name of the function is remove duplicates
this function will take added as input and what is the size of the array so.
So one two three four five six seven eight nine ten eleven and twelve so they are total twelve elements
so the size of that is twin.
And now let us bring down the vector so that we can see the output.
So like close to zero I list in product size a plus plus
no first.
Before running this program let's see what our output should be so when one is coming for the first
time then 5 is going for the first time 2 is coming for the first time for is going for the first time
will not take this forward then 3 is coming for the first time so we will not take this tree.
We will take six videos or take seven.
We will not take one we will not take one.
We will not take two.
So this should be our answer.
1 5 2 4 2 6 7 1 5 2 4 2 6 7.
So let's see.
It's an apple.
Okay.
So basically we have to include vector.
We have to include an order to map.
So instead of including these two we can write
so then I'll let them know program.
Okay so my method count what is the idea.
So if my map not count if I.
Okay so the name of that is error.
So let's change the name.
The name is no.
So this is the output 1 5 2 4 2 6 7.
So our output is right as discussed when 5 246 7 so all the elements are unique and elements that are
appearing in the same order.
Now let us discuss what is the time complexity of a solution
know what we are doing here.
So we are just getting already today.
And basically this current function will take constraint time.
This pushback will take constraint time and this insertion will take constant time.
So our time complexity is basically linear.
Now if you're 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 logging time and this insertion function will also take logging time
so a time complexity will become and log in so this is the time complexity if you will use map.
And this is the time complexity if you will use unordered 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 5 then 2 then forward and then 3 6 and 7.
So 1 5 2 4 2 6 7.
So I hope you understood this.
I hope you understood discussion also.
I will see you in the next one.
And if you're having it out you can ask me.
Bye bye.
Thank you.