1
00:00:01,460 --> 00:00:02,130
Hi, everyone.

2
00:00:02,150 --> 00:00:06,050
So in this video, we're going to solve one question case hortatory.

3
00:00:07,760 --> 00:00:12,140
Now, in this question, two things will be given as input, so first is the.

4
00:00:12,470 --> 00:00:14,260
And second is the value of key.

5
00:00:14,310 --> 00:00:17,660
So an integer or two things will be input.

6
00:00:17,660 --> 00:00:19,280
First is indigeneity.

7
00:00:19,670 --> 00:00:22,010
Second is integer key.

8
00:00:22,940 --> 00:00:24,060
Now, what is the question?

9
00:00:24,530 --> 00:00:28,250
So, for instance, the question, let us first take one example.

10
00:00:28,490 --> 00:00:31,550
So let us consider this example and one more thing.

11
00:00:31,580 --> 00:00:34,100
So basically, you have to start this out in decreasing order.

12
00:00:35,090 --> 00:00:37,970
We have to start there in decreasing order, so get sorted out.

13
00:00:38,390 --> 00:00:40,840
So for understanding the caution, we take one example.

14
00:00:41,120 --> 00:00:42,960
So let us consider this example.

15
00:00:43,280 --> 00:00:45,890
So if you will, Saudi, what you will be at output.

16
00:00:46,130 --> 00:00:52,850
So we have decided that in descending order, then 15 or 20, then we have 10, then we have nine.

17
00:00:52,850 --> 00:00:54,080
And then we have six.

18
00:00:56,070 --> 00:00:56,710
So here.

19
00:00:58,080 --> 00:01:02,250
15, so then 10 is shifting to point towards left.

20
00:01:02,280 --> 00:01:06,360
So this is to position well, same same position.

21
00:01:06,690 --> 00:01:09,690
Now 15 is shifting to position left.

22
00:01:10,620 --> 00:01:16,620
Six when partition left, nine, 30 when partition, right and nine is shifting when partition left,

23
00:01:17,580 --> 00:01:24,720
so you can see after starting the adding, the decreasing order, the maximum shift that element can

24
00:01:24,720 --> 00:01:27,550
take is to vital because the value of history.

25
00:01:28,110 --> 00:01:31,090
So what I mean to say is so consider this area.

26
00:01:32,010 --> 00:01:34,630
So this is your normal unsorted area.

27
00:01:34,650 --> 00:01:36,220
So this is your case ordinary.

28
00:01:36,900 --> 00:01:42,690
So the meaning of Casoria, that is basically so let's say this is your element, so your element is

29
00:01:42,690 --> 00:01:43,740
present at index.

30
00:01:44,730 --> 00:01:48,090
So this element after getting sorted in descending order.

31
00:01:49,190 --> 00:01:55,340
So this element, after getting sorted in descending order, so the maximum that it can take, it can

32
00:01:55,340 --> 00:01:57,610
go left, is actually minus one distance.

33
00:01:57,620 --> 00:02:01,460
And similarly, the maximum that it can go right is actually K minus one.

34
00:02:02,810 --> 00:02:10,580
I'm repeating myself, so this is the given case already, your element is present again next time you

35
00:02:10,580 --> 00:02:13,920
have to start the the decreasing order in descending order.

36
00:02:14,270 --> 00:02:21,130
Now, after searching the area so your asset element can be present at same index, only it can go gey

37
00:02:21,170 --> 00:02:24,520
minus one position left or it can go game minus one position.

38
00:02:24,560 --> 00:02:24,950
Right.

39
00:02:25,310 --> 00:02:25,930
Simple.

40
00:02:26,210 --> 00:02:27,650
So you can see this example.

41
00:02:27,860 --> 00:02:34,520
So is at the same position, 15 is going to be left to the is because the value of Kastari.

42
00:02:34,880 --> 00:02:40,510
So the maximum left position is so this is a so the maximum left that I can go is eight minus two.

43
00:02:40,520 --> 00:02:41,720
That makes me right.

44
00:02:41,720 --> 00:02:46,130
That I can go is also applies to sortable left or to position.

45
00:02:46,130 --> 00:02:46,420
Right.

46
00:02:46,820 --> 00:02:49,010
So that's why this is a valid example.

47
00:02:49,280 --> 00:02:50,950
So this is a valid case.

48
00:02:51,050 --> 00:02:51,470
Jannati.

49
00:02:52,500 --> 00:02:58,100
Now, let us consider this input, so let us sort this out in descending order, in decreasing order.

50
00:02:58,560 --> 00:03:01,590
So, OK, so 15 is two times letting the value.

51
00:03:02,630 --> 00:03:03,800
So let's say this, austral.

52
00:03:06,520 --> 00:03:12,970
Now, after starting the arrest of the 15, this is well, then I have then then I have nine and then

53
00:03:12,970 --> 00:03:13,590
I have six.

54
00:03:14,230 --> 00:03:15,390
Now see this example.

55
00:03:16,030 --> 00:03:18,800
So 10 is shifting to position left.

56
00:03:18,820 --> 00:03:25,150
So two is allowed because the value of Kastari well is same now 15 is shifting.

57
00:03:25,420 --> 00:03:27,360
So one, two and three.

58
00:03:27,580 --> 00:03:31,540
So 15 is shifting three positions towards left, but he's not allowed.

