1
00:00:03,570 --> 00:00:04,230
Hi, everyone.

2
00:00:04,260 --> 00:00:09,550
So in this video, we are going to solve this question, find the majority element inside the.

3
00:00:10,190 --> 00:00:12,360
OK, so what is the majority element?

4
00:00:12,570 --> 00:00:18,480
So element is to be a majority element if it appears more than and by two times, OK.

5
00:00:19,050 --> 00:00:21,670
What is and and is basically the size of the area.

6
00:00:22,100 --> 00:00:22,530
OK.

7
00:00:22,710 --> 00:00:24,280
And is basically the size of the area.

8
00:00:24,450 --> 00:00:30,750
So if there is an element, if there is an element that appears more then and by two times OK, so more

9
00:00:30,750 --> 00:00:35,190
then and by two times then that element will be called as majority element.

10
00:00:35,770 --> 00:00:38,930
OK, let's take some example to understand the question.

11
00:00:38,940 --> 00:00:43,030
OK, so in this case, the value of N is basically three.

12
00:00:43,140 --> 00:00:47,730
OK, size of that is basically three and we can see the majority element.

13
00:00:47,790 --> 00:00:48,160
OK.

14
00:00:48,180 --> 00:00:50,880
In this case, the majority element is basically three.

15
00:00:51,240 --> 00:00:55,470
You can see three is appearing two times, three is appearing two times.

16
00:00:55,470 --> 00:01:01,020
And what is and by two so and by two is basically three by two which is basically one OK.

17
00:01:01,230 --> 00:01:03,600
And two is basically greater than one.

18
00:01:03,720 --> 00:01:06,870
So greater then and by two OK.

19
00:01:06,900 --> 00:01:09,130
So in this case our majority element is three.

20
00:01:09,180 --> 00:01:10,680
OK, so we have to return three.

21
00:01:10,920 --> 00:01:15,240
We have to find the majority element and we have to return the majority element.

22
00:01:16,020 --> 00:01:17,490
Let us consider this example.

23
00:01:17,910 --> 00:01:19,080
So what is the value of N?

24
00:01:19,530 --> 00:01:22,940
So the value of N is basically one, two, three, four, five, six and seven.

25
00:01:22,950 --> 00:01:24,630
So the value of end is basically seven.

26
00:01:24,840 --> 00:01:28,910
What is and by doing so and by two is basically three.

27
00:01:29,250 --> 00:01:32,420
Now see in this case the majority element is basically two.

28
00:01:32,910 --> 00:01:37,560
So the majority element is basically two and two is appearing basically four times.

29
00:01:38,640 --> 00:01:42,750
Two is appearing in the area four times and four is basically greater than three.

30
00:01:43,110 --> 00:01:44,310
Four is good, then three.

31
00:01:44,520 --> 00:01:46,140
Now, let us consider this example.

32
00:01:46,350 --> 00:01:48,750
Let us try to find out the value of end first.

33
00:01:48,750 --> 00:01:52,770
So the value of N is basically one, two, three, four, five, six, seven, eight, nine and ten.

34
00:01:53,370 --> 00:01:58,350
OK, so the value of this basically ten letters and by two, so end by two is basically five.

35
00:01:58,740 --> 00:02:00,870
Now count the occurrence of four.

36
00:02:00,870 --> 00:02:04,970
So one, two, three, four, five and six.

37
00:02:05,280 --> 00:02:10,949
So basically in this case, my majority element is four because it is appearing six times and six is

38
00:02:10,949 --> 00:02:18,330
basically greater than five then and by the majority element is that element that will appear more than.

39
00:02:19,300 --> 00:02:22,570
And by two times now, let us consider this example.

40
00:02:23,380 --> 00:02:30,010
So in this example, the value of N is basically five nowadays and by two so and by two is basically

41
00:02:30,010 --> 00:02:30,300
two.

42
00:02:30,550 --> 00:02:33,610
In this case, majority element is not there.

43
00:02:33,820 --> 00:02:35,020
So in this case.

44
00:02:36,040 --> 00:02:42,430
Majority element does not present a majority element is not present, but.

45
00:02:43,440 --> 00:02:46,330
We can assume that the majority element is always present.

46
00:02:46,650 --> 00:02:47,800
Now see the question.

47
00:02:48,240 --> 00:02:51,110
So this is basically a precaution.

48
00:02:51,280 --> 00:02:52,650
Again, majority element.

49
00:02:52,800 --> 00:02:58,410
And the question is, we can always assume that basically the majority element will always exist in

50
00:02:58,410 --> 00:02:58,610
there.

51
00:02:59,070 --> 00:03:01,670
We can assume that the majority element will always exist.

52
00:03:01,890 --> 00:03:05,330
So that means we will not receive input like this.

53
00:03:05,940 --> 00:03:07,950
We will not receive input like this.

54
00:03:07,950 --> 00:03:11,760
So we can safely assume that the majority element will always be there.

