1
00:00:01,260 --> 00:00:02,020
Hi, everyone.

2
00:00:02,040 --> 00:00:06,990
So in this video, we are going to write the code for this problem number of aliens, basically we need

3
00:00:06,990 --> 00:00:09,640
to write the code for the offense, not defense.

4
00:00:09,660 --> 00:00:12,930
We need to write the code for finding out the number of connected components.

5
00:00:14,620 --> 00:00:19,320
We need to write the code for finding out the number of connected components in the graph.

6
00:00:19,830 --> 00:00:24,090
And DFS algorithm can be used to find out the number of connected components.

7
00:00:24,600 --> 00:00:24,930
Right.

8
00:00:25,170 --> 00:00:30,660
So we just need to maintain one count that how many times I am running the algorithm.

9
00:00:30,660 --> 00:00:31,950
And that will be our answer.

10
00:00:33,360 --> 00:00:34,980
Right, for the algorithm.

11
00:00:35,100 --> 00:00:39,900
But we need we need a visitor, daddy and DFAC, the recursive algorithm.

12
00:00:39,900 --> 00:00:44,430
So it will recursively visit all the elements.

13
00:00:44,790 --> 00:00:45,180
Right.

14
00:00:45,840 --> 00:00:47,780
So let's start writing the code.

15
00:00:49,200 --> 00:00:50,690
So this is great.

16
00:00:50,850 --> 00:00:57,600
OK, so first let's find out how many rules are there that will be grid, not size.

17
00:01:03,820 --> 00:01:09,640
And let's find out how many columns out there that will be great of zero that size.

18
00:01:14,170 --> 00:01:22,120
Now, what we need, we need a visionary also, so this visit is that it will be a total matrix, right?

19
00:01:22,390 --> 00:01:28,960
So initially, what I'm going to do is I will create one visited Eddie, I will create one visited Eddie.

20
00:01:32,390 --> 00:01:39,200
I mean, to reiterate, and initially, no one is arrested, so I will initialize all the value to false

21
00:01:40,180 --> 00:01:46,270
light so all these values will be initialized or Tuvalu's because I have not listed any element yet.

22
00:01:46,820 --> 00:01:48,100
So let's do that.

23
00:01:49,010 --> 00:01:53,930
So we need to revisit it today and it will be of type.

24
00:01:53,990 --> 00:01:54,620
All right.

25
00:01:57,230 --> 00:01:58,700
So that predictable.

26
00:02:02,250 --> 00:02:03,300
And I visited.

27
00:02:06,020 --> 00:02:15,320
So how many rooms are there, M plus three Ambrosial with their great criticizes, eminent, so Amaru's

28
00:02:15,320 --> 00:02:20,000
will be there and we need to initialize.

29
00:02:23,830 --> 00:02:25,480
All the values would follow.

30
00:02:25,540 --> 00:02:30,830
So how many columns and columns and we need to initialize all the elements with files.

31
00:02:31,780 --> 00:02:33,370
So this is this index, right?

32
00:02:34,510 --> 00:02:36,280
This is this index for doing this.

33
00:02:39,500 --> 00:02:46,850
So this is this index, so what I'm doing, I am creating one vector, this vector is of size and so

34
00:02:46,850 --> 00:02:53,040
Ambros will be there, Ambros will be there and distractor, what does it contains?

35
00:02:53,060 --> 00:02:58,790
It contains a vector of bull and disprovable is of size n and initialized with false.

36
00:02:59,150 --> 00:03:01,220
So this vector is of size and.

37
00:03:03,710 --> 00:03:11,000
His office says any and all the values are initialized with files, all the values are initialized with

38
00:03:11,000 --> 00:03:11,460
files.

39
00:03:11,960 --> 00:03:15,650
So that is what we need to do right now.

40
00:03:15,650 --> 00:03:20,930
What we need to do, we need to iterate over this data with this great array.

41
00:03:21,170 --> 00:03:25,430
And if it is one and not visited, then start the offense.

42
00:03:26,330 --> 00:03:26,720
Right.

43
00:03:28,220 --> 00:03:36,730
So our answer will be our answer is how many times we are calling DFS algorithm.

44
00:03:37,040 --> 00:03:39,000
So countercurrent will be our answer.

45
00:03:39,020 --> 00:03:45,320
Initially, the count zero and our answer will be count how many times we will call the algorithm.

