Hi, everyone.
So in this lesson, we are going to solve this question, find the smallest elements.
So the input is basically in an area and I integer key, so we have to find the key smallest elements.
So, for example, what are the key smallest elements here?
So this is zero one five and six.
So these are the four smallest elements.
President in this area.
So since the value of Gaisford, so say I will take four, so I have to find the smallest element.
Now the first and the basic approach is basically what you will lose or you will apply the sorting algorithm.
So if you are deciding now, what do I look like?
So this is zero, then one, then five, six.
So it will become eight.
Then nine, then 10.
And then 12.
And then they have to do so, you have to find fast food, so take the first four elements and this
is your answer.
So this is your smallest elements now with the complexity of the solution.
So that time complexities and low end because you have to sort the area and then after sorting the area,
you can take the first four elements and basically the first key elements.
You will take the first key elements, and that will be your answer.
Now, this was the first way using Starting Now the time complexity for using Sardinians and Logan.
But I want to solve this question in a longer time complexity.
Now, this is long and this is logoff.
So Loki's much, much less than Laugavegur because and it's basically the number of elements present
in the area and will be very small.
So basically, it is much, much less than in.
So that's why lockyear will be much, much smaller than log often.
So I want to solve this question in this much time complexity.
Now let's discuss how we can solve this question.
So basically, what I will do, I will create a maximum priority queue.
So what I'm going to do, I will create a maximum priority queue and I will push for key elements so
the value of Gaisford, so I will first push.
So this is my original idea before sorting the inventory.
So I will first push the key elements to the value of Gaisford.
So push the first four elements into your maximum priority.
So this is eight, then five, then 12 and then 10.
Simple now consider elements one by one, so zero now.
So basically the zero element is less than the largest element.
So the maximum pressure to give you can only access the largest element.
So zero is less than 10.
So what I will do, I will slap 10 with zero.
Now, this is my priority.
Give it five.
OK, so the maximum limit rostral, the maximum limit was 12.
So zero will get slapped with 12.
So 12 will come hit.
So zero will come around the system.
Now, the next element is one.
So when you compare one with the largest element to the largest element is 10, because in the mix protect
you, you only have access to the largest element using the top function to compare one with Pennsylvania's
less than 10.
So what I will do, I will strap.
So this is eight five zero and then we will pop out done.
And we will push one bob then and push one.
So when now the next element is six.
So six and what is the largest element, the largest element is currently eight now six is less than
eight.
So we will pop it and we will push six six five zero and one.
The next element is nine.
So campaign nine with the largest element to the largest element is six.
So nine is bigger than six to do nothing.
So do nothing.
And the still remains him six, five, zero and one.
And now basically we will reach the end of the year.
So what is my answer?
So this is my answer.
The elements present in the mix and produce my answer.
You can compare.
See, the elements are correct.
Six five 091 Now, since this is a dequeue so it will pop out elements, then the elements will come
in the order.
So first six will come, then five will come, then one will come and then zero will come.
This is the Maksym element, so that's where it will come out first, so this will be an order, it
will pop out the element from the MAKSYM priority you.
If you want to retain the Olympics in started with what you will do, you will just reverse the elements.
So after reversing, this will become zero one five and six and then you can print or you can do anything
you want.
So with the help of Maksym, where we can reconcile this question and local time and local time, because
you can see what is the size of the mix compared to you.
So it is containing key elements.
So that's why the insert function and the function they will take.
So basically they push and delete is actually pop.
So push and pop, they will take log of their time.
Simple, so let's take one more example to.
I understand this question better.
So let's say my area is said this is my area.
Five, then six, then nine, then later.
Well, then let's say three, then let's say 13 and then let's say two.
And let's say the valley of KS three.
I want to find out three smallest, smallest element.
So again, I will create a maximum priority queue and I will push the first key elements.
So push the first key elements.
That is first three elements into to make priority.
So this is five, then I have six and then I have nine now elementally so compared well with the largest
elements that I just listen to a little girl then I do nothing.
Now the next element is three now compared three with the largest element.
So three is actually less than nine.
So it will do pop nine and push three.
So five, six, three.
Now the next element is 13.
So 13 the largest element in the mix and produce six.
I don't lundie mix impractical.
We only have access to the topmost element that is the largest element.
So 13 will be 13 is good and six do nothing.
Now, the next element is to show two, and the largest element is six, total is less than six, but
will push through.
We will pop six and we will push two.
So this is we are five, then two and three.
So this is the content of the priority.
You and then I will reach the end of the area.
So what is my answer?
This is my answer.
So the three smallest elements are five, two and three.
And if you will pop out the elements, first of all, five will come, then three will come and then
two will come.
So these are the three smallest element present in this area.
So with the help of maximum priority queue, you can easily solve this question.
So if you are ready now, let us right the called.
So let's say I want to return a vector of integers.
And let's say the name of the function is Geissman list or before, let's say let's printhead only,
we will not return, we will just print and we have to print Casemore list elements.
So Casemore list, it will take areas and put.
So it will take the size and it will also take the value of.
So what we have to do is, first of all, I have to create a maximum priority to.
So this is the syntax for creating a mix, in particular vintages, then I have to pop, I have to push
first gay elements.
So I am pushing.
The first key elements into my priority given to my Maksym verdict also be Cadart Bush.
Now, after pushing what we have to do.
So they decided over.
So this time I would start trading from next.
I placeless, sorry, Ellerston and I placeless.
Now, what we have to do, so we have to combat the element to the current element, so if Elfy is basically
less than the topmost element of the priority, you sort of must element is actually.
Your daughter up, so if my current element is less than the maximum present in the mix in particular,
then what you can do to pop out the maximum elements would be good pop.
You'll call the function pop.
And they will push the current elements will be Art Bush.
Elfy.
And that's.
And that's all that we have to do, so for printing the answer no.
So it's time to bring it down, so I have my answer stored in the priority queue, so let us bring those
elements.
So while priority queue is not empty.
What they have to do.
You will take one by one and you will bring that element.
So I only have access to the topmost element.
So bigger and bigger, not Bob.
And now let us pass let us create an integrated.
Let's say the elements are.
Five, six, nine.
Well, let's say three.
Let's say 13 and let's go to.
So I have to call this function is my list.
So I have to pass.
What is the number of elements or one, two, three, four, five, six and seven?
So seven elements are there.
And lastly, I want to find out the smallest elements of the value of Kastari.
The use prior to whatever have to you have to include prior to you or you can simply write.
So if you do not want to write this, what you have to do this, it is actually implemented in July,
so you have to include hash included QUE.
So I think this much more will work.
So let us test our program.
So my answer is five, three and two.
And I wouldn't say it's 100 percent correct because they had the same input that we give.
We discussed here, so five to two was our answer, and they are also coming out to be five, three
and two.
So basically our goal is working fine.
Now, let us discuss the time, complexity.
So the size of my priority is actually key.
And I am pushing key elements of their time, complexity for this party scale, Skalak.
Again, this will run and minus good times and I am popping the element and pushing the elements, so
again, lockyear times when and minus Killock and the size of the Prada Gucci.
So I am popping out elements of Killock again, if you will, at this time complexity.
So your time will come out to be alloca.
Which is the desired time complexity.
OK, so this way you will be able to find out the smallest elements so you can write the code in Davíð
also, for example, what I'm doing here.
So I'm comparing and then I'm pushing or popping the elements.
But instead of this campaign, I pushed the elements and popped the element.
So let me take an example.
So let us take this example.
Only five, six, nine.
So what I want to show you.
So finally, what do we want?
So let's take an example first of the five, six, then let's say nine, then to 12, three, 13 and
two and the value of case three.
So finally, what will happen?
Our maximum priority queue.
So the size of the maximum vertical will be key because it will contain key elements.
Correct.
So finally, the size of a maximum priority is going to be key.
So what we will do, we will maintain the size.
So I maintain the size what I want to say.
So you push the first element size is less then, correct?
Less than I requested.
Now push the next element.
The size is two and the maximum size allowed is three, correct, because the next element nine.
So the size is three and the maximum size allowed is three.
Correct push the fourth element.
Now the size is equal.
Sorry, now the size is for the sizes four and the maximum size allowed is three.
So what you will do, you will pop one element and which element we can bob.
Obviously the maximum vertical so we can only possibly largest element.
So I will.
Popplewell Correct.
Now push three.
So Bush three.
So, again, this is greater than the maximum size allowed, so you will pop the maximum element, what
is the maximum element?
Nine, so nine will get popped.
So currently this is going to make symbiotically five six entry.
So the next element is tradin so Bush starting now again, the has become forth, but this is not allowed.
So make some element.
So today we'll get Bob.
Now, to add insult to again, the size becomes four to.
So, Bob, did I just say, well, Bob, the largest element and this is the content of the mix in particular
to five and three, and if you will eliminate one by one, so five will come first, then three will
come first and then two will come first.
So five, three, two.
So in this way, you can also write the code.
So we just have to maintain the size of the prior.
So if you want, I can write this code for you.
So, OK, so let me write this code for you so that you can understand it.
But the logic is same, just the way of writing will be different.
So what we have to do, let's comment about this called.
So what I am saying, you have to create a protocol that is correct, so after creating the protocol,
let's start inserting elements one by one.
So I equals zero.
I listen in, I placeless.
I will just maintain the size of my mixing protocol.
Symbol.
So let's push the element, so let's push elements or picador push.
If I am pushing the element and after pushing the limit, let's check the size so I have function to
be good size, so the maximum size allowed is gey.
So if the size becomes a gudinski.
That makes them say the loudest, if the sides become bigger, then you will just pop.
So Picador Pop.
And that's all so what I'm doing.
If the size becomes bigger than the size of the priority has to be key because our priority will contain
key elements finally, so the size becomes bigger than you can basically pop and then you can just print
the content of your priority queue.
So while.
The product is not empty.
So I'm just writing the same code, you can copy paste this line.
So bigger and bigger.
ARTPOP.
OK, so we are just getting over the.
I am pushing every element and if the size becomes bigger, then you will pop the element which element
will be popped.
So the largest element will be popped out first.
So largest element.
Will be deleted.
Correct, and then finally, the size of your priority queue, it is containing key elements and now
let us push, not a sprint.
Those key elements seem so here.
Also, your answer was containing key elements.
Inside your priority, you insider makes Embraer dequeue.
So this court will also work fine, just like the Boven, if you want, I can run this court for you.
So the output is going out to resolve this one, five, three and do so same.
The output is coming out three, five, three and two.
So let's run our program.
So you can see the output is coming out to be five, three and two, and what is the time, complexity
of the solution?
So this solution is exactly the same as the previous one, but just the way of writing is different.
So, again, this loop is running and times and I am doing logi work, so this will take a long time.
So the time, complexities and Locky.
And for this, the time, complexity, scale.
OK, so again, if you will add these to the time complexity is going to be and logi so everything the
same time, complexity, space, complexity.
OK, so the space complexity is big off key because.
My hope will contain key elements at any point of time, so this is the time and the space complexity,
I'm repeating myself.
The above me of writing the code and the below of writing the code.
The logic is seem exactly the same logic, but the way of writing is different.
And again, the time and the space complexity, the same for both the solutions.
So in the next video, what will do so in the next video, we will discuss how we can use our inbuilt
medium priority.
So this is actually an example I would take you in the next video.
We will discuss how to create how to use the inbuilt minimum priority protocol.
I will see you there.
Bye bye.