1
00:00:00,600 --> 00:00:01,620
Welcome back.

2
00:00:01,620 --> 00:00:06,240
Now let's go ahead and think about the brute force method to solve this question.

3
00:00:06,240 --> 00:00:12,120
We have already seen that if we can detect whether there is a cycle in the graph, then we can say that

4
00:00:12,120 --> 00:00:13,920
we cannot complete all the courses.

5
00:00:13,920 --> 00:00:19,230
So we are trying to think about how can we check if there is a cycle in the graph which is given to

6
00:00:19,230 --> 00:00:19,530
us?

7
00:00:19,530 --> 00:00:21,030
Now let's take an example.

8
00:00:21,030 --> 00:00:23,130
Let's say n is equal to eight.

9
00:00:23,130 --> 00:00:26,100
So the nodes are going to be from 0 to 7.

10
00:00:26,100 --> 00:00:28,140
And let's say the graph looks like this.

11
00:00:28,710 --> 00:00:31,020
All right so we can represent this.

12
00:00:31,020 --> 00:00:34,830
The the prerequisite array which will be given to us would be looking like this.

13
00:00:34,830 --> 00:00:35,340
Right.

14
00:00:36,590 --> 00:00:38,570
So you can see there is a link.

15
00:00:38,600 --> 00:00:39,530
Two comma one.

16
00:00:39,530 --> 00:00:42,830
So this means that before doing two you have to do one.

17
00:00:42,830 --> 00:00:44,750
So this is how we can visualize this.

18
00:00:44,750 --> 00:00:48,890
And then we have three comma two which means before doing three you have to do two right.

19
00:00:48,890 --> 00:00:50,090
Which is this link over here.

20
00:00:50,090 --> 00:00:52,370
And before doing four you have to do three.

21
00:00:52,370 --> 00:00:54,500
And before doing four you have to do two.

22
00:00:54,500 --> 00:00:56,900
And before doing five you have to do zero.

23
00:00:56,900 --> 00:01:00,680
And before doing six you have to do five, which is this link over here.

24
00:01:00,680 --> 00:01:03,080
And then before doing zero you have to do six.

25
00:01:03,080 --> 00:01:07,520
And then nothing is mentioned about seven, which means that it's just like this over here.

26
00:01:07,520 --> 00:01:11,090
Not there's no edge with this from seven to any other node.

27
00:01:11,090 --> 00:01:11,480
All right.

28
00:01:11,480 --> 00:01:13,250
So this is how we have visualized the graph.

29
00:01:13,250 --> 00:01:19,190
Now let's try to think about the brute force method of solving and checking whether there is a cycle

30
00:01:19,190 --> 00:01:20,540
in this graph or not.

31
00:01:20,540 --> 00:01:24,260
Now remember the graph can be unconnected.

32
00:01:24,260 --> 00:01:24,680
All right.

33
00:01:24,680 --> 00:01:27,590
So for example over here you can see this part over here.

34
00:01:28,760 --> 00:01:31,340
Is not connected with these two other parts.

35
00:01:31,340 --> 00:01:33,200
So the graph can be unconnected.

36
00:01:33,200 --> 00:01:37,280
So this is something that you have to keep in mind when you come up with the brute force solution.

37
00:01:37,280 --> 00:01:37,850
All right.

38
00:01:37,850 --> 00:01:38,990
Now let's proceed.

39
00:01:38,990 --> 00:01:42,620
Now we to start with we have the value of n.

40
00:01:42,620 --> 00:01:45,860
And we have this array over here which is the prerequisites array.

41
00:01:45,890 --> 00:01:51,140
Now using the prerequisites array and n let's form the adjacency list.

42
00:01:51,140 --> 00:01:53,060
So this is going to be our first step.

43
00:01:53,060 --> 00:01:56,600
We will form the adjacency list which is going to be an array of arrays.

44
00:01:56,600 --> 00:02:00,680
So over here we will have the indices from 0 to 7.

45
00:02:00,680 --> 00:02:00,860
Right.

46
00:02:00,860 --> 00:02:01,940
So we have zero.

47
00:02:02,980 --> 00:02:04,330
And we'll have an array over there.

48
00:02:04,330 --> 00:02:05,230
And then we have one.

49
00:02:05,230 --> 00:02:06,280
We have an array over there.

50
00:02:06,280 --> 00:02:08,500
And this goes on till index seven.

51
00:02:08,500 --> 00:02:10,420
So this is our adjacency list.