46
00:03:46,520 --> 00:03:49,700
Now, what we need to do, we need to hydrate over the Eddie.

47
00:03:50,390 --> 00:03:55,060
So let's hydrate equals zero iList and am I plus.

48
00:03:55,070 --> 00:03:55,520
Plus.

49
00:03:58,980 --> 00:04:09,300
Forint J equals zero, G, Leiston and G plus plus what you need to do if the current element.

50
00:04:11,330 --> 00:04:20,540
So if greed of AIG, if the current element is basically one, if the current element is one where they

51
00:04:20,540 --> 00:04:24,710
need to do, you will call the algorithm, right?

52
00:04:25,010 --> 00:04:26,970
You will call the algorithm what they have.

53
00:04:27,270 --> 00:04:29,480
Gardam will take it will take has input.

54
00:04:29,760 --> 00:04:37,670
It will take the index I and the current index, and it will take a visitor that remember the algorithm

55
00:04:37,670 --> 00:04:39,440
used to take visitor, that is input.

56
00:04:40,760 --> 00:04:45,280
And what else do we need to do since we are running the DFS algorithm.

57
00:04:45,620 --> 00:04:49,250
So we need to do account plus plus rate.

58
00:04:49,550 --> 00:04:51,680
We are doing we are running the official gardam.

59
00:04:51,680 --> 00:04:53,350
So we need to do count plus.

60
00:04:53,360 --> 00:04:56,060
Plus no one thing is missing here.

61
00:04:56,510 --> 00:04:57,630
What else do we need to do?

62
00:04:58,400 --> 00:05:00,230
So let me clear the screen first.

63
00:05:02,150 --> 00:05:03,920
Let's talk about this example.

64
00:05:04,160 --> 00:05:04,670
Right.

65
00:05:06,530 --> 00:05:14,050
So what we need to do, I am I reading all this greenery and I will start from this element, right.

66
00:05:14,690 --> 00:05:21,200
But if it is when you will start DFS, but you also need to check whether this element is visited or

67
00:05:21,200 --> 00:05:21,500
not.

68
00:05:22,190 --> 00:05:22,580
Right.

69
00:05:22,820 --> 00:05:27,590
So here we should write one more condition that the current element has not been visited.

70
00:05:27,890 --> 00:05:32,080
Then only you will start DFS from that element late.

71
00:05:32,210 --> 00:05:33,380
For example, this is one.

72
00:05:34,720 --> 00:05:39,980
So when you will start DFS from this element, what this element will do, it will visit these four

73
00:05:39,980 --> 00:05:42,800
elements so that your next element will be one.

74
00:05:42,980 --> 00:05:45,490
And if it is one, you will start DFS again.

75
00:05:45,500 --> 00:05:46,970
But that is wrong, right?

76
00:05:47,150 --> 00:05:51,590
So you should have one more, Jacare, that the current element has not been visited.

77
00:05:53,330 --> 00:05:53,770
Right.

78
00:05:55,990 --> 00:06:03,760
So we need to have one more check before calling the DFS from this element that the current element

79
00:06:03,760 --> 00:06:04,890
should not be visited.

80
00:06:05,590 --> 00:06:12,260
So if visited of IJI is false.

81
00:06:13,270 --> 00:06:19,910
So if the current element has not been visited, then only you will start DFS from the current element.

82
00:06:21,570 --> 00:06:22,000
Right.

83
00:06:23,430 --> 00:06:29,550
So now our goal is really the only thing that is missing is we need to write the code for the DFS function,

84
00:06:29,550 --> 00:06:31,650
which is going to be a recursive function.

85
00:06:34,110 --> 00:06:39,600
So where does this DFS function will return, it will not add anything, it will just visit all the

86
00:06:39,600 --> 00:06:43,840
elements and what it is taking it is taking graphics input.

87
00:06:44,010 --> 00:06:48,890
So let's take the graph vector vector character.

88
00:06:50,220 --> 00:06:53,490
And this is our graph grid, right?

89
00:06:53,830 --> 00:06:57,090
It is taking the index, Anji.

90
00:06:57,570 --> 00:07:02,190
And it is also taking I've visited at as input rate.

91
00:07:02,730 --> 00:07:05,670
So this visit today is to the Eddie.