55
00:03:12,360 --> 00:03:18,120
We can assume that the majority element will always be there and input like this will not be there and

56
00:03:18,150 --> 00:03:19,440
put like this will not be there.

57
00:03:19,620 --> 00:03:21,510
Now, let us try to solve this question.

58
00:03:22,440 --> 00:03:25,630
So let's discuss various approaches of solving this question.

59
00:03:25,890 --> 00:03:30,460
Now, first, let us discuss the very simple approach, the brute force approach.

60
00:03:30,780 --> 00:03:32,460
So what is the new approach?

61
00:03:32,520 --> 00:03:33,750
So naive approach.

62
00:03:33,870 --> 00:03:34,550
What it will say.

63
00:03:34,770 --> 00:03:37,350
So you have a Netty and you have elements.

64
00:03:38,190 --> 00:03:39,450
So what is the new approach?

65
00:03:39,450 --> 00:03:43,050
And I will say find the occurrence of this element.

66
00:03:43,110 --> 00:03:45,240
So what I will do, I will pick this element.

67
00:03:45,240 --> 00:03:50,630
I will pick this element and I will find its occurrence by iterating over that completely.

68
00:03:50,910 --> 00:03:56,130
Now, I will check this element and now I will find the occurrence of this element or the completely

69
00:03:56,760 --> 00:03:59,730
similarly pick the third element and find a talkathons.

70
00:04:00,000 --> 00:04:05,290
So brute force is very simple, but we have to do I will pick one element and I will try to find it

71
00:04:05,730 --> 00:04:06,780
over the complete area.

72
00:04:06,960 --> 00:04:13,590
If I'm able to find an element, if I am able to find an element whose occurrence is basically guerdon

73
00:04:13,590 --> 00:04:15,740
and Bitel, I will return that element.

74
00:04:15,990 --> 00:04:17,350
I will return that element.

75
00:04:17,610 --> 00:04:20,329
So what be the time complexity so complex?

76
00:04:20,339 --> 00:04:21,130
It is very simple.

77
00:04:21,180 --> 00:04:25,590
We are picking each and every element and I will try to find the occurrence of that element.

78
00:04:25,770 --> 00:04:30,900
So time complexity is basically and square and the space complexity is basically big often.

79
00:04:31,200 --> 00:04:32,710
So this is the brute force approach.

80
00:04:33,750 --> 00:04:36,420
Now, one more thing, since what is the majority element?

81
00:04:36,720 --> 00:04:41,070
So majority element is that element whose occurrence is basically guerdon end by two.

82
00:04:41,310 --> 00:04:45,030
So that means we can have only one element as the majority element.

83
00:04:45,180 --> 00:04:48,780
OK, so there will be only one majority element.

84
00:04:49,790 --> 00:04:54,740
We cannot have more than one majority element because their definition of majority element is basically

85
00:04:54,740 --> 00:04:57,250
that element whose occurrence is greater than ENVI two.

86
00:04:57,680 --> 00:05:01,340
So they will be always one element that will be the majority element.

87
00:05:02,270 --> 00:05:04,130
Now, let us discuss the second approach.

88
00:05:05,390 --> 00:05:11,100
So in second approach, what we can do, we can take the help of Hashmat, we can take the help of map.

89
00:05:11,150 --> 00:05:16,320
So what we will do, so we will store element and we restore its count, give a loopier.

90
00:05:16,400 --> 00:05:18,970
OK, so this will be my key element.

91
00:05:18,990 --> 00:05:20,480
And so what will happen?

92
00:05:20,510 --> 00:05:21,710
So this will be my area.

93
00:05:21,980 --> 00:05:26,480
But I will also I will iterate over the area and I will fill this hash map.

94
00:05:27,540 --> 00:05:34,250
I will fill the hash map, so after reading over the completely, my hash map will be ready now.

95
00:05:34,280 --> 00:05:35,640
It will do so.

96
00:05:35,670 --> 00:05:36,860
Let us take an example.

97
00:05:36,860 --> 00:05:37,190
Look.

98
00:05:37,440 --> 00:05:39,900
So let us take a small example.

99
00:05:39,900 --> 00:05:41,790
Let's say this is my example, three to three.

100
00:05:42,940 --> 00:05:44,510
OK, now let us make of it.

101
00:05:44,800 --> 00:05:51,310
Let us say it so after trading threes, basically a beating two times and two is basically a beating

102
00:05:51,310 --> 00:05:51,820
when times.

103
00:05:51,850 --> 00:05:53,500
OK, so this would be my shrimp.

104
00:05:54,190 --> 00:05:56,200
Now, what I will do with the hash map is ready.

105
00:05:56,440 --> 00:05:58,200
We will address or the hash map.

106
00:05:58,810 --> 00:06:01,100
And when we are dealing with the Hashmat, we can check.

107
00:06:01,510 --> 00:06:06,610
So if there is an element whose occurrence is basically good and by two, if there is an element, we

108
00:06:06,610 --> 00:06:07,520
will return the key.