59
00:03:32,080 --> 00:03:37,110
That makes shifting towards left or right is only two and it is shifting three.

60
00:03:37,570 --> 00:03:42,100
So this this is not a valid example of a case or tonetti.

61
00:03:43,490 --> 00:03:44,930
Let's take one more example.

62
00:03:46,830 --> 00:03:53,640
Now, tell me whether this is an example of a case out of that or not, so again, after searching the

63
00:03:53,640 --> 00:04:00,360
area, but the condition to A15, then this will be 10, then six, then five and then four and the

64
00:04:00,360 --> 00:04:01,270
value of Kastel.

65
00:04:01,320 --> 00:04:06,720
So that makes them jump towards left is one and then make them jump towards right is also one simple

66
00:04:07,170 --> 00:04:08,640
fluffiness taking a jump of one.

67
00:04:08,640 --> 00:04:09,060
Correct.

68
00:04:09,540 --> 00:04:10,890
Then taking a jump of one.

69
00:04:10,890 --> 00:04:11,300
Correct.

70
00:04:11,640 --> 00:04:12,600
Six correct.

71
00:04:12,690 --> 00:04:15,820
For one jump five only one shift.

72
00:04:16,170 --> 00:04:18,990
So this is a valid example of a case already.

73
00:04:19,290 --> 00:04:20,850
This is a valid case.

74
00:04:20,850 --> 00:04:21,850
Octodad is simple.

75
00:04:22,680 --> 00:04:28,190
Now let's take this example and tell me whether this is a valid example of a case after that or not.

76
00:04:28,860 --> 00:04:31,250
Now, after searching the area under the closing order.

77
00:04:31,590 --> 00:04:38,130
So I have 15 to then then six, five and four and the value of case two.

78
00:04:38,400 --> 00:04:42,690
So that makes him jump towards left can be one and that makes him jump towards right.

79
00:04:42,690 --> 00:04:43,260
Can be one.

80
00:04:44,040 --> 00:04:45,720
Now, 10 is taking a jump of one.

81
00:04:45,960 --> 00:04:46,400
Correct.

82
00:04:46,800 --> 00:04:48,330
So this is taking a jump of one.

83
00:04:48,570 --> 00:04:49,020
Correct.

84
00:04:49,260 --> 00:04:51,510
But 15 is taking a jump of two.

85
00:04:52,350 --> 00:04:57,460
So it is shifting towards left by two and two is not allowed maximum one is allowed.

86
00:04:57,660 --> 00:05:00,860
So that means this is a not a valid case already.

87
00:05:01,260 --> 00:05:03,380
This is not a valid case or today.

88
00:05:04,440 --> 00:05:09,670
So I hope by this time the question is clear to you and the question is very simple.

89
00:05:10,080 --> 00:05:11,760
So given a case of Tonetti.

90
00:05:13,240 --> 00:05:17,410
So you will be given two things as input, so first, you will be provided with an.

91
00:05:17,680 --> 00:05:19,690
And second thing is the value of.

92
00:05:20,500 --> 00:05:26,800
So you can assume that the input that is a so that you do not have to check whether the input allocated

93
00:05:26,800 --> 00:05:27,350
area or not.

94
00:05:27,370 --> 00:05:31,240
You can assume that the input provided is going to be a valid case after that.

95
00:05:32,020 --> 00:05:37,350
Now, assuming the input is a valid case after that, it you have to write the code to sort this area.

96
00:05:38,020 --> 00:05:39,930
You have to write the code for sorting this area.

97
00:05:40,840 --> 00:05:47,200
Now, the one simple approach, so the first brute force approach is basically blindly use any sorting

98
00:05:47,200 --> 00:05:50,290
algorithm, so blindly use the inbuilt start function.

99
00:05:51,280 --> 00:05:55,850
If you will use the words Batard function, your time complexity came out to be a slogan, if any,

100
00:05:55,860 --> 00:05:57,470
is basically the size of the area.

101
00:05:58,210 --> 00:06:04,620
So this will be a time complexity, if you will use the inbuilt sorting algorithm this uses.

102
00:06:04,630 --> 00:06:09,160
So actually, you can use my chart, you can use quicksort, or you can use Heap's art as discussed

103
00:06:09,160 --> 00:06:09,930
in the last video.

104
00:06:10,270 --> 00:06:14,110
So if you only use this art function time complex, it is going to be a login.

105
00:06:14,530 --> 00:06:19,630
But one thing to notice here is so this art function, this art function works for any random.

106
00:06:22,460 --> 00:06:27,670
So this is the time complexity for sorting so and the length of time complexity for I think I random

107
00:06:27,680 --> 00:06:27,920
area.

108
00:06:29,670 --> 00:06:32,600
But in the question it is, given that this is not a random area.

109
00:06:33,030 --> 00:06:34,770
This is actually a case already.

110
00:06:35,070 --> 00:06:39,180
So these are property that the area is a certain area.

111
00:06:39,210 --> 00:06:41,220
So that means you have to use that property.

112
00:06:42,310 --> 00:06:45,310
If you lose that property, your time complexity will decrease.

113
00:06:46,640 --> 00:06:51,780
Time complexity will be will become less dense and Logan and how are we going to solve this question?