92
00:07:08,850 --> 00:07:19,010
And visited, so one important thing is basically this visitor that should be passed Bio-Reference,

93
00:07:20,580 --> 00:07:24,390
this visitor that should be passed by the fence, because what we are going to do is we are going to

94
00:07:24,390 --> 00:07:25,910
change this reality.

95
00:07:26,190 --> 00:07:28,050
So that changes should be reflected here.

96
00:07:28,050 --> 00:07:34,560
Also made so you will not pass by value, you will pass by reference, because the whatever changes

97
00:07:34,560 --> 00:07:39,520
we are doing in this function that changes should reflect in main function also.

98
00:07:40,260 --> 00:07:43,820
So you need to pass Bio-Reference and that is very important.

99
00:07:43,830 --> 00:07:45,920
Otherwise your algorithm will not run.

100
00:07:46,320 --> 00:07:47,900
It will give you wrong output.

101
00:07:48,390 --> 00:07:50,550
So it has to be Bio-Reference.

102
00:07:52,590 --> 00:07:58,110
Now, this is going to be a recursive algorithm, so very simple, simple based guesses, right?

103
00:07:58,260 --> 00:08:09,540
If I is less than zero indexes invalid, you are just basically less than zero invalid index or the

104
00:08:09,540 --> 00:08:14,190
value of AI is basically greater than or close to your griddled size.

105
00:08:15,600 --> 00:08:18,450
Again, invalid index.

106
00:08:20,070 --> 00:08:26,910
Or Jay is basically bigger than our to grade of zero dark size again in the next.

107
00:08:28,800 --> 00:08:31,020
So these are all invalidly next.

108
00:08:31,380 --> 00:08:34,770
And when we will get invalided, index, what we will do, we will simply return.

109
00:08:34,860 --> 00:08:38,130
Do not do anything Sembler written because the index is invalid.

110
00:08:38,970 --> 00:08:39,350
Right?

111
00:08:39,360 --> 00:08:47,580
Simple because other simple baskets can be if the current element is basically zero, if the current

112
00:08:47,580 --> 00:08:49,520
element is water.

113
00:08:50,100 --> 00:08:53,430
So if the current element is water, what will will simply return.

114
00:08:54,150 --> 00:08:54,580
Right.

115
00:08:55,500 --> 00:09:01,230
Similarly, another base case can be if the current element is already visited.

116
00:09:01,260 --> 00:09:05,760
So if we started off IGY is already true.

117
00:09:05,880 --> 00:09:09,090
We have already visited this element in that case.

118
00:09:09,090 --> 00:09:12,590
Also where they are going to do is you done right.

119
00:09:12,870 --> 00:09:16,560
So simple, simple cases because this is going to be a recursive algorithm.

120
00:09:18,450 --> 00:09:21,510
So now let's actually write the code for the first.

121
00:09:23,720 --> 00:09:30,110
So I'm standing at the current parliament, right, I am standing at current elements, so I am standing

122
00:09:30,110 --> 00:09:30,420
here.

123
00:09:30,800 --> 00:09:34,670
So what I'm going to do is I will mogg this element as visited.

124
00:09:36,080 --> 00:09:44,060
So what to do since I am standing at the next AMG and this index is valid and this index is containing

125
00:09:44,060 --> 00:09:47,520
element one that this land and this index has not been visited before.

126
00:09:48,260 --> 00:09:53,690
So this element has not been visited before and now I am visiting this element.

127
00:09:53,690 --> 00:09:55,880
So I will mark this as proof.

128
00:09:56,930 --> 00:09:57,320
Right.

129
00:09:57,320 --> 00:09:58,580
I will mark this as true.

130
00:09:58,820 --> 00:10:03,200
And since we are changing the mystery value, that's why we need to take Bio-Reference, because the

131
00:10:03,210 --> 00:10:06,310
changes must be reflected here in this function also.

132
00:10:06,680 --> 00:10:09,560
And then what we need to do so from a given index.

133
00:10:10,280 --> 00:10:11,810
From a given index.

134
00:10:12,620 --> 00:10:13,070
Right.

135
00:10:13,070 --> 00:10:14,360
From a given index.

136
00:10:14,360 --> 00:10:19,720
What you can do, you can move in either directions, we can move in either directions.