52
00:02:10,420 --> 00:02:14,530
So we are going to form our adjacency list using n and this prerequisite array.

53
00:02:14,530 --> 00:02:17,890
So for example at index zero there is a link to five.

54
00:02:17,890 --> 00:02:19,300
So we will fill five over here.

55
00:02:19,300 --> 00:02:20,500
And there is no other link.

56
00:02:20,500 --> 00:02:22,600
Now at index one there is a link to two.

57
00:02:22,630 --> 00:02:23,950
So we will fill two over here.

58
00:02:23,950 --> 00:02:26,230
And at index seven there is no other link.

59
00:02:26,230 --> 00:02:27,730
So this would be an empty array.

60
00:02:27,730 --> 00:02:29,470
So this is our adjacency list.

61
00:02:29,470 --> 00:02:31,660
So this would be the first thing that we will form.

62
00:02:31,660 --> 00:02:32,170
Right.

63
00:02:32,170 --> 00:02:37,060
And then because we we will need to know how to traverse the given graph.

64
00:02:37,060 --> 00:02:37,330
Right.

65
00:02:37,330 --> 00:02:40,480
So basically we will have to find a way to traverse the given graph.

66
00:02:40,480 --> 00:02:45,070
And keeping in mind that the graph can be unconnected and check for cycles.

67
00:02:45,070 --> 00:02:46,480
So this is what we are trying to do.

68
00:02:46,720 --> 00:02:48,970
The first step is to form our adjacency list.

69
00:02:48,970 --> 00:02:52,780
And then we will just take each vertex one by one.

70
00:02:52,780 --> 00:02:55,330
And then we will do BFS or DFS.

71
00:02:55,330 --> 00:03:00,520
That is we will traverse the graph from that particular vertex starting from that vertex.

72
00:03:00,520 --> 00:03:03,760
And we can use breadth first search or depth first search.

73
00:03:03,760 --> 00:03:04,570
It does not matter.

74
00:03:04,570 --> 00:03:04,870
Right.

75
00:03:04,870 --> 00:03:06,220
So we will do this.

76
00:03:06,220 --> 00:03:12,850
And as we traverse the graph we will just check whether the vertex from which we started to traverse

77
00:03:12,850 --> 00:03:15,700
the graph is appearing again in the traversal.

78
00:03:15,700 --> 00:03:22,000
If it is appearing again, then we can be sure that we are seeing we have a cycle, and then if we have

79
00:03:22,000 --> 00:03:25,600
a cycle, it just means that we cannot complete all the courses.

80
00:03:25,600 --> 00:03:27,490
So this is the brute force method right?

81
00:03:27,490 --> 00:03:30,430
So again why are we taking every vertex one by one?

82
00:03:30,430 --> 00:03:33,520
It's because of the fact that the graph can be unconnected.

83
00:03:33,520 --> 00:03:40,750
For example, if we start over here and if we do BFS or DFS, we will visit all these vertices and we

84
00:03:40,750 --> 00:03:42,490
will see that there is no cycle.

85
00:03:42,490 --> 00:03:42,880
Right?

86
00:03:42,880 --> 00:03:44,560
There is no cycle at this point.

87
00:03:44,560 --> 00:03:49,270
But then we cannot be sure that there is no cycle in all the graph, because you can see we have not

88
00:03:49,270 --> 00:03:53,950
touched any of these vertices because this component and this component is unconnected.

89
00:03:53,950 --> 00:03:54,220
Right.

90
00:03:54,220 --> 00:03:57,310
So that's why we have to take each vertex one by one.

91
00:03:57,310 --> 00:03:58,840
And then we have to traverse it.

92
00:03:58,840 --> 00:04:00,730
So for example we will start over here.

93
00:04:00,730 --> 00:04:03,040
We will traverse we'll see that there is no cycle.

94
00:04:03,040 --> 00:04:07,930
But for example when we come over here and when we traverse, we will see that we will come to five

95
00:04:07,930 --> 00:04:10,750
and then we'll come to six, and then we'll again come to one.

96
00:04:10,750 --> 00:04:16,360
So we can see that the vertex from which we started is appearing again in the traversal, which means

97
00:04:16,360 --> 00:04:20,560
that there is a cycle, and hence we cannot complete all the courses.

98
00:04:20,560 --> 00:04:22,870
So this is how we are going to solve this question.

99
00:04:22,870 --> 00:04:27,220
Now let's take a quick look at the space and time complexity of this solution.