114
00:06:51,800 --> 00:06:56,330
So basically we will use the MAKSYM priority queue to solve this question.

115
00:06:56,750 --> 00:06:59,920
And now let us discuss how the mix in particular will help us.

116
00:06:59,930 --> 00:07:00,980
And so I like this question.

117
00:07:03,110 --> 00:07:04,970
So let us consider this example.

118
00:07:06,890 --> 00:07:09,770
So what is the value of so the value of Kastari?

119
00:07:10,840 --> 00:07:11,800
So what you will do?

120
00:07:12,740 --> 00:07:18,560
So this is index zero, this is index one, index to index three and index four.

121
00:07:19,460 --> 00:07:22,410
So at index zero, what elements can come?

122
00:07:22,430 --> 00:07:23,750
So after starting the area.

123
00:07:25,060 --> 00:07:26,590
So let's say I'm creating new area.

124
00:07:26,630 --> 00:07:30,400
Let's say this is Arab and Arab, I will store my output.

125
00:07:30,550 --> 00:07:34,000
Let us assume so at this position.

126
00:07:35,440 --> 00:07:36,530
Which elements can come?

127
00:07:36,910 --> 00:07:43,240
So, again, to point towards this history, so make them do point towards left and similarly makes

128
00:07:43,240 --> 00:07:49,450
them do point towards right, so that to point towards left zero minus two and similarly to position

129
00:07:49,450 --> 00:07:50,120
towards right.

130
00:07:50,680 --> 00:07:57,130
So at this position, I have three contenders, so I have to come here, 15 can come here and seven

131
00:07:57,130 --> 00:07:57,730
can come here.

132
00:07:58,000 --> 00:07:59,410
So among these three elements.

133
00:08:01,030 --> 00:08:02,720
Only one of them will come here.

134
00:08:02,740 --> 00:08:07,940
You do not need to consider these elements because they can never come at index zero.

135
00:08:08,860 --> 00:08:11,460
They can never they are not competing for index zero.

136
00:08:11,890 --> 00:08:14,890
So we have to decide among these three which element should come.

137
00:08:15,610 --> 00:08:18,400
And it is very obvious that we have to start using order.

138
00:08:18,400 --> 00:08:21,220
So the maximum element will pick the maximum limit.

139
00:08:21,700 --> 00:08:22,890
So this is your Arabie?

140
00:08:23,170 --> 00:08:26,130
I'm going to pick the maximum limit, so remove the maximum element.

141
00:08:26,500 --> 00:08:28,240
So 15 is going to become come here.

142
00:08:28,360 --> 00:08:28,900
Simple.

143
00:08:30,290 --> 00:08:35,890
Now, let's try to fill in next one so that the next one, what other competitors thought, well, can

144
00:08:35,900 --> 00:08:42,720
come here, 15 can come, seven can come and four can come, but 15 is already used.

145
00:08:42,740 --> 00:08:46,220
So I have only three contenders, so I have to break and come.

146
00:08:46,610 --> 00:08:48,470
Seven can come or four can come.

147
00:08:48,800 --> 00:08:52,110
Only three elements are going to compete for the next one.

148
00:08:52,730 --> 00:08:54,800
And among these three, I repeat the maximum.

149
00:08:55,250 --> 00:08:56,300
So I will pick 12.

150
00:08:58,150 --> 00:09:04,180
Simple, now let's try to fill in next to so next to what competitors I can have.

151
00:09:04,450 --> 00:09:08,680
So again, so two elements towards left and two elements towards right.

152
00:09:08,710 --> 00:09:13,180
So if you go to element towards left, so 15 is already taken to his left.

153
00:09:13,510 --> 00:09:14,830
So too is the competitor.

154
00:09:14,830 --> 00:09:19,120
Obviously seven is going to be competitor and two elements towards.

155
00:09:19,120 --> 00:09:19,480
Right.

156
00:09:19,810 --> 00:09:22,810
So I have seven and so I have four and nine.

157
00:09:24,050 --> 00:09:25,970
OK, so I did one mistake, so this is.

158
00:09:26,040 --> 00:09:31,790
Well, actually, this is not the first one, and since Doyle has been taken to trial, will not come

159
00:09:31,790 --> 00:09:32,010
here.

160
00:09:32,030 --> 00:09:33,310
So this is this rostral.

161
00:09:33,590 --> 00:09:34,820
So I'd come here.

162
00:09:36,030 --> 00:09:41,620
Now, what are the competitors for nine, so seven foot and nine and what you have to do?

163
00:09:41,640 --> 00:09:43,980
We have to pick the maximum of oil.

164
00:09:44,190 --> 00:09:45,680
So the maximum is going to be nine.

165
00:09:46,260 --> 00:09:47,640
So I'm going to pick nine.

166
00:09:49,010 --> 00:09:55,490
Simple, now let's try to fill in the history of an industry where the competitors so element is the

167
00:09:55,490 --> 00:10:00,220
competitor element nine is not competitive because it has already been used.

168
00:10:00,710 --> 00:10:02,390
Element seven is competitor.

169
00:10:03,050 --> 00:10:09,040
Element 15 was also competitor, but it has been used so that I have only two elements left.

170
00:10:09,260 --> 00:10:12,050
So among these two, I will pick the maximum, so I will pick seven.

171
00:10:12,410 --> 00:10:16,760
And then I have only one index left and I have only one element left.