109
00:06:07,570 --> 00:06:08,410
OK, the whiskey.

110
00:06:09,370 --> 00:06:10,440
So I will return the key.

111
00:06:10,500 --> 00:06:11,650
OK, very, very simple.

112
00:06:11,950 --> 00:06:15,300
So what will be the time and the space complexities or the time complexity.

113
00:06:15,310 --> 00:06:19,780
We are just iterating over the array and then we will try to add hash episode time.

114
00:06:19,780 --> 00:06:25,140
Complexity is big often and the space complexity is also big often because we are using hash map.

115
00:06:26,050 --> 00:06:29,080
OK, so space complexity will be big often.

116
00:06:29,110 --> 00:06:30,920
Now you can also see the space complex.

117
00:06:30,940 --> 00:06:37,750
It is big off and too, because we can say the majority element, we can always assume that the majority

118
00:06:37,750 --> 00:06:40,230
element will always be there as given the question.

119
00:06:40,840 --> 00:06:44,320
So basically the size of the Hashmat will basically be.

120
00:06:44,320 --> 00:06:46,180
And by doing it, by doing basically nothing.

121
00:06:46,210 --> 00:06:47,410
It is just big often.

122
00:06:47,440 --> 00:06:48,970
OK, so I will say.

123
00:06:49,970 --> 00:06:53,060
The space, complexity and that complexity, both are linear.

124
00:06:54,430 --> 00:06:56,830
OK, now let's discuss the third approach.

125
00:06:57,760 --> 00:06:58,940
So what is the third approach?

126
00:06:59,320 --> 00:07:02,800
So in third approach, this is basically called the starting approach.

127
00:07:02,980 --> 00:07:08,170
So what we will do in sorting so let's say this is really what we will do.

128
00:07:08,170 --> 00:07:10,590
We will basically start daddy, OK?

129
00:07:10,620 --> 00:07:12,420
So after sorting the idea, what will happen?

130
00:07:12,430 --> 00:07:16,100
So after sorting the idea, what will be my majority element?

131
00:07:16,120 --> 00:07:17,830
OK, so what is the majority element?

132
00:07:17,830 --> 00:07:22,270
Majority element is that element which is all and vital times.

133
00:07:22,510 --> 00:07:25,300
So after sorting the area, I will find out the main element.

134
00:07:25,930 --> 00:07:27,050
This is my element.

135
00:07:27,070 --> 00:07:31,960
So what is is basically and vital and this will be my majority element.

136
00:07:34,000 --> 00:07:36,240
OK, so what I have to do, I have to do two steps.

137
00:07:36,820 --> 00:07:38,710
So first step is basically start the.

138
00:07:40,350 --> 00:07:43,240
First step is very simple, we just have to start the.

139
00:07:43,860 --> 00:07:48,870
And since the majority element is that element, which is appearing more then and two times so the size

140
00:07:48,870 --> 00:07:51,990
of the area is basically then we will find out the main element.

141
00:07:52,680 --> 00:07:56,370
And that element is basically the majority element.

142
00:07:56,400 --> 00:07:57,940
OK, very simple.

143
00:07:58,530 --> 00:08:03,480
So what would be the time complexity since we are using starting small time complexities and log-in

144
00:08:03,780 --> 00:08:07,540
and then we can find out the in question time and then we can return them.

145
00:08:08,400 --> 00:08:10,860
And the space, it is basically big often.

146
00:08:12,010 --> 00:08:16,240
So this is the third approach starting now, let let's discuss the best approach.

147
00:08:16,390 --> 00:08:19,520
OK, let's discuss the best approach.

148
00:08:19,540 --> 00:08:24,910
So this is approach four, and this is basically called voting approach.

149
00:08:24,910 --> 00:08:26,230
More swotting approach.

150
00:08:26,510 --> 00:08:28,340
OK, Moray's wording approach.

151
00:08:28,390 --> 00:08:32,710
So this is the best approach now where this approach will do so.

152
00:08:32,860 --> 00:08:34,090
What is the best?

153
00:08:34,090 --> 00:08:35,350
First, discuss the intuition.

154
00:08:35,559 --> 00:08:39,980
OK, now there exists a majority element.

155
00:08:40,000 --> 00:08:42,600
OK, so we know majority element exists.

156
00:08:42,940 --> 00:08:44,690
So what is the majority element?

157
00:08:44,730 --> 00:08:49,090
The majority element is that element which will appear more than two times, OK.

158
00:08:50,100 --> 00:08:53,370
And these are sort of the elements of elements.

159
00:08:53,760 --> 00:08:57,420
So what I will do, so I will mark the majority element.

160
00:08:57,540 --> 00:09:02,670
So I'm discussing the inclusion, so I will mark the majority element plus one.

161
00:09:02,970 --> 00:09:08,130
OK, if there's a majority element, that means I will market my platform and that's all the elements

162
00:09:08,130 --> 00:09:12,830
will be marked as minus one sentence majority element of and by two.