100
00:04:27,220 --> 00:04:30,550
Now let me just have a pointer mentioned over here.

101
00:04:30,550 --> 00:04:36,430
The complexity analysis is going to be much easier to understand when we look at the code of this solution.

102
00:04:36,430 --> 00:04:38,530
But let's try to discuss it over here.

103
00:04:38,530 --> 00:04:40,990
First let's take a look at the time complexity.

104
00:04:40,990 --> 00:04:45,460
So what are the things that take up time forming the adjacency list will take up time, right?

105
00:04:45,460 --> 00:04:49,540
Because we first have to form an empty array of n elements.

106
00:04:49,540 --> 00:04:52,450
So that's why we have n o of n over here.

107
00:04:52,450 --> 00:04:57,880
And then we are going to iterate over the prerequisite array to form to fill the adjacency list, right.

108
00:04:57,880 --> 00:05:01,180
To identify the edges and fill it into our adjacency list.

109
00:05:01,180 --> 00:05:07,390
So that's why we are going to have O of n plus p operations to form the adjacency list, where n is

110
00:05:07,390 --> 00:05:12,280
the number of vertices and p is the number of elements in our prerequisite array.

111
00:05:12,280 --> 00:05:13,300
Again, why is that?

112
00:05:13,300 --> 00:05:18,370
So over here we have n because initially we'll have to form an array of empty arrays.

113
00:05:18,370 --> 00:05:20,500
And the elements is going to be n right.

114
00:05:20,500 --> 00:05:24,400
They are going to be n empty arrays in the adjacency list array.

115
00:05:24,460 --> 00:05:25,000
So that.

116
00:05:25,000 --> 00:05:27,790
So to form that we will have to do n operations over here.

117
00:05:27,790 --> 00:05:33,790
And then we will iterate through the prerequisite array and identify the edges and fill it to our adjacency

118
00:05:33,790 --> 00:05:34,060
list.

119
00:05:34,060 --> 00:05:37,510
So over here we are doing O of n plus p operations.

120
00:05:38,050 --> 00:05:40,960
And then we are going to take each vertex one by one.

121
00:05:40,960 --> 00:05:42,520
So there are n vertices.

122
00:05:42,520 --> 00:05:45,190
So this is going to be an o of n operation.

123
00:05:45,190 --> 00:05:49,090
And then we are going to check if the vertex is appearing in the traversal.

124
00:05:49,090 --> 00:05:51,520
So basically we are going to take each vertex.

125
00:05:51,520 --> 00:05:54,100
And then we are going to do BFS or DFS.

126
00:05:54,100 --> 00:06:00,940
Now we know that the time complexity of BFS or DFS is O of n plus e, where n is the number of vertices.

127
00:06:00,940 --> 00:06:01,180
Right?

128
00:06:01,180 --> 00:06:03,190
Or we can say o of v plus e.

129
00:06:03,220 --> 00:06:09,850
So we are going to do an O of v plus e operation in the worst case on each of these n vertices.

130
00:06:09,850 --> 00:06:10,480
Why is that?

131
00:06:10,480 --> 00:06:13,750
So the worst case is if all of the vertices are connected, right?

132
00:06:13,750 --> 00:06:20,560
If all of them are connected, then for each of these vertices we will do o of n plus e number of operations.

133
00:06:20,560 --> 00:06:23,140
So that's why taking this together right.

134
00:06:23,140 --> 00:06:25,900
So for each of them we are doing N plus E operations.

135
00:06:25,900 --> 00:06:30,550
So the total number of operations over here is going to be n into n plus e.

136
00:06:30,550 --> 00:06:33,010
So let's add this and this together.

137
00:06:33,010 --> 00:06:38,350
And we get that the time complexity is n plus p plus n into n plus e.

138
00:06:38,350 --> 00:06:40,420
So this n over here is this n right.

139
00:06:40,420 --> 00:06:46,360
So this is this n and n plus e is what we have over here which is what we have over here.

140
00:06:46,360 --> 00:06:51,250
And again that's why we are multiplying them because for each of these we are doing n plus e operations

141
00:06:51,250 --> 00:06:51,550
again.

142
00:06:51,550 --> 00:06:56,470
So the time complexity is O of n plus p plus n into n plus e.

143
00:06:56,500 --> 00:06:58,180
Now let's try to simplify this.

144
00:06:58,180 --> 00:06:58,480
All right.

145
00:06:58,480 --> 00:06:59,710
So let's try to simplify this.