172
00:10:16,760 --> 00:10:18,410
So I will put forward here.

173
00:10:19,160 --> 00:10:20,870
So this will be my assorted area.

174
00:10:22,040 --> 00:10:24,560
So this is actually a maximum priority queue.

175
00:10:25,130 --> 00:10:31,670
So what we are doing at each index for filling each index, we have to take the maximum of key elements.

176
00:10:33,130 --> 00:10:38,980
We are taking so I'm repeating myself so far, failing economics, what we are doing, we are taking

177
00:10:38,980 --> 00:10:40,960
a maximum of key elements.

178
00:10:41,800 --> 00:10:42,310
Simple.

179
00:10:44,160 --> 00:10:49,770
And we know in the maximum priority queue, if you will, construct to them prior to you then getting

180
00:10:49,770 --> 00:10:51,600
the maximum this constant time.

181
00:10:53,320 --> 00:10:59,680
So that's why you can help us here, because we can get the maximum limited question time simple.

182
00:11:01,390 --> 00:11:02,730
Let's take one more example.

183
00:11:04,600 --> 00:11:06,060
So let's take this example.

184
00:11:10,520 --> 00:11:11,780
And now what we are going to do.

185
00:11:13,080 --> 00:11:19,440
So the value of Kastari, so what I will do, I will create a maximum priority queue of Sastry.

186
00:11:21,060 --> 00:11:23,400
Now, after creating the maximum prior to Güzel.

187
00:11:24,380 --> 00:11:30,320
These are indexes, so so these are indexes, so every index zero, index one, index to index three,

188
00:11:30,320 --> 00:11:31,100
an index for.

189
00:11:32,160 --> 00:11:40,350
And my priority will be Sastry, so initially my priority queue, so I am writing initially my prayer

190
00:11:40,350 --> 00:11:41,280
to use MBT.

191
00:11:45,330 --> 00:11:48,020
So initially overprotecting them pretty OK.

192
00:11:48,360 --> 00:11:54,390
So what we will do will push key elements of the value of Kastari, so I will push starting key elements

193
00:11:54,390 --> 00:11:55,050
into my.

194
00:11:56,100 --> 00:12:00,860
Priority queue, so the elementary school, the next element is seven and the next element is five.

195
00:12:01,620 --> 00:12:04,330
So this is not arranged in this manner.

196
00:12:04,350 --> 00:12:05,860
This is actually be a maximum.

197
00:12:05,970 --> 00:12:07,920
But you can just write like this.

198
00:12:08,990 --> 00:12:14,310
So what I want to say is this is not a story like this, this will be basically you can know how to

199
00:12:14,310 --> 00:12:15,300
create an episode.

200
00:12:15,320 --> 00:12:17,870
Well, then said will go here and then Fishville.

201
00:12:17,870 --> 00:12:18,270
Go ahead.

202
00:12:18,530 --> 00:12:18,890
So.

203
00:12:20,250 --> 00:12:25,770
The Maksym heap withstood the elements in this manner, but we know how it makes them work so you can

204
00:12:25,780 --> 00:12:27,380
directly ride the like like this.

205
00:12:28,020 --> 00:12:30,360
So we have three elements at this position.

206
00:12:30,600 --> 00:12:31,290
Seven and five.

207
00:12:32,280 --> 00:12:38,190
And now I am standing at this index, so what I will do, I will iterate from this to this and I will

208
00:12:38,190 --> 00:12:41,220
start feeling from so let's call this index start.

209
00:12:43,910 --> 00:12:47,060
Now, this is so fulfilling, the elements start.

210
00:12:48,270 --> 00:12:54,570
I will take the maximum of these three, so let me try to again, so my prayer is containing three elements.

211
00:12:54,710 --> 00:12:57,660
Well, then eliminate seven and then eliminate five.

212
00:12:59,080 --> 00:13:04,500
I want to fill the place and start, so I'm going to do the maximum element, so the maximum limit is

213
00:13:04,780 --> 00:13:10,450
so remote and right well here at the start position, then start position placeless.

214
00:13:12,080 --> 00:13:16,330
Simple and similarly, you will push the element presented index.

215
00:13:17,060 --> 00:13:20,560
So the element is nine now for filling the elements start.

216
00:13:20,600 --> 00:13:24,500
So what I am doing, I will move in this direction and start will also move in this direction.

217
00:13:26,410 --> 00:13:32,110
Now, take the maximum of these three, so the element is nine, so remove nine and put it here again

218
00:13:32,980 --> 00:13:33,780
what you are going to do.

219
00:13:33,790 --> 00:13:36,940
So I will come here and startle.

220
00:13:36,940 --> 00:13:37,410
Come here.

221
00:13:38,290 --> 00:13:40,000
So now, again, take the maximum.

222
00:13:41,930 --> 00:13:43,160
So push for.

223
00:13:44,810 --> 00:13:49,430
Bush fought inside the pressure to unite the maximum of seven, five and four, so I will pick seven.

224
00:13:49,450 --> 00:13:50,420
So right, seven hit.

225
00:13:52,220 --> 00:13:58,160
Now, what will happen to your eye will reach the end of the day and you have two elements left inside

226
00:13:58,160 --> 00:13:58,720
your priority.

227
00:13:58,950 --> 00:14:00,980
Five and four, and we have two indexes left.