163
00:09:13,170 --> 00:09:19,800
So if you will add these two plus and minus one, finally your output will be plus one, not necessary

164
00:09:19,800 --> 00:09:20,240
plus one.

165
00:09:20,250 --> 00:09:22,120
Basically it can be positive.

166
00:09:22,170 --> 00:09:25,560
OK, it can be anything plus two plus three plus four.

167
00:09:25,560 --> 00:09:32,060
Anything but the output will be positive, very positive because the majority elements, they are appearing

168
00:09:32,230 --> 00:09:36,650
then and vital times and the rest of the elements are basically Leiston and by two times.

169
00:09:36,840 --> 00:09:41,280
So I am making the majority element s plus one, and that's two of the elements on Minocin.

170
00:09:41,490 --> 00:09:45,450
So if you will add the majority element with the rest of the elements.

171
00:09:46,580 --> 00:09:48,470
The output will be a positive element.

172
00:09:48,500 --> 00:09:51,820
OK, so this is the indication now let let's discuss the approach.

173
00:09:52,160 --> 00:10:00,260
So the approach is very simple, but what more voting algorithms is so consider you have elementally.

174
00:10:01,900 --> 00:10:08,140
You have elements, and I am saying this element is basically a majority element element, the majority

175
00:10:08,140 --> 00:10:08,590
element.

176
00:10:08,860 --> 00:10:15,820
So what do we do if we will cancel out each occurrence of element, each with other elements that are

177
00:10:15,820 --> 00:10:16,810
different from each?

178
00:10:17,260 --> 00:10:20,620
Then it will exist until the end if it is a majority element.

179
00:10:21,070 --> 00:10:22,870
OK, I am repeating myself.

180
00:10:23,710 --> 00:10:24,940
The approach is very simple.

181
00:10:25,210 --> 00:10:28,330
It is it will use the endurance or element.

182
00:10:28,330 --> 00:10:30,460
It is basically a majority element.

183
00:10:30,820 --> 00:10:34,600
OK, I'm saying I am assuming element is majority element.

184
00:10:34,900 --> 00:10:39,520
Now if I will cancel out all the elements or these are all of elements.

185
00:10:40,960 --> 00:10:47,350
So if you will cancel, if you will do it, which is the majority element, minus all the other elements.

186
00:10:50,220 --> 00:10:51,960
E minus all of their elements.

187
00:10:52,470 --> 00:10:53,340
So what will happen?

188
00:10:53,640 --> 00:10:56,370
So basically it will exist till the end.

189
00:10:56,610 --> 00:10:58,980
It will exist till the end of time.

190
00:10:58,980 --> 00:11:07,050
Doing so if I will cancel out each occurrence of an element e from the all other elements that are different

191
00:11:07,050 --> 00:11:12,420
from E, then it will exist till the end if it is the majority element.

192
00:11:13,080 --> 00:11:14,840
OK, very simple approach.

193
00:11:15,000 --> 00:11:16,950
Let us take an example to understand it.

194
00:11:17,860 --> 00:11:20,250
We will take few example and then we will write the code.

195
00:11:20,730 --> 00:11:24,390
So let us take this example three to three.

196
00:11:26,510 --> 00:11:27,200
Three to three.

197
00:11:28,750 --> 00:11:34,030
So initially, I don't know what is the majority element, so let us assume something, let's see.

198
00:11:34,420 --> 00:11:40,840
My candidate of the majority element is the first element three and obviously each count is basically

199
00:11:40,840 --> 00:11:41,080
one.

200
00:11:41,870 --> 00:11:47,410
OK, so what we have to do, if I will encounter a different element, I will subtract, I'm assuming

201
00:11:47,410 --> 00:11:50,020
my candidate for the majority element history.

202
00:11:50,020 --> 00:11:53,410
And it's going is one now I read from the Nitrate or the Eddie.

203
00:11:54,390 --> 00:11:58,770
So this is element, compare it to what they have to do, we have to subtract.

204
00:11:59,070 --> 00:11:59,930
So what will happen?

205
00:12:00,300 --> 00:12:01,770
I will make the count zero.

206
00:12:01,950 --> 00:12:03,410
OK, three and two, they are different.

207
00:12:03,420 --> 00:12:05,180
So I will do count minus minus.

208
00:12:05,190 --> 00:12:08,700
I will make the count zero after doing the count zero.

209
00:12:09,090 --> 00:12:12,960
That means this is not my majority element because the count zero.

210
00:12:13,170 --> 00:12:14,150
So I will update.

211
00:12:14,520 --> 00:12:18,890
So my new candidate element is basically two and my count is one.

212
00:12:19,560 --> 00:12:24,480
Now I am saying that two is the candidate for the majority element and disappearing one time.

213
00:12:24,810 --> 00:12:27,630
Now let us continue our so I have elementary.

214
00:12:27,900 --> 00:12:31,170
So elementary is basically different than to what I will do.

215
00:12:31,170 --> 00:12:31,930
I will subtract.