146
00:06:59,740 --> 00:07:02,410
We get n plus p plus.

147
00:07:02,560 --> 00:07:04,420
N square plus NE.

148
00:07:04,990 --> 00:07:07,180
Now n square is going to be greater than n.

149
00:07:07,180 --> 00:07:08,830
So we can just avoid this.

150
00:07:08,830 --> 00:07:15,610
And we can say that the time complexity is of the order of p plus n square plus n into e.

151
00:07:15,610 --> 00:07:17,950
So this is the time complexity of this solution.

152
00:07:17,950 --> 00:07:20,620
Now what about the space complexity of this solution.

153
00:07:20,620 --> 00:07:23,620
Now what are the things that take up space that can scale?

154
00:07:23,620 --> 00:07:28,630
When our input scales we are forming an adjacency list and then we are using a queue.

155
00:07:28,630 --> 00:07:30,730
If we go ahead with the BFS solution.

156
00:07:30,730 --> 00:07:33,820
Now in this part let's practice the breadth first search.

157
00:07:33,820 --> 00:07:34,060
Right.

158
00:07:34,060 --> 00:07:36,910
Because we have done questions for DFS previously.

159
00:07:36,910 --> 00:07:38,980
So let's implement this with BFS.

160
00:07:38,980 --> 00:07:41,020
So we can do it either BFS or DFS.

161
00:07:41,020 --> 00:07:45,460
Now if you do it DFS then the stack would take up space if you do it iteratively.

162
00:07:45,460 --> 00:07:49,240
And if you do DFS recursively, then the call stack will take up space.

163
00:07:49,240 --> 00:07:52,360
So accordingly you have to consider the space complexity.

164
00:07:52,360 --> 00:07:54,910
Now in this case we move ahead with BFS.

165
00:07:54,910 --> 00:07:56,890
So the queue is going to take up space.

166
00:07:56,890 --> 00:07:59,080
And then we have our visited object right.

167
00:07:59,080 --> 00:08:04,870
So whenever we do BFS we will need a visited object so that we don't go ahead into an infinite loop.

168
00:08:04,870 --> 00:08:06,880
So these are the things that take up space.

169
00:08:06,880 --> 00:08:07,330
All right.

170
00:08:07,330 --> 00:08:11,290
Now the adjacency list is going to be an array of arrays.

171
00:08:11,290 --> 00:08:11,710
Right.

172
00:08:11,710 --> 00:08:17,560
And the number of arrays inside the adjacency list will be equal to the number of vertices which is

173
00:08:17,560 --> 00:08:18,370
equal to n.

174
00:08:18,370 --> 00:08:21,040
And then inside this we are going to fill the edges right.

175
00:08:21,040 --> 00:08:27,220
So that's why the space taken up by the adjacency list is going to be of the order of n plus e, where

176
00:08:27,220 --> 00:08:29,740
n is the number of vertices and e is the number of edges.

177
00:08:29,740 --> 00:08:31,300
So this is pretty straightforward.

178
00:08:31,300 --> 00:08:34,810
And the queue is going to take up space of the order of n.

179
00:08:34,810 --> 00:08:37,360
We know that for breadth first search, the queue.

180
00:08:37,360 --> 00:08:43,030
In the worst case, possibility can take up space of the order of n, and the visited object is also

181
00:08:43,030 --> 00:08:48,910
going to take up space of the order of N, because if even if we visit all the all the vertices right

182
00:08:48,910 --> 00:08:50,020
in the same traversal.

183
00:08:50,020 --> 00:08:55,960
So if all of them were connected and we visit all of them in one BFS traversal, then also the visited

184
00:08:55,960 --> 00:08:58,030
object is going to take up O of n space.

185
00:08:58,030 --> 00:09:01,000
So among all these three the greatest is n plus e.

186
00:09:01,000 --> 00:09:02,620
So this is going to dominate right.

187
00:09:02,620 --> 00:09:07,300
So the space complexity of this solution is going to be of the order of n plus e.

188
00:09:07,330 --> 00:09:13,150
So we have seen that the time complexity is of the order of p plus n square plus n e.

189
00:09:13,150 --> 00:09:16,390
And the space complexity is of the order of n plus E.

190
00:09:16,390 --> 00:09:16,750
Right.

191
00:09:16,750 --> 00:09:17,770
So we have seen this.

192
00:09:17,770 --> 00:09:23,590
Now one more interesting thing to observe is that in the worst case in the graph, the number of edges