228
00:14:02,090 --> 00:14:04,620
So we're going to do the and put it here.

229
00:14:05,850 --> 00:14:10,120
The maximum element put it here, so this will be your answer, correct?

230
00:14:11,390 --> 00:14:12,800
Let's take one more example.

231
00:14:14,790 --> 00:14:21,180
Let's take this example, only 12, 15, seven, OK, so let's take among this one, let's take this

232
00:14:21,180 --> 00:14:22,500
example, 10, 15.

233
00:14:22,740 --> 00:14:25,320
So, OK, 10, 15, six, four, five.

234
00:14:26,230 --> 00:14:27,490
Then 15, six foot five.

235
00:14:32,910 --> 00:14:40,830
So 10, then 15, then six, then four and then five and the value of case two, so the value of KS

236
00:14:40,830 --> 00:14:44,110
to that means the size of one vertical will be too simple.

237
00:14:44,490 --> 00:14:48,570
So initially my prior to the maximum, prior to the maximum hippies and pretty.

238
00:14:50,320 --> 00:14:56,380
Now, Bush is starting to show the value of Gaist, also push the starting two elements into a priority

239
00:14:56,400 --> 00:14:58,480
given elements 10 and 15.

240
00:15:00,290 --> 00:15:01,250
This is your.

241
00:15:02,390 --> 00:15:04,460
I and this is your start.

242
00:15:05,860 --> 00:15:13,720
Simple then approach is very simple pick the Maksym element and put it here at the start position and

243
00:15:13,720 --> 00:15:15,490
then start placeless.

244
00:15:16,690 --> 00:15:24,280
Similarly, I placeless Sudie, first you will push elements, so push element six and then you will

245
00:15:24,280 --> 00:15:25,240
do a placeless.

246
00:15:26,730 --> 00:15:27,180
Correct.

247
00:15:27,330 --> 00:15:32,500
So this is my new eye and this is my new start again, pick the MAKSYM element to make some element

248
00:15:32,500 --> 00:15:36,960
Distin so removed, then put it here to start placeless.

249
00:15:37,620 --> 00:15:39,120
So Start is going to come here.

250
00:15:40,400 --> 00:15:48,320
And to really push the element forward and do it so I is going to come here and you can notice every

251
00:15:48,320 --> 00:15:53,270
time the size of my priority queue, at each point, at every moment of time, the size of my priority

252
00:15:53,420 --> 00:15:57,080
is actually to only it is containing only two elements because the value of to.

253
00:15:58,220 --> 00:16:03,050
And now, again, the maximum element to the element is six, seven, eight, six, eight, the starting

254
00:16:03,050 --> 00:16:05,440
position, then start placeless.

255
00:16:05,540 --> 00:16:06,980
So START will move ahead.

256
00:16:08,110 --> 00:16:11,380
Then put the element of life support element five.

257
00:16:12,490 --> 00:16:18,170
We are putting the element faith, and then I will do a plus plus stylizing is the index of the array.

258
00:16:18,910 --> 00:16:21,030
Then again, the MAKSYM element.

259
00:16:21,040 --> 00:16:22,540
So the maximum element is five.

260
00:16:23,110 --> 00:16:26,470
So put five at the starting position and start plus plus.

261
00:16:28,300 --> 00:16:34,070
Now, see the value of index, the index is the index, which is the end of the area.

262
00:16:34,540 --> 00:16:37,010
So when index, which is the end of the day, we will stop.

263
00:16:37,270 --> 00:16:39,320
So at this point, what is the condition of my area?

264
00:16:39,340 --> 00:16:42,350
So it is containing 15 then then then six, then five.

265
00:16:42,730 --> 00:16:44,500
So one index is left.

266
00:16:44,890 --> 00:16:45,780
So this start.

267
00:16:46,270 --> 00:16:50,680
So one index is left and you can see there is only one element present in the vertical.

268
00:16:50,950 --> 00:16:54,370
So what you will do, you will take that element and you will put it here.

269
00:16:55,840 --> 00:17:02,140
Simple, so what is the time, complexity, if you will, use Maksym prior to you so for analyzing the

270
00:17:02,140 --> 00:17:06,310
time complexity, let us first write the code and then we will analyze the time complexity.

271
00:17:09,690 --> 00:17:14,910
So we have to change, we have to do changes inside area so that it will be void, the name, let's

272
00:17:14,910 --> 00:17:17,069
say the name of the function is already.

273
00:17:23,660 --> 00:17:25,670
So what it will take, so it will take.

274
00:17:26,650 --> 00:17:32,480
Anti-Terrorism, but obviously the size of the anti-terrorist and are very bulky.

275
00:17:34,070 --> 00:17:39,560
Then why do you have to do so, we have to create Makhzoumi and we know how to kill, it makes me so

276
00:17:39,560 --> 00:17:39,940
proud.

277
00:17:40,340 --> 00:17:42,680
I want to create a make some heap of integers.

278
00:17:42,680 --> 00:17:46,820
Let's say the name is Piku and obviously you have to include.

279
00:17:55,160 --> 00:18:00,980
Now, the first step is we will take we have to insert the first gay elements into the protocol, so

280
00:18:00,980 --> 00:18:02,650
we have to insert the first gay element.