216
00:12:31,980 --> 00:12:33,310
OK, you can see here.

217
00:12:33,450 --> 00:12:35,370
So what we can do, we can see here.

218
00:12:36,470 --> 00:12:41,540
Is the majority element, I'm subtracting the majority aluminum, subtracting the count from all of

219
00:12:41,540 --> 00:12:42,240
that element.

220
00:12:42,290 --> 00:12:46,070
OK, and if it is a majority, it will appear it will exist till then.

221
00:12:46,290 --> 00:12:46,640
OK.

222
00:12:48,490 --> 00:12:52,730
Now, 20, 20, they are different, so I will subtract.

223
00:12:52,750 --> 00:12:55,400
So the count will become zero if the count becomes zero.

224
00:12:55,420 --> 00:12:59,080
It's time to update your candidate for the majority elements who can read history.

225
00:12:59,680 --> 00:13:01,650
And the count is basically one.

226
00:13:01,900 --> 00:13:02,890
Then what will happen?

227
00:13:03,740 --> 00:13:05,420
Let us continue attracting the ordinary.

228
00:13:05,450 --> 00:13:09,600
Now the jury will finish and your candidate is basically three, which is your answer.

229
00:13:10,270 --> 00:13:11,810
In this case, three is the answer.

230
00:13:12,400 --> 00:13:13,520
So that's how it is working.

231
00:13:13,540 --> 00:13:15,280
Let us take this example also.

232
00:13:15,910 --> 00:13:17,650
OK, so this is two to one one.

233
00:13:17,650 --> 00:13:18,220
One, two, two.

234
00:13:19,730 --> 00:13:27,920
So let's take this example to two, then I have one, one and one, then I have to do what we have to

235
00:13:27,920 --> 00:13:28,060
do.

236
00:13:28,070 --> 00:13:29,090
We have to assume first.

237
00:13:29,390 --> 00:13:32,720
So let us assume this is the candidate for the majority element.

238
00:13:32,750 --> 00:13:33,110
OK.

239
00:13:34,190 --> 00:13:38,390
So the candidate is basically do and each count is basically one.

240
00:13:38,420 --> 00:13:44,600
OK, so two is the candidate for the majority element because initially I have to assume, OK, now

241
00:13:44,600 --> 00:13:46,600
let's continue our trading already.

242
00:13:47,390 --> 00:13:49,630
So to two and two, they both are slim.

243
00:13:49,640 --> 00:13:55,790
So what I will do, I will increase the council count plus plus or count will become two now one and

244
00:13:55,790 --> 00:13:57,610
two, they are different.

245
00:13:57,950 --> 00:14:03,170
When is the current element and two I am assuming is the majority element since the candidate is different,

246
00:14:03,170 --> 00:14:03,870
elements are different.

247
00:14:03,890 --> 00:14:06,900
I will do count minus minus so count will become one.

248
00:14:07,490 --> 00:14:09,560
So what I am doing if same.

249
00:14:10,880 --> 00:14:18,780
Then mattilda, count, placeless, if different in the elzbieta, they are different if different.

250
00:14:18,800 --> 00:14:26,930
I will do count minus minus and if the count becomes zero, if the count becomes zero, that means update

251
00:14:27,200 --> 00:14:30,770
your majority element to update your candidate for the majority element.

252
00:14:30,950 --> 00:14:33,890
OK, now compare one with two.

253
00:14:34,580 --> 00:14:35,540
So they are different.

254
00:14:36,620 --> 00:14:37,340
They are different.

255
00:14:37,340 --> 00:14:40,340
And what will do count minus minus count will become zero.

256
00:14:40,340 --> 00:14:44,000
As soon as the count will become zero, it's time to update your majority element.

257
00:14:44,360 --> 00:14:49,760
So now the candidate is won, OK, now the candidate is won and its count is one.

258
00:14:50,270 --> 00:14:51,860
OK, one is updating one time.

259
00:14:52,460 --> 00:14:54,410
Now let's continue our trading order.

260
00:14:54,560 --> 00:14:56,120
So I have one.

261
00:14:56,150 --> 00:14:56,780
I have one.

262
00:14:57,230 --> 00:14:59,690
So I will do count plus plus or count this to.

263
00:15:00,770 --> 00:15:04,250
I have to so what I will do, so I think this is one.

264
00:15:04,700 --> 00:15:07,520
OK, so I have to and this is the candidate element.

265
00:15:07,550 --> 00:15:12,110
This is the majority element, which is one what will do I will do count minus, minus account becomes

266
00:15:12,110 --> 00:15:12,350
one.

267
00:15:13,130 --> 00:15:15,990
Now, again, I have to say no to anyone.

268
00:15:16,160 --> 00:15:16,880
They are different.

269
00:15:17,360 --> 00:15:21,560
So they will look on to minus minus since the count becomes a zero.

270
00:15:21,860 --> 00:15:23,160
If the count becomes zero.

271
00:15:23,180 --> 00:15:25,540
It's time to update their majority element.

