Hi, everyone.
So in this video, we're going to solve one question case hortatory.
Now, in this question, two things will be given as input, so first is the.
And second is the value of key.
So an integer or two things will be input.
First is indigeneity.
Second is integer key.
Now, what is the question?
So, for instance, the question, let us first take one example.
So let us consider this example and one more thing.
So basically, you have to start this out in decreasing order.
We have to start there in decreasing order, so get sorted out.
So for understanding the caution, we take one example.
So let us consider this example.
So if you will, Saudi, what you will be at output.
So we have decided that in descending order, then 15 or 20, then we have 10, then we have nine.
And then we have six.
So here.
15, so then 10 is shifting to point towards left.
So this is to position well, same same position.
Now 15 is shifting to position left.
Six when partition left, nine, 30 when partition, right and nine is shifting when partition left,
so you can see after starting the adding, the decreasing order, the maximum shift that element can
take is to vital because the value of history.
So what I mean to say is so consider this area.
So this is your normal unsorted area.
So this is your case ordinary.
So the meaning of Casoria, that is basically so let's say this is your element, so your element is
present at index.
So this element after getting sorted in descending order.
So this element, after getting sorted in descending order, so the maximum that it can take, it can
go left, is actually minus one distance.
And similarly, the maximum that it can go right is actually K minus one.
I'm repeating myself, so this is the given case already, your element is present again next time you
have to start the the decreasing order in descending order.
Now, after searching the area so your asset element can be present at same index, only it can go gey
minus one position left or it can go game minus one position.
Right.
Simple.
So you can see this example.
So is at the same position, 15 is going to be left to the is because the value of Kastari.
So the maximum left position is so this is a so the maximum left that I can go is eight minus two.
That makes me right.
That I can go is also applies to sortable left or to position.
Right.
So that's why this is a valid example.
So this is a valid case.
Jannati.
Now, let us consider this input, so let us sort this out in descending order, in decreasing order.
So, OK, so 15 is two times letting the value.
So let's say this, austral.
Now, after starting the arrest of the 15, this is well, then I have then then I have nine and then
I have six.
Now see this example.
So 10 is shifting to position left.
So two is allowed because the value of Kastari well is same now 15 is shifting.
So one, two and three.
So 15 is shifting three positions towards left, but he's not allowed.
That makes shifting towards left or right is only two and it is shifting three.
So this this is not a valid example of a case or tonetti.
Let's take one more example.
Now, tell me whether this is an example of a case out of that or not, so again, after searching the
area, but the condition to A15, then this will be 10, then six, then five and then four and the
value of Kastel.
So that makes them jump towards left is one and then make them jump towards right is also one simple
fluffiness taking a jump of one.
Correct.
Then taking a jump of one.
Correct.
Six correct.
For one jump five only one shift.
So this is a valid example of a case already.
This is a valid case.
Octodad is simple.
Now let's take this example and tell me whether this is a valid example of a case after that or not.
Now, after searching the area under the closing order.
So I have 15 to then then six, five and four and the value of case two.
So that makes him jump towards left can be one and that makes him jump towards right.
Can be one.
Now, 10 is taking a jump of one.
Correct.
So this is taking a jump of one.
Correct.
But 15 is taking a jump of two.
So it is shifting towards left by two and two is not allowed maximum one is allowed.
So that means this is a not a valid case already.
This is not a valid case or today.
So I hope by this time the question is clear to you and the question is very simple.
So given a case of Tonetti.
So you will be given two things as input, so first, you will be provided with an.
And second thing is the value of.
So you can assume that the input that is a so that you do not have to check whether the input allocated
area or not.
You can assume that the input provided is going to be a valid case after that.
Now, assuming the input is a valid case after that, it you have to write the code to sort this area.
You have to write the code for sorting this area.
Now, the one simple approach, so the first brute force approach is basically blindly use any sorting
algorithm, so blindly use the inbuilt start function.
If you will use the words Batard function, your time complexity came out to be a slogan, if any,
is basically the size of the area.
So this will be a time complexity, if you will use the inbuilt sorting algorithm this uses.
So actually, you can use my chart, you can use quicksort, or you can use Heap's art as discussed
in the last video.
So if you only use this art function time complex, it is going to be a login.
But one thing to notice here is so this art function, this art function works for any random.
So this is the time complexity for sorting so and the length of time complexity for I think I random
area.
But in the question it is, given that this is not a random area.
This is actually a case already.
So these are property that the area is a certain area.
So that means you have to use that property.
If you lose that property, your time complexity will decrease.
Time complexity will be will become less dense and Logan and how are we going to solve this question?
So basically we will use the MAKSYM priority queue to solve this question.
And now let us discuss how the mix in particular will help us.
And so I like this question.
So let us consider this example.
So what is the value of so the value of Kastari?
So what you will do?
So this is index zero, this is index one, index to index three and index four.
So at index zero, what elements can come?
So after starting the area.
So let's say I'm creating new area.
Let's say this is Arab and Arab, I will store my output.
Let us assume so at this position.
Which elements can come?
So, again, to point towards this history, so make them do point towards left and similarly makes
them do point towards right, so that to point towards left zero minus two and similarly to position
towards right.
So at this position, I have three contenders, so I have to come here, 15 can come here and seven
can come here.
So among these three elements.
Only one of them will come here.
You do not need to consider these elements because they can never come at index zero.
They can never they are not competing for index zero.
So we have to decide among these three which element should come.
And it is very obvious that we have to start using order.
So the maximum element will pick the maximum limit.
So this is your Arabie?
I'm going to pick the maximum limit, so remove the maximum element.
So 15 is going to become come here.
Simple.
Now, let's try to fill in next one so that the next one, what other competitors thought, well, can
come here, 15 can come, seven can come and four can come, but 15 is already used.
So I have only three contenders, so I have to break and come.
Seven can come or four can come.
Only three elements are going to compete for the next one.
And among these three, I repeat the maximum.
So I will pick 12.
Simple, now let's try to fill in next to so next to what competitors I can have.
So again, so two elements towards left and two elements towards right.
So if you go to element towards left, so 15 is already taken to his left.
So too is the competitor.
Obviously seven is going to be competitor and two elements towards.
Right.
So I have seven and so I have four and nine.
OK, so I did one mistake, so this is.
Well, actually, this is not the first one, and since Doyle has been taken to trial, will not come
here.
So this is this rostral.
So I'd come here.
Now, what are the competitors for nine, so seven foot and nine and what you have to do?
We have to pick the maximum of oil.
So the maximum is going to be nine.
So I'm going to pick nine.
Simple, now let's try to fill in the history of an industry where the competitors so element is the
competitor element nine is not competitive because it has already been used.
Element seven is competitor.
Element 15 was also competitor, but it has been used so that I have only two elements left.
So among these two, I will pick the maximum, so I will pick seven.
And then I have only one index left and I have only one element left.
So I will put forward here.
So this will be my assorted area.
So this is actually a maximum priority queue.
So what we are doing at each index for filling each index, we have to take the maximum of key elements.
We are taking so I'm repeating myself so far, failing economics, what we are doing, we are taking
a maximum of key elements.
Simple.
And we know in the maximum priority queue, if you will, construct to them prior to you then getting
the maximum this constant time.
So that's why you can help us here, because we can get the maximum limited question time simple.
Let's take one more example.
So let's take this example.
And now what we are going to do.
So the value of Kastari, so what I will do, I will create a maximum priority queue of Sastry.
Now, after creating the maximum prior to Güzel.
These are indexes, so so these are indexes, so every index zero, index one, index to index three,
an index for.
And my priority will be Sastry, so initially my priority queue, so I am writing initially my prayer
to use MBT.
So initially overprotecting them pretty OK.
So what we will do will push key elements of the value of Kastari, so I will push starting key elements
into my.
Priority queue, so the elementary school, the next element is seven and the next element is five.
So this is not arranged in this manner.
This is actually be a maximum.
But you can just write like this.
So what I want to say is this is not a story like this, this will be basically you can know how to
create an episode.
Well, then said will go here and then Fishville.
Go ahead.
So.
The Maksym heap withstood the elements in this manner, but we know how it makes them work so you can
directly ride the like like this.
So we have three elements at this position.
Seven and five.
And now I am standing at this index, so what I will do, I will iterate from this to this and I will
start feeling from so let's call this index start.
Now, this is so fulfilling, the elements start.
I will take the maximum of these three, so let me try to again, so my prayer is containing three elements.
Well, then eliminate seven and then eliminate five.
I want to fill the place and start, so I'm going to do the maximum element, so the maximum limit is
so remote and right well here at the start position, then start position placeless.
Simple and similarly, you will push the element presented index.
So the element is nine now for filling the elements start.
So what I am doing, I will move in this direction and start will also move in this direction.
Now, take the maximum of these three, so the element is nine, so remove nine and put it here again
what you are going to do.
So I will come here and startle.
Come here.
So now, again, take the maximum.
So push for.
Bush fought inside the pressure to unite the maximum of seven, five and four, so I will pick seven.
So right, seven hit.
Now, what will happen to your eye will reach the end of the day and you have two elements left inside
your priority.
Five and four, and we have two indexes left.
So we're going to do the and put it here.
The maximum element put it here, so this will be your answer, correct?
Let's take one more example.
Let's take this example, only 12, 15, seven, OK, so let's take among this one, let's take this
example, 10, 15.
So, OK, 10, 15, six, four, five.
Then 15, six foot five.
So 10, then 15, then six, then four and then five and the value of case two, so the value of KS
to that means the size of one vertical will be too simple.
So initially my prior to the maximum, prior to the maximum hippies and pretty.
Now, Bush is starting to show the value of Gaist, also push the starting two elements into a priority
given elements 10 and 15.
This is your.
I and this is your start.
Simple then approach is very simple pick the Maksym element and put it here at the start position and
then start placeless.
Similarly, I placeless Sudie, first you will push elements, so push element six and then you will
do a placeless.
Correct.
So this is my new eye and this is my new start again, pick the MAKSYM element to make some element
Distin so removed, then put it here to start placeless.
So Start is going to come here.
And to really push the element forward and do it so I is going to come here and you can notice every
time the size of my priority queue, at each point, at every moment of time, the size of my priority
is actually to only it is containing only two elements because the value of to.
And now, again, the maximum element to the element is six, seven, eight, six, eight, the starting
position, then start placeless.
So START will move ahead.
Then put the element of life support element five.
We are putting the element faith, and then I will do a plus plus stylizing is the index of the array.
Then again, the MAKSYM element.
So the maximum element is five.
So put five at the starting position and start plus plus.
Now, see the value of index, the index is the index, which is the end of the area.
So when index, which is the end of the day, we will stop.
So at this point, what is the condition of my area?
So it is containing 15 then then then six, then five.
So one index is left.
So this start.
So one index is left and you can see there is only one element present in the vertical.
So what you will do, you will take that element and you will put it here.
Simple, so what is the time, complexity, if you will, use Maksym prior to you so for analyzing the
time complexity, let us first write the code and then we will analyze the time complexity.
So we have to change, we have to do changes inside area so that it will be void, the name, let's
say the name of the function is already.
So what it will take, so it will take.
Anti-Terrorism, but obviously the size of the anti-terrorist and are very bulky.
Then why do you have to do so, we have to create Makhzoumi and we know how to kill, it makes me so
proud.
I want to create a make some heap of integers.
Let's say the name is Piku and obviously you have to include.
Now, the first step is we will take we have to insert the first gay elements into the protocol, so
we have to insert the first gay element.
So the value of gays to for the first two elements inside our priority queue.
So in the first two elements, first key elements inside our dequeue.
So I have a function, B, Cadart Bush.
What I will do, so I will give in.
So after inserting the first elements.
What I have to do, so if you remember, I have to take a variable I saw the value of I will start from
Key and I left and I placeless.
I will do some work here.
And again, if you remember, I also take a point to start.
So start will start from zero.
So you can see so I am taking the point, the first one is this dart pointer and this is was this was
my appointer.
So I started from this index.
I started from this index.
So this index is zero one and two, you can see.
So I said starting from two, so two is actually key and similarly I starting from K and so start will
start from zero.
Now, what we have to do, so this index, so don't my editors and put so what will be put off start?
So in the start, I have to get the topmost element, so how to get up must be Coudert up, so it will
give me the maximum element and after getting the maximum limit, we have to also remove from the priority.
You know, after knowing what we have to do, we have to start placeless and then we have to insert
the i8 element, insert into our biodegrades will be gardot.
Bush, I have to push a little bit, so in but off I.
So I am pushing a settlement, so this is a and then what will happen, I placeless, simple, not after
doing this.
After doing this, what would I have to do?
So there will be some elements that will be left inside our priority queue.
So while the priority is not empty.
So while the Braddick is not empty, what we have to do so in Batoff start, where does it start?
So this is actually.
B, Cadart top.
And again, Bidgood ARTPOP.
And start placeless, simple, so that's all we have to do.
So this is now let's test our code.
So let us clear denarii.
And let's say the elements are dead certain, 12, six, seven and nine.
And let's say the value of care is actually three and we will call it a function.
So this is case already.
I have to parse two things.
So let us pass the Portelli.
Number of elements is faith and the value of Kastari.
Now, after doing this letter, spent nearly.
OK, so this will be fine, if not.
So this is my complete call now.
Let's take this example, 10, 12, six, seven, nine.
And let's see what will happen.
So 10, 12, six, seven and nine, so I have this, Eddie.
This is 10, then 12, then six, then seven, then nine and the Valley of KS actually, so three,
a value of KS three, correct.
And these are the indexes, zero, one, two, three and four.
Now I am creating a maximum priority, correct?
I am pushing the first key elements for the value of Kastari.
So push the first three elements into our priority queue.
So this is my priority, which is containing three elements.
I pushed and then I pushed.
Well, then I pushed six correct.
Start as a zero.
So this is your start.
I is gay.
So gays basically three, so this is are a.
Correct.
Now, of this brought up, what is the maximum elements or the maximum element, so put at it, but
at this stage next so remove 2L and put at the START index.
So this then will become tool.
So I am writing below, so this pen will become, well, correct then, Bob.
So Bob Delimit start to start is going to come here.
Then push the Taliban today at seven, so push the element seven.
Then C++.
So I will come here.
Correct.
Now, again, so big, what is the maximum limit, so the maximum limit is so one thing that you can
notice my size of Diplodocus always Gayathri so the size of the particular is three, always another
maximum limitation support element 10 at the starting position.
So I will push down here then Bob.
So we already Bob then started as press so start will move ahead.
Now, Bush, the eighth element, that element is nine, so push the element nine.
Now, again, the size and priority is three and the eight plus plus.
So remove I and I will reach basically the end of the.
So when I will reach the end of the address, this condition will become false.
And I will reach at this point line number 20 now, how many elements is containing?
So it is containing three elements.
And what I'm doing and put off start this up, so it is the topmost element, nine, so remove nine.
And put it here, so remove six foot nine and then you do pop.
So we already started to split.
So Start is going to come here.
Then again, is not empty Dopp elements of that top is seven.
The upper limit is seven, right, seven, so right, seven here and then you will do you'll pop the
element and start plus place to start is going to come here and mop up the elements, six foot six and
then start placeless and then you try to keep them pretty.
So when you try to keep them pretty, you will stop.
And this is reality.
So it stays 10, then 12, 10, nine, seven and six.
So this is your final output.
This is this area sorted in descending order, decreasing order, and you can see so the value of gave
us three and our initial Aribert was only Shilbury then then 12, then six, then seven.
And then you can see so many shipping went position.
Well, one position six, two positions or two operation is allowed, one seven one position and nine
one position.
So everything is working fine.
Now let us try to test our program.
Let's try to test double gold.
So see our iReporters coming out right now.
That is sorted in descending order.
Ten, nine, seven, six.
Now, let's try to analyze the time and the space complexity of what our solution.
So what I'm doing here.
This loop will run good times and push function, so if you remember, if there are any elements to
the Bush function will take for pushing one element, that it will take longer in time.
Correct.
So now this loop is going to run good times and the size of the priority is key.
So the time complexity schlocky.
So for this part, the time complexities gridlocking so gay is the number of elements present in my
priority queue.
So now decide also how many times this loop will run, so this loop is going to run and minus goodtimes.
And in each loop, what work I am doing, so this is constant worktop, constant pop, I am popping.
So how much time, Logi?
So far, a whopping one element, the time complexity was a log of N if and is the number of elements.
So in this case, the number of elements is key.
So that's why locating then this is constant work and again, push.
So log Gabler's location to lock.
So ultimately, what is my complex complexity is to look, you can remove to the time complexities and
mindlessly multiply lucky.
So this is the time complexity now for this part.
So how many elements have left, so if you see and minus key elements has been pushed to its correct
position, so this loop will run times and this is what is constant.
This work is lockyear time.
And this work is constrained.
So finally, this is the time complexity for this part.
Now we are going to add all these three time complexity and let's see what will be our final time complexity.
So I have Killock.
So this is Kellock.
Now you can ride like this, so let's multiply.
So this is an logi.
Then minus Gailhaguet.
And then this one, so this is Golok.
So these two will cancel out each other and now let us combine this.
So this is big off and plus gay.
Lakki.
Correct.
Now, the value of and will be, Aniceto, the number of elements present in our area, so the value
will be returned to the buyer of five 10 to the power six, and the value of it will be like three,
five, 10 or 20.
So basically I can see the value of and is much, much greater then.
So basically, can I say that the complexity is nothing, but it is an logi.
Simple and see if the value of a very small.
If the value of small so lucky, if you will use Locata, the value will always decrease.
Loggers are decreasing function, it will decrease your value.
So the value is very small.
So that means logging will also be very, very small.
So it will also be very, very small.
So again, what you can do so you can say the maritime complexities big of an.
So that time complexities big often, and this is much, much better than using any sorting algorithm.
So we discussed if you blindly use any sorting algorithm, that a time complexity actually was and login,
but using the MAKSYM prior to our time complexities big off and.
And now let's discuss this space complexity, so we are just creating a priority queue and the priority
queue will contain key elements.
So the space complexities big off key.
Again, the value of care will be very small, three, five, 10 or 20.
So you can see that the space complexity is big often.
So this is the final time complexity, which is linear and this is defined space complexity, which
is constant big often because the value of K is going to be very, very small.
So I hope you understood the solution.
So if you have any doubt, the best way is basically to take one example and to try it and discovered
you will understand everything.
So I will see you in the next one.
Bye.