137
00:10:19,970 --> 00:10:26,030
So what we will do, we will call DFS, we will call the function DFS in all the other directions,

138
00:10:27,590 --> 00:10:30,460
call DFS, function in all eight directions.

139
00:10:30,980 --> 00:10:31,390
Right.

140
00:10:31,790 --> 00:10:32,900
So let's do that.

141
00:10:34,460 --> 00:10:38,300
We need to call the DFS function on all eight Badakshan.

142
00:10:38,300 --> 00:10:39,950
So the efface.

143
00:10:41,180 --> 00:10:42,560
This is a recursive algorithm.

144
00:10:42,560 --> 00:10:46,010
We already know this will take graph as input.

145
00:10:46,550 --> 00:10:56,420
This will take the first let's say I minus one and G minus one and it will take with Gianetti Farshad.

146
00:10:58,340 --> 00:10:58,750
Right.

147
00:10:58,760 --> 00:11:06,170
So let's copy this and there are eight directions possible, so let's paste them.

148
00:11:13,100 --> 00:11:22,010
So this is one, two, three, four, five, six, seven and eight, yes, so total eight directions.

149
00:11:27,270 --> 00:11:33,420
And now let us change the values, so I am minus and minus, and the second can be a minus, one energy

150
00:11:35,250 --> 00:11:44,340
tower can be a minus one energy plus one for the addiction can be, I think, minus one.

151
00:11:46,770 --> 00:11:52,320
Which direction can be I and J plus one?

152
00:11:54,500 --> 00:12:03,660
Sixth medication can be a plus one and G minus one, correct, next direction can be lifted.

153
00:12:03,680 --> 00:12:13,550
This is G and this is a plus one and let's say the last election is a plus one and G plus one.

154
00:12:14,090 --> 00:12:16,790
So D let me give some spaces between them.

155
00:12:21,840 --> 00:12:24,790
So these are total eight possible actions, right?

156
00:12:26,070 --> 00:12:31,320
So from a given element, I will call DFS on all eight possible directions.

157
00:12:34,870 --> 00:12:36,610
And that will be the entity called.

158
00:12:44,480 --> 00:12:47,370
Right, so this will be the entire record.

159
00:12:48,140 --> 00:12:49,870
Let me give space's here.

160
00:12:53,760 --> 00:12:58,800
Yep, and let's also make sure that in line.

161
00:13:02,430 --> 00:13:06,900
So, yeah, this will be total eight possible directions, right?

162
00:13:07,170 --> 00:13:09,090
So this is the complete code.

163
00:13:10,770 --> 00:13:12,480
Let's our current annual summit.

164
00:13:17,120 --> 00:13:19,440
So we are getting some compilation error.

165
00:13:19,610 --> 00:13:20,190
Did you mean.

166
00:13:20,660 --> 00:13:26,570
OK, so spelling mistake, this will be size.

167
00:13:32,680 --> 00:13:34,930
Yep, our code is working right now.

168
00:13:43,110 --> 00:13:45,150
OK, so we are getting a wrong answer.

169
00:13:45,780 --> 00:13:48,620
Let's see what we did wrong.

170
00:13:52,230 --> 00:13:55,320
OK, so let's see, what is this?

171
00:13:56,190 --> 00:14:05,190
So this is we have one one zero zero zero, then again, one one zero zero zero, then zero zero one

172
00:14:05,190 --> 00:14:09,130
zero zero and then zero zero zero one one.

173
00:14:09,210 --> 00:14:11,520
So this is the graph.

174
00:14:11,520 --> 00:14:14,630
And yeah, the expected output is correct.

175
00:14:14,640 --> 00:14:17,220
This is one connected component.

176
00:14:17,280 --> 00:14:19,050
This is another connected component.

177
00:14:19,050 --> 00:14:20,920
And this is another connected component.

178
00:14:21,300 --> 00:14:25,800
So the expected output is correct and our goal is giving the output as one.

179
00:14:26,880 --> 00:14:31,830
So our goal is giving wrong output and why it is.

180
00:14:31,830 --> 00:14:36,270
So let's try to analyze what we did wrong here.

181
00:14:38,310 --> 00:14:39,030
Hi, everyone.

182
00:14:39,060 --> 00:14:42,340
So I have figured out actually why our goal was failing.

183
00:14:42,630 --> 00:14:46,280
So let me try to submit this quote again and let's see.