272
00:15:25,580 --> 00:15:28,850
So the majority element is two and it's counted one.

273
00:15:29,120 --> 00:15:32,540
OK, so the majority element is to end its count is one.

274
00:15:32,810 --> 00:15:36,440
Finally, your error will end and this is your answer.

275
00:15:37,130 --> 00:15:39,190
OK, this is our majority element.

276
00:15:40,040 --> 00:15:40,980
This is the answer.

277
00:15:41,690 --> 00:15:43,090
So algorithm is very simple.

278
00:15:43,100 --> 00:15:45,170
What we are doing, we are subtracting.

279
00:15:45,170 --> 00:15:47,630
So Element E is the majority element.

280
00:15:48,020 --> 00:15:57,080
So subtract the count of majority element from the rest of the elements since E is the majority element.

281
00:15:57,090 --> 00:15:59,460
So it will remain till the end of the year.

282
00:15:59,630 --> 00:16:01,510
It will exist till the end of the year.

283
00:16:01,880 --> 00:16:04,310
So in this case, how many times two is appearing.

284
00:16:04,610 --> 00:16:05,540
So two is appearing.

285
00:16:05,540 --> 00:16:07,940
One, two, three, four.

286
00:16:08,210 --> 00:16:09,860
So two is appearing four times.

287
00:16:09,860 --> 00:16:12,500
How many times different elements are appearing so different.

288
00:16:12,500 --> 00:16:15,100
These three are different elements than the majority element.

289
00:16:15,800 --> 00:16:18,920
So the rest of the elements are appearing three times.

290
00:16:19,880 --> 00:16:21,440
So if you subtract the count.

291
00:16:22,850 --> 00:16:29,060
OK, the count, so the count is one, so basically, if you will subtract the count, since it is the

292
00:16:29,060 --> 00:16:31,540
majority elements or two will exist till the end.

293
00:16:31,730 --> 00:16:33,320
That's why two is existing till.

294
00:16:34,610 --> 00:16:36,050
Let's take one more example.

295
00:16:38,130 --> 00:16:40,260
Then after this example, we will write the code.

296
00:16:40,410 --> 00:16:48,390
OK, so four seven four four seven four four and nine four three logic is very simple.

297
00:16:49,050 --> 00:16:55,320
I will compare the current element of the eddy with the candidate, with the majority element candidate

298
00:16:55,320 --> 00:16:56,040
if they are same.

299
00:16:57,160 --> 00:17:01,940
I will do countless place else, but they are different if they are different.

300
00:17:02,410 --> 00:17:07,000
I will look on minus minus if the count becomes zero.

301
00:17:07,240 --> 00:17:13,599
That means it's time to update the candidate and update the majority of their candidate element.

302
00:17:13,640 --> 00:17:16,210
Now, initially, I don't know which is the majority element.

303
00:17:16,220 --> 00:17:22,010
So my candidate is basically four and the count is basically one.

304
00:17:22,060 --> 00:17:23,650
OK, for disappearing one time.

305
00:17:23,829 --> 00:17:25,390
Now let's get rid of a diary.

306
00:17:25,470 --> 00:17:26,920
OK, let's start out reading.

307
00:17:28,180 --> 00:17:29,990
Seven, seven and four.

308
00:17:30,010 --> 00:17:34,480
They are different if they are different, I will look out minus minus this account becomes zero.

309
00:17:34,690 --> 00:17:39,300
If the count zero, it's time to update OK, the count update.

310
00:17:40,000 --> 00:17:43,330
So seven is the candidate element and its count is one.

311
00:17:43,330 --> 00:17:45,640
Seven is appearing one times again, four.

312
00:17:45,880 --> 00:17:47,850
So four and seven, they are different.

313
00:17:48,010 --> 00:17:52,030
So if they are different, Waterloo count minus minus so count becomes zero.

314
00:17:52,390 --> 00:17:55,940
If the count zero we will update the majority element.

315
00:17:55,940 --> 00:18:01,060
So four and the count of 47 for disappearing one times again after.

316
00:18:01,090 --> 00:18:03,510
So make the count to 14 for the same.

317
00:18:03,520 --> 00:18:04,540
So that's why the count.

318
00:18:04,540 --> 00:18:04,810
Plus.

319
00:18:04,810 --> 00:18:05,140
Plus.

320
00:18:06,660 --> 00:18:11,070
Seven, seven and four, they are different, so to minus minus, so count becomes one.

321
00:18:12,220 --> 00:18:19,150
Again, for so foreign food, there seems to count placeless again for so foreign food, there seems

322
00:18:19,150 --> 00:18:20,260
to count placeless.

323
00:18:21,950 --> 00:18:24,860
Nine and four, they are different, so minus minus.

324
00:18:26,210 --> 00:18:30,300
Four and four, OK, four and four that seem so complex plus.

325
00:18:32,140 --> 00:18:34,570
Three and four, they are different.

326
00:18:34,600 --> 00:18:36,070
So count minus, minus.