281
00:18:02,670 --> 00:18:06,580
So the value of gays to for the first two elements inside our priority queue.

282
00:18:10,170 --> 00:18:15,450
So in the first two elements, first key elements inside our dequeue.

283
00:18:17,130 --> 00:18:19,320
So I have a function, B, Cadart Bush.

284
00:18:20,570 --> 00:18:22,640
What I will do, so I will give in.

285
00:18:24,200 --> 00:18:26,150
So after inserting the first elements.

286
00:18:28,740 --> 00:18:33,360
What I have to do, so if you remember, I have to take a variable I saw the value of I will start from

287
00:18:33,370 --> 00:18:36,360
Key and I left and I placeless.

288
00:18:37,170 --> 00:18:38,370
I will do some work here.

289
00:18:38,910 --> 00:18:41,990
And again, if you remember, I also take a point to start.

290
00:18:42,000 --> 00:18:43,890
So start will start from zero.

291
00:18:45,660 --> 00:18:52,320
So you can see so I am taking the point, the first one is this dart pointer and this is was this was

292
00:18:52,320 --> 00:18:53,160
my appointer.

293
00:18:53,790 --> 00:18:55,620
So I started from this index.

294
00:18:56,190 --> 00:18:57,570
I started from this index.

295
00:18:57,580 --> 00:19:00,480
So this index is zero one and two, you can see.

296
00:19:01,650 --> 00:19:11,400
So I said starting from two, so two is actually key and similarly I starting from K and so start will

297
00:19:11,400 --> 00:19:12,180
start from zero.

298
00:19:13,660 --> 00:19:20,410
Now, what we have to do, so this index, so don't my editors and put so what will be put off start?

299
00:19:21,540 --> 00:19:28,350
So in the start, I have to get the topmost element, so how to get up must be Coudert up, so it will

300
00:19:28,350 --> 00:19:34,260
give me the maximum element and after getting the maximum limit, we have to also remove from the priority.

301
00:19:34,280 --> 00:19:40,650
You know, after knowing what we have to do, we have to start placeless and then we have to insert

302
00:19:40,650 --> 00:19:43,770
the i8 element, insert into our biodegrades will be gardot.

303
00:19:45,000 --> 00:19:49,230
Bush, I have to push a little bit, so in but off I.

304
00:19:50,820 --> 00:19:57,570
So I am pushing a settlement, so this is a and then what will happen, I placeless, simple, not after

305
00:19:57,570 --> 00:19:58,200
doing this.

306
00:19:59,540 --> 00:20:01,470
After doing this, what would I have to do?

307
00:20:01,490 --> 00:20:06,310
So there will be some elements that will be left inside our priority queue.

308
00:20:06,770 --> 00:20:09,140
So while the priority is not empty.

309
00:20:15,460 --> 00:20:23,050
So while the Braddick is not empty, what we have to do so in Batoff start, where does it start?

310
00:20:23,080 --> 00:20:24,220
So this is actually.

311
00:20:25,340 --> 00:20:26,990
B, Cadart top.

312
00:20:29,480 --> 00:20:31,040
And again, Bidgood ARTPOP.

313
00:20:33,390 --> 00:20:36,960
And start placeless, simple, so that's all we have to do.

314
00:20:36,990 --> 00:20:40,140
So this is now let's test our code.

315
00:20:40,140 --> 00:20:42,060
So let us clear denarii.

316
00:20:45,010 --> 00:20:51,820
And let's say the elements are dead certain, 12, six, seven and nine.

317
00:20:54,530 --> 00:21:01,670
And let's say the value of care is actually three and we will call it a function.

318
00:21:01,940 --> 00:21:03,280
So this is case already.

319
00:21:04,130 --> 00:21:05,450
I have to parse two things.

320
00:21:06,780 --> 00:21:09,490
So let us pass the Portelli.

321
00:21:10,880 --> 00:21:13,530
Number of elements is faith and the value of Kastari.

322
00:21:15,240 --> 00:21:17,640
Now, after doing this letter, spent nearly.

323
00:21:23,020 --> 00:21:24,700
OK, so this will be fine, if not.

324
00:21:35,830 --> 00:21:37,960
So this is my complete call now.

325
00:21:37,970 --> 00:21:40,690
Let's take this example, 10, 12, six, seven, nine.

326
00:21:42,260 --> 00:21:43,550
And let's see what will happen.

327
00:21:46,750 --> 00:21:50,340
So 10, 12, six, seven and nine, so I have this, Eddie.

328
00:21:52,750 --> 00:22:00,670
This is 10, then 12, then six, then seven, then nine and the Valley of KS actually, so three,

329
00:22:00,940 --> 00:22:03,790
a value of KS three, correct.

330
00:22:06,410 --> 00:22:10,310
And these are the indexes, zero, one, two, three and four.

331
00:22:11,070 --> 00:22:13,880
Now I am creating a maximum priority, correct?

332
00:22:13,940 --> 00:22:17,330
I am pushing the first key elements for the value of Kastari.

333
00:22:17,330 --> 00:22:20,510
So push the first three elements into our priority queue.

334
00:22:20,990 --> 00:22:23,690
So this is my priority, which is containing three elements.

335
00:22:24,230 --> 00:22:25,740
I pushed and then I pushed.

336
00:22:25,790 --> 00:22:27,770
Well, then I pushed six correct.