184
00:14:47,400 --> 00:14:51,500
So see, this is the input which is given to us.

185
00:14:52,140 --> 00:14:57,780
The input is one one zero zero one zero, then one one zero zero zero.

186
00:14:58,050 --> 00:15:03,340
Then I have zero zero one zero zero, then zero zero zero one and one.

187
00:15:03,750 --> 00:15:07,060
So what my goal is returning.

188
00:15:07,320 --> 00:15:10,890
So what I am doing, I am moving in two directions.

189
00:15:11,340 --> 00:15:11,790
Right.

190
00:15:12,630 --> 00:15:14,290
If you will move in each direction.

191
00:15:14,550 --> 00:15:16,680
So that means you can move diagonally also.

192
00:15:17,880 --> 00:15:18,290
Right.

193
00:15:18,570 --> 00:15:21,490
So I can move diagonally and I can reach here.

194
00:15:21,510 --> 00:15:24,010
Similarly, I can move diagonally and I can reach here.

195
00:15:24,270 --> 00:15:27,560
So what my goal is doing, I am moving in eight directions.

196
00:15:27,780 --> 00:15:31,620
So my goal is combining all these right.

197
00:15:31,860 --> 00:15:33,720
My goal is combining all this.

198
00:15:33,720 --> 00:15:38,120
And that's why my goal is retaining that output is when there is only one connected component.

199
00:15:38,610 --> 00:15:40,470
So that's why the goal is returning one.

200
00:15:40,650 --> 00:15:46,680
But if you will see the actual quotient description in that question, it has mentioned that you can

201
00:15:46,680 --> 00:15:48,900
either move horizontally automatically.

202
00:15:49,470 --> 00:15:49,720
Right.

203
00:15:50,010 --> 00:15:53,160
It is mentioned that you can move in four directions.

204
00:15:53,580 --> 00:15:56,660
So it was like pretty silly mistake from my side.

205
00:15:56,670 --> 00:15:58,830
Actually, I saw only one question before solving this.

206
00:15:59,130 --> 00:16:02,430
So in that question, I was able to move in a direction.

207
00:16:02,700 --> 00:16:04,410
So that's why I missed out here.

208
00:16:04,680 --> 00:16:09,060
And like, I paused the video for some time and I tried debugging a lot.

209
00:16:09,060 --> 00:16:13,680
And then when I was not able to find the solution, then I read the description again.

210
00:16:13,690 --> 00:16:17,580
And then I was able to figure out that you can move only in four directions.

211
00:16:18,600 --> 00:16:20,940
So if you will move in for direction, what will happen?

212
00:16:21,120 --> 00:16:23,430
You will not be able to reach this right.

213
00:16:23,670 --> 00:16:26,220
You will not be able to reach at this one.

214
00:16:26,230 --> 00:16:28,620
So you will finish here similarly.

215
00:16:28,620 --> 00:16:33,540
Then you will finish it because you will not be able to move diagonally and this will be another connected

216
00:16:33,540 --> 00:16:34,120
component.

217
00:16:34,320 --> 00:16:39,230
So instead of moving in a direction, we need to modify our code to move only in four direction.

218
00:16:39,510 --> 00:16:42,030
So that was the error that we did.

219
00:16:42,310 --> 00:16:44,490
It was a pretty silly mistake from my side.

220
00:16:44,850 --> 00:16:45,270
Right.

221
00:16:45,420 --> 00:16:46,910
So here you can see it.

222
00:16:46,950 --> 00:16:53,100
You can see for yourself that the question is asking us to move only horizontally or vertically Direxion

223
00:16:53,100 --> 00:16:54,480
and not diagonal direction.

224
00:16:54,870 --> 00:16:56,330
So I am so sorry, guys.

225
00:16:57,030 --> 00:17:00,950
That's why you should read the question very carefully before jumping to the code.

226
00:17:01,110 --> 00:17:05,849
So since we can move on in four direction, let's remove this line.

227
00:17:08,880 --> 00:17:12,390
Which else I think we need to remove this line also.

228
00:17:15,829 --> 00:17:17,869
We need to remove this line.

229
00:17:21,010 --> 00:17:28,550
And we need to remove this line, so I have removed all the four directional directions right now.

230
00:17:28,569 --> 00:17:29,240
This is correct.