327
00:18:37,020 --> 00:18:37,990
Now, finally, you are.

328
00:18:38,580 --> 00:18:43,050
So since Ford was the majority, elements of Ford will appear till the end of the year.

329
00:18:43,380 --> 00:18:44,730
So what is the answer?

330
00:18:45,300 --> 00:18:50,850
The answer is basically the candidate element, which is for you can see yourself how many times Ford

331
00:18:50,850 --> 00:18:51,510
is appearing.

332
00:18:51,510 --> 00:18:54,960
So one, two, three, four, five and six.

333
00:18:55,320 --> 00:18:57,270
So Ford is appearing six times.

334
00:18:57,270 --> 00:19:03,020
And the rest of the elements since the ad is basically after distance or the rest of the elements are

335
00:19:03,030 --> 00:19:08,640
appearing four times, if you will subtract six minus four, which is to OK, this two and two.

336
00:19:08,970 --> 00:19:10,080
OK, this is same.

337
00:19:11,920 --> 00:19:17,920
Since Ford was the majority element of the majority element from the rest of the element, so the majority

338
00:19:17,920 --> 00:19:19,510
element will exist till the end.

339
00:19:19,630 --> 00:19:20,710
This is the main logic.

340
00:19:20,960 --> 00:19:23,050
OK, so this is the majority element.

341
00:19:23,320 --> 00:19:28,000
And it's found after subtracting from the older elements as to, OK, you can see two.

342
00:19:30,030 --> 00:19:32,890
This is the approach, this is the Andalusians and Putin is very simple.

343
00:19:33,210 --> 00:19:36,340
So if you find out a different element, you have to subtract.

344
00:19:36,780 --> 00:19:37,950
Now, let us write the code.

345
00:19:44,170 --> 00:19:50,110
OK, so I have to retain the majority element, then I have the functional majority element and let's

346
00:19:50,110 --> 00:19:52,240
see the name of the vector is a.

347
00:19:54,200 --> 00:20:00,230
So very simple approach, what is the candidate, so candidate is the first element, Joselo.

348
00:20:02,710 --> 00:20:05,760
And it is appearing one time, OK?

349
00:20:06,990 --> 00:20:10,090
So this candidate is the candidate for the majority element.

350
00:20:13,560 --> 00:20:17,430
Now, let us find out the size, so the size is basically a large size.

351
00:20:20,190 --> 00:20:21,880
And now let us it over, Daddy.

352
00:20:22,030 --> 00:20:22,350
OK.

353
00:20:23,820 --> 00:20:25,590
So I have to start out reading from one.

354
00:20:26,690 --> 00:20:28,730
So I lived in Indianapolis bliss.

355
00:20:29,860 --> 00:20:34,540
Again, very simple condition, if the elements are slim, if the current element.

356
00:20:35,630 --> 00:20:40,060
It seems the candidate element then you have to do count placeless.

357
00:20:41,750 --> 00:20:44,690
In the elzbieta, but you have to do the elements are different.

358
00:20:44,720 --> 00:20:46,310
You have to do count minus minus.

359
00:20:47,220 --> 00:20:51,540
And after doing minus minus, if the count becomes a zero.

360
00:20:54,470 --> 00:20:55,970
If the count becomes suicidal.

361
00:20:57,520 --> 00:21:03,340
That means it's time to update your candidate element, so my candidate element is the current element

362
00:21:04,000 --> 00:21:06,930
and the current element is appearing one times.

363
00:21:07,510 --> 00:21:13,860
OK, finally, since we can assume that the candidate that the majority element always exist.

364
00:21:13,870 --> 00:21:17,010
So you are present in the variable candidate.

365
00:21:17,050 --> 00:21:18,490
OK, let's get another caller.

366
00:21:22,240 --> 00:21:23,770
OK, now let's meet gold.

367
00:21:29,740 --> 00:21:32,080
OK, so basically our code is working fine.

368
00:21:33,460 --> 00:21:35,520
So what is the time in the space complexity?

369
00:21:35,740 --> 00:21:37,910
So what is the time and the space complexities?

370
00:21:37,910 --> 00:21:40,030
So the time complexity is big.

371
00:21:40,030 --> 00:21:46,540
Often what we are doing, we are just iterating over the edge and the space complex, it is big of one.

372
00:21:46,580 --> 00:21:49,690
OK, so this is the time in this space complexity.

373
00:21:50,800 --> 00:21:56,410
Now, one more thing here, what we are doing here, we are assuming that the majority element always

374
00:21:56,410 --> 00:21:56,840
exist.

375
00:21:57,310 --> 00:22:00,050
Now, what if the majority element do not always exist?

376
00:22:00,110 --> 00:22:01,960
OK, so what if we do not?

377
00:22:01,960 --> 00:22:04,960
We cannot assume so if we cannot assume what we have to do.

378
00:22:06,190 --> 00:22:11,230
So if we cannot assume what we have to do, we have to find the count of the candidate element.