337
00:22:28,520 --> 00:22:29,650
Start as a zero.

338
00:22:29,990 --> 00:22:31,430
So this is your start.

339
00:22:32,760 --> 00:22:33,580
I is gay.

340
00:22:33,930 --> 00:22:37,080
So gays basically three, so this is are a.

341
00:22:39,900 --> 00:22:40,370
Correct.

342
00:22:41,860 --> 00:22:48,520
Now, of this brought up, what is the maximum elements or the maximum element, so put at it, but

343
00:22:48,520 --> 00:22:52,750
at this stage next so remove 2L and put at the START index.

344
00:22:52,780 --> 00:22:54,490
So this then will become tool.

345
00:22:56,420 --> 00:23:01,940
So I am writing below, so this pen will become, well, correct then, Bob.

346
00:23:02,420 --> 00:23:06,620
So Bob Delimit start to start is going to come here.

347
00:23:08,950 --> 00:23:14,320
Then push the Taliban today at seven, so push the element seven.

348
00:23:15,310 --> 00:23:16,450
Then C++.

349
00:23:17,790 --> 00:23:19,170
So I will come here.

350
00:23:20,250 --> 00:23:20,660
Correct.

351
00:23:22,260 --> 00:23:28,410
Now, again, so big, what is the maximum limit, so the maximum limit is so one thing that you can

352
00:23:28,410 --> 00:23:34,650
notice my size of Diplodocus always Gayathri so the size of the particular is three, always another

353
00:23:34,650 --> 00:23:38,610
maximum limitation support element 10 at the starting position.

354
00:23:39,130 --> 00:23:41,860
So I will push down here then Bob.

355
00:23:41,910 --> 00:23:46,110
So we already Bob then started as press so start will move ahead.

356
00:23:49,240 --> 00:23:54,010
Now, Bush, the eighth element, that element is nine, so push the element nine.

357
00:23:54,670 --> 00:23:58,740
Now, again, the size and priority is three and the eight plus plus.

358
00:23:58,990 --> 00:24:02,140
So remove I and I will reach basically the end of the.

359
00:24:04,620 --> 00:24:08,190
So when I will reach the end of the address, this condition will become false.

360
00:24:09,600 --> 00:24:15,060
And I will reach at this point line number 20 now, how many elements is containing?

361
00:24:15,060 --> 00:24:16,680
So it is containing three elements.

362
00:24:17,790 --> 00:24:24,090
And what I'm doing and put off start this up, so it is the topmost element, nine, so remove nine.

363
00:24:25,310 --> 00:24:30,590
And put it here, so remove six foot nine and then you do pop.

364
00:24:30,620 --> 00:24:32,970
So we already started to split.

365
00:24:33,050 --> 00:24:34,510
So Start is going to come here.

366
00:24:35,560 --> 00:24:40,720
Then again, is not empty Dopp elements of that top is seven.

367
00:24:42,270 --> 00:24:48,930
The upper limit is seven, right, seven, so right, seven here and then you will do you'll pop the

368
00:24:48,950 --> 00:24:56,100
element and start plus place to start is going to come here and mop up the elements, six foot six and

369
00:24:56,100 --> 00:24:58,950
then start placeless and then you try to keep them pretty.

370
00:24:58,980 --> 00:25:00,920
So when you try to keep them pretty, you will stop.

371
00:25:00,930 --> 00:25:01,860
And this is reality.

372
00:25:02,220 --> 00:25:07,110
So it stays 10, then 12, 10, nine, seven and six.

373
00:25:07,500 --> 00:25:09,150
So this is your final output.

374
00:25:11,390 --> 00:25:17,750
This is this area sorted in descending order, decreasing order, and you can see so the value of gave

375
00:25:17,750 --> 00:25:22,850
us three and our initial Aribert was only Shilbury then then 12, then six, then seven.

376
00:25:22,850 --> 00:25:25,980
And then you can see so many shipping went position.

377
00:25:26,120 --> 00:25:31,760
Well, one position six, two positions or two operation is allowed, one seven one position and nine

378
00:25:31,760 --> 00:25:32,510
one position.

379
00:25:32,810 --> 00:25:34,130
So everything is working fine.

380
00:25:34,910 --> 00:25:36,680
Now let us try to test our program.

381
00:25:36,870 --> 00:25:38,180
Let's try to test double gold.

382
00:25:43,900 --> 00:25:46,630
So see our iReporters coming out right now.

383
00:25:46,690 --> 00:25:49,060
That is sorted in descending order.

384
00:25:49,810 --> 00:25:51,130
Ten, nine, seven, six.

385
00:25:52,690 --> 00:25:56,320
Now, let's try to analyze the time and the space complexity of what our solution.

386
00:25:58,810 --> 00:25:59,950
So what I'm doing here.

387
00:26:01,800 --> 00:26:08,370
This loop will run good times and push function, so if you remember, if there are any elements to

388
00:26:08,370 --> 00:26:13,020
the Bush function will take for pushing one element, that it will take longer in time.

389
00:26:13,740 --> 00:26:14,160
Correct.

390
00:26:14,820 --> 00:26:21,410
So now this loop is going to run good times and the size of the priority is key.

391
00:26:21,660 --> 00:26:24,090
So the time complexity schlocky.