231
00:17:30,370 --> 00:17:31,570
Now I will call Vilborg.

232
00:17:36,410 --> 00:17:39,110
So now we are getting a time limit exceeded.

233
00:17:40,160 --> 00:17:41,090
Yeah, very good.

234
00:17:41,570 --> 00:17:44,270
Let's see how many test case our court is passing.

235
00:17:51,960 --> 00:17:56,610
So our goal, the past 47 days, cases out of 48,

236
00:17:59,610 --> 00:18:02,070
so basically we are getting time limited exited.

237
00:18:02,380 --> 00:18:08,070
So let's try to find out what is the time complexity of our code and then we will see how we can reduce

238
00:18:08,070 --> 00:18:09,160
the time complexity.

239
00:18:09,240 --> 00:18:13,630
So let's discuss the time complexity so that we can reduce our time complexity.

240
00:18:14,040 --> 00:18:21,090
So what is the time complexity of how according to our time complexities and I mean because we are iterating

241
00:18:21,090 --> 00:18:27,210
right Ambrosiano in columns so that when the time complexities Emman and we are going to each and every

242
00:18:27,210 --> 00:18:28,410
element only once.

243
00:18:28,530 --> 00:18:28,890
Right.

244
00:18:29,130 --> 00:18:35,140
We are visiting the element only once since we are visiting each and every element only once.

245
00:18:35,160 --> 00:18:41,380
So that's why the time complexities Eman and regarding the space complexity.

246
00:18:41,400 --> 00:18:43,340
So we have created this visibility.

247
00:18:43,570 --> 00:18:45,030
So space complexities.

248
00:18:45,030 --> 00:18:46,080
Emman, right.

249
00:18:46,350 --> 00:18:48,270
So this is the time and the space complexity.

250
00:18:48,510 --> 00:18:52,860
And even after this time, complexity, I am getting time limited exited.

251
00:18:53,250 --> 00:18:56,990
So that means there is not a problem with our logic.

252
00:18:57,000 --> 00:19:01,620
There is some different problem and what this different problem is.

253
00:19:01,920 --> 00:19:05,760
So here what they are doing, you are pressing the greenery, right.

254
00:19:05,760 --> 00:19:07,290
And you are passing by value.

255
00:19:07,680 --> 00:19:10,380
So by value, what will happen for this function?

256
00:19:10,740 --> 00:19:15,090
This grid array will be created and all the values will be copied.

257
00:19:15,390 --> 00:19:15,850
Right.

258
00:19:15,990 --> 00:19:17,130
So that will take time.

259
00:19:17,760 --> 00:19:20,760
So what I am trying to say here is this grid array.

260
00:19:20,760 --> 00:19:25,590
We are passing this great array by value and when we pass by value, so what will happen?

261
00:19:25,800 --> 00:19:30,750
This function will create one local variable grid and it will copy all the data.

262
00:19:31,590 --> 00:19:33,350
It will copy all the data.

263
00:19:34,620 --> 00:19:36,450
So that is time consuming, right?

264
00:19:36,880 --> 00:19:38,160
That will take time.

265
00:19:38,400 --> 00:19:43,650
So what we will do, instead of taking by value, if we will take it by reference, then we will not

266
00:19:43,650 --> 00:19:48,620
have a time limit extended, because if you take by definition, then we will not copy the data.

267
00:19:48,870 --> 00:19:51,350
We will just refer to the data that is present here.

268
00:19:54,770 --> 00:20:00,920
So what we are going to do is instead of taking great away by volume, we will take great Bio-Reference

269
00:20:01,640 --> 00:20:05,480
so that we will avoid the time that we are using in copying the data.

270
00:20:06,140 --> 00:20:09,710
Now, if we will submit now, Gore will work.

271
00:20:13,020 --> 00:20:15,810
Right, so now our court is working.

272
00:20:16,180 --> 00:20:23,250
OK, so this was the catch, a great idea by the fence to reduce your time complexity, to save the

273
00:20:23,250 --> 00:20:25,350
time that you are using in copying the data.

274
00:20:27,000 --> 00:20:29,060
So this is it from this device.

275
00:20:29,070 --> 00:20:32,910
If you have any doubt to ask me, I will see you in the next one.

276
00:20:33,090 --> 00:20:33,630
Thank you.