379
00:22:11,260 --> 00:22:11,680
OK.

380
00:22:12,760 --> 00:22:15,370
Now, what we can do, let us take a variable.

381
00:22:16,850 --> 00:22:20,630
Count two, OK, at the security will count do so.

382
00:22:22,780 --> 00:22:24,400
What we're doing, let us assume.

383
00:22:25,730 --> 00:22:28,730
So we cannot assume that the majority element is always there.

384
00:22:28,790 --> 00:22:32,860
OK, we cannot assume majority element is always there.

385
00:22:32,870 --> 00:22:34,370
So we will check first.

386
00:22:35,220 --> 00:22:37,130
OK, so we will check first.

387
00:22:38,110 --> 00:22:39,730
So let's sit right over the Eddie.

388
00:22:44,880 --> 00:22:46,680
We cannot assume so we check.

389
00:22:48,010 --> 00:22:51,010
So we check whether the candidate element is majority element or not.

390
00:22:51,040 --> 00:22:54,100
OK, so what you have to do, you just have to find it count.

391
00:22:55,140 --> 00:23:03,000
So if the current element is it goes to the candidate element, then will do we will do count two plus.

392
00:23:03,000 --> 00:23:03,390
Plus.

393
00:23:03,390 --> 00:23:04,920
Okay, count two plus plus.

394
00:23:06,460 --> 00:23:11,530
Finally, we know the count of the candidate element, so basically if the count.

395
00:23:13,660 --> 00:23:18,930
OK, count two is basically good end by two, so that means the majority element is dead.

396
00:23:19,240 --> 00:23:21,580
So if the majority element is dead, I can return.

397
00:23:21,610 --> 00:23:25,710
The candidate element in the Elzbieta majority element do not exist.

398
00:23:26,320 --> 00:23:30,850
OK, so if the majority element do not exist, then minus one because we have to return an integer.

399
00:23:31,180 --> 00:23:32,590
So I'm returning minus one.

400
00:23:35,890 --> 00:23:38,020
OK, now let's meet our called.

401
00:23:44,160 --> 00:23:49,140
OK, so our court is working fine now, why this court is working fine, so this court is working fine

402
00:23:49,140 --> 00:23:53,010
because in the end it is given that the majority element is almost there.

403
00:23:53,370 --> 00:23:57,500
OK, in the question it is given that the majority element is always present.

404
00:23:57,810 --> 00:24:01,620
So that's why you will always be able to find a candidate element.

405
00:24:02,670 --> 00:24:07,550
You will always be able to find a kindred element whose account is basically guerdon and vital.

406
00:24:07,800 --> 00:24:12,570
So in every condition, in every input, this written statement will be executed.

407
00:24:12,630 --> 00:24:15,450
OK, we will never reach the part.

408
00:24:15,870 --> 00:24:20,760
We will never reach the part, OK, because in the question it is given the majority element always

409
00:24:20,760 --> 00:24:21,210
exist.

410
00:24:22,570 --> 00:24:23,740
Now, let us summarize.

411
00:24:25,370 --> 00:24:30,110
So we discussed four approaches to solve this question, so first one was the brute force approach.

412
00:24:30,380 --> 00:24:34,250
So in the brute force approach, time was and square and the space was big.

413
00:24:34,250 --> 00:24:36,620
Often the second was Hashmat approach.

414
00:24:36,860 --> 00:24:39,950
So time was big often and the space was also big.

415
00:24:39,950 --> 00:24:42,510
Often the third was deciding approach.

416
00:24:42,590 --> 00:24:46,070
So the time was at Logan and the space was big.

417
00:24:46,070 --> 00:24:46,460
Often.

418
00:24:46,970 --> 00:24:52,910
Now the best approach is basically this more voting algorithm, Woody's voting algorithm.

419
00:24:55,010 --> 00:25:00,050
And basically that time is big off and the spaces because one.

420
00:25:02,080 --> 00:25:08,080
OK, then, to this very simple, it will subtract, if you will, separate the majority element, which

421
00:25:08,080 --> 00:25:14,830
is element, it also protect the majority element from the rest of the elements, since this is a majority

422
00:25:14,830 --> 00:25:15,100
element.

423
00:25:15,110 --> 00:25:18,310
So it will appear till the end of the year, it will exist.

424
00:25:18,640 --> 00:25:21,430
And of the area, we are doing exactly the same.

425
00:25:22,320 --> 00:25:23,950
OK, we are doing exactly the same here.

426
00:25:24,130 --> 00:25:28,080
I'm assuming this is my majority element and I am over the area.

427
00:25:28,180 --> 00:25:31,320
If this is a majority element, it will exist till the end of the area.

428
00:25:31,580 --> 00:25:34,070
OK, it will exist till the end of the year.

429
00:25:36,750 --> 00:25:42,350
So this is a very famous question, OK, so if you have any doubt in this question, you can ask me,

430
00:25:42,390 --> 00:25:43,830
OK, thank you.