392
00:26:25,410 --> 00:26:30,990
So for this part, the time complexities gridlocking so gay is the number of elements present in my

393
00:26:30,990 --> 00:26:31,670
priority queue.

394
00:26:33,050 --> 00:26:39,860
So now decide also how many times this loop will run, so this loop is going to run and minus goodtimes.

395
00:26:41,220 --> 00:26:49,070
And in each loop, what work I am doing, so this is constant worktop, constant pop, I am popping.

396
00:26:49,080 --> 00:26:50,910
So how much time, Logi?

397
00:26:52,140 --> 00:26:57,150
So far, a whopping one element, the time complexity was a log of N if and is the number of elements.

398
00:26:57,340 --> 00:26:59,350
So in this case, the number of elements is key.

399
00:26:59,370 --> 00:27:03,720
So that's why locating then this is constant work and again, push.

400
00:27:04,050 --> 00:27:06,480
So log Gabler's location to lock.

401
00:27:09,410 --> 00:27:14,690
So ultimately, what is my complex complexity is to look, you can remove to the time complexities and

402
00:27:14,690 --> 00:27:17,210
mindlessly multiply lucky.

403
00:27:18,230 --> 00:27:21,410
So this is the time complexity now for this part.

404
00:27:24,810 --> 00:27:32,190
So how many elements have left, so if you see and minus key elements has been pushed to its correct

405
00:27:32,190 --> 00:27:37,620
position, so this loop will run times and this is what is constant.

406
00:27:38,850 --> 00:27:40,860
This work is lockyear time.

407
00:27:42,150 --> 00:27:43,630
And this work is constrained.

408
00:27:43,800 --> 00:27:46,320
So finally, this is the time complexity for this part.

409
00:27:46,350 --> 00:27:52,240
Now we are going to add all these three time complexity and let's see what will be our final time complexity.

410
00:27:52,770 --> 00:27:54,420
So I have Killock.

411
00:27:56,130 --> 00:27:57,230
So this is Kellock.

412
00:27:58,210 --> 00:28:01,240
Now you can ride like this, so let's multiply.

413
00:28:01,270 --> 00:28:02,860
So this is an logi.

414
00:28:04,270 --> 00:28:06,130
Then minus Gailhaguet.

415
00:28:07,160 --> 00:28:09,780
And then this one, so this is Golok.

416
00:28:12,050 --> 00:28:16,160
So these two will cancel out each other and now let us combine this.

417
00:28:16,190 --> 00:28:20,410
So this is big off and plus gay.

418
00:28:21,510 --> 00:28:22,260
Lakki.

419
00:28:23,400 --> 00:28:23,860
Correct.

420
00:28:24,210 --> 00:28:29,970
Now, the value of and will be, Aniceto, the number of elements present in our area, so the value

421
00:28:29,970 --> 00:28:36,240
will be returned to the buyer of five 10 to the power six, and the value of it will be like three,

422
00:28:36,540 --> 00:28:38,460
five, 10 or 20.

423
00:28:38,700 --> 00:28:42,290
So basically I can see the value of and is much, much greater then.

424
00:28:43,260 --> 00:28:48,690
So basically, can I say that the complexity is nothing, but it is an logi.

425
00:28:50,470 --> 00:28:53,560
Simple and see if the value of a very small.

426
00:28:54,450 --> 00:29:00,870
If the value of small so lucky, if you will use Locata, the value will always decrease.

427
00:29:01,200 --> 00:29:03,560
Loggers are decreasing function, it will decrease your value.

428
00:29:03,870 --> 00:29:05,230
So the value is very small.

429
00:29:05,430 --> 00:29:09,510
So that means logging will also be very, very small.

430
00:29:10,050 --> 00:29:11,670
So it will also be very, very small.

431
00:29:12,090 --> 00:29:16,410
So again, what you can do so you can say the maritime complexities big of an.

432
00:29:18,700 --> 00:29:23,480
So that time complexities big often, and this is much, much better than using any sorting algorithm.

433
00:29:24,220 --> 00:29:28,510
So we discussed if you blindly use any sorting algorithm, that a time complexity actually was and login,

434
00:29:28,990 --> 00:29:33,010
but using the MAKSYM prior to our time complexities big off and.

435
00:29:34,120 --> 00:29:39,670
And now let's discuss this space complexity, so we are just creating a priority queue and the priority

436
00:29:39,670 --> 00:29:41,410
queue will contain key elements.

437
00:29:41,410 --> 00:29:43,780
So the space complexities big off key.

438
00:29:44,050 --> 00:29:48,220
Again, the value of care will be very small, three, five, 10 or 20.

439
00:29:48,430 --> 00:29:51,670
So you can see that the space complexity is big often.

440
00:29:53,130 --> 00:29:59,550
So this is the final time complexity, which is linear and this is defined space complexity, which

441
00:29:59,550 --> 00:30:03,810
is constant big often because the value of K is going to be very, very small.

442
00:30:03,930 --> 00:30:05,760
So I hope you understood the solution.

443
00:30:06,660 --> 00:30:12,210
So if you have any doubt, the best way is basically to take one example and to try it and discovered

444
00:30:12,600 --> 00:30:13,840
you will understand everything.

445
00:30:14,520 --> 00:30:15,920
So I will see you in the next one.

446
00:30:16,250 --> 00:30:16,460
Bye.