193
00:09:23,590 --> 00:09:27,670
can be of the order of n square, where n is the number of vertices.

194
00:09:27,670 --> 00:09:29,470
So let's try to understand this.

195
00:09:29,470 --> 00:09:31,450
Let's say the graph looks something like this.

196
00:09:31,450 --> 00:09:34,120
So this node is connected to every node.

197
00:09:34,120 --> 00:09:38,350
Then this core this node over here is connected to every node except this one.

198
00:09:38,350 --> 00:09:42,250
And this one is connected to every node except these two etc..

199
00:09:42,250 --> 00:09:43,300
So it's going on like that.

200
00:09:43,300 --> 00:09:49,540
So we can say that if there are n nodes then this node over here has n minus one connections and this

201
00:09:49,540 --> 00:09:53,920
one has n minus two connections, this one has n minus three connections etc..

202
00:09:53,920 --> 00:09:54,220
All right.

203
00:09:54,220 --> 00:09:55,840
So again this is a directed graph.

204
00:09:55,840 --> 00:09:56,980
So it goes in this way.

205
00:09:56,980 --> 00:09:58,990
So these are the n minus one connections.

206
00:09:58,990 --> 00:10:01,480
Then we have n minus two connections over here.

207
00:10:01,480 --> 00:10:04,750
And then over here you can see we have n minus three connections.

208
00:10:04,750 --> 00:10:05,770
And it goes on like that.

209
00:10:05,770 --> 00:10:10,720
Now if we add this up n minus one plus n minus two etc. up to one right.

210
00:10:10,720 --> 00:10:12,280
This is an arithmetic progression.

211
00:10:12,280 --> 00:10:19,240
And we have seen that this is equal to n minus one into n minus one plus one, which is n divided by

212
00:10:19,240 --> 00:10:19,450
two.

213
00:10:19,450 --> 00:10:19,810
Right.

214
00:10:19,810 --> 00:10:24,430
And this is um this on simplifying we have a term of n square.

215
00:10:24,430 --> 00:10:24,610
Right.

216
00:10:24,610 --> 00:10:25,570
Let's just simplify this.

217
00:10:25,600 --> 00:10:29,200
We get n square minus n and we have by two by two.

218
00:10:29,200 --> 00:10:34,900
So if we take the Big-O analysis or the asymptotic analysis of this, this is going to converge to O

219
00:10:34,900 --> 00:10:35,680
of n square.

220
00:10:35,680 --> 00:10:35,980
Right.

221
00:10:35,980 --> 00:10:40,990
So that's why we can say that in the worst case the edges can be of the order of n square.

222
00:10:41,020 --> 00:10:48,340
Now if we implement this over here, if we put this into our time and space complexity, we can write

223
00:10:48,340 --> 00:10:49,480
n square over here.

224
00:10:50,260 --> 00:10:51,370
And over here as well.

225
00:10:51,400 --> 00:10:51,850
Right.

226
00:10:51,850 --> 00:10:58,090
So in this case we can say that the time complexity is of the order of p plus n cubed.

227
00:10:58,830 --> 00:11:00,840
Because we have n over here and n square.

228
00:11:00,840 --> 00:11:02,370
So this becomes n cube.

229
00:11:02,370 --> 00:11:04,050
So n cube is greater than n square.

230
00:11:04,050 --> 00:11:05,310
So we can neglect this.

231
00:11:05,310 --> 00:11:07,590
And we get p plus n cube over here.

232
00:11:07,590 --> 00:11:12,270
And then the space complexity in this case becomes of the order of n square.

233
00:11:12,300 --> 00:11:12,750
All right.

234
00:11:12,750 --> 00:11:15,300
So you can explain both of these in the interview.

235
00:11:15,300 --> 00:11:17,850
Again the if if the interviewer wants.

236
00:11:17,850 --> 00:11:19,620
So again this is a good point to know.

237
00:11:19,620 --> 00:11:24,480
So we have seen that the time complexity is of the order of p plus n square plus n e.

238
00:11:24,480 --> 00:11:30,270
And if we take up the worst case possibility, we can say that that's of the order of p plus n cube.

239
00:11:30,270 --> 00:11:33,330
And the space complexity is of the order of n plus e.

240
00:11:33,330 --> 00:11:38,970
And if you take E as of to be of the order of n square, then we say that the space complexity is of

241
00:11:38,970 --> 00:11:40,230
the order of n square.