1
00:00:00,630 --> 00:00:01,680
Welcome back.

2
00:00:01,680 --> 00:00:06,210
Let's now go ahead and code the solution which we discussed in the previous video.

3
00:00:06,210 --> 00:00:10,500
Now for this let's go ahead and write the function check if can finish.

4
00:00:12,910 --> 00:00:17,380
And this is going to be the implementation of the topological sort which we discussed.

5
00:00:17,410 --> 00:00:21,190
Now this function is going to take in n and the prereqs.

6
00:00:23,090 --> 00:00:23,780
All right.

7
00:00:24,510 --> 00:00:27,930
Now inside this function let's have a stack.

8
00:00:27,930 --> 00:00:29,040
So let's initialize this.

9
00:00:29,040 --> 00:00:30,270
So const stack.

10
00:00:30,270 --> 00:00:32,670
Now at this point it's going to be empty.

11
00:00:32,700 --> 00:00:39,840
Now we will call our helper function to get the adjacency list and the indegree array for each of the

12
00:00:39,840 --> 00:00:40,440
vertices.

13
00:00:40,440 --> 00:00:47,040
So let's say const and we will have our helper function which will just return an array of arrays.

14
00:00:47,040 --> 00:00:50,640
So one element in this array is going to be our adjacency list.

15
00:00:51,670 --> 00:00:54,970
And the second element is going to be the in degree array.

16
00:00:55,000 --> 00:00:55,420
All right.

17
00:00:55,420 --> 00:00:57,820
So I'm just doing this together.

18
00:00:57,820 --> 00:01:03,340
So that's why we have over here uh the adjacency list and in degree as two elements of this array.

19
00:01:03,340 --> 00:01:09,460
So this is the way that you can return two different arrays in JavaScript right from the same function.

20
00:01:09,460 --> 00:01:13,030
And this is going to be what we get back from our helper function.

21
00:01:13,030 --> 00:01:16,420
And this function is going to take in n and the prereqs.

22
00:01:16,420 --> 00:01:18,580
So let's go ahead and write our helper function.

23
00:01:18,580 --> 00:01:20,830
So let's just have a placeholder over here.

24
00:01:20,830 --> 00:01:25,210
Now I'm saying const helper is equal to function.

25
00:01:25,210 --> 00:01:27,880
And this takes in n and the prereqs.

26
00:01:28,270 --> 00:01:28,690
All right.

27
00:01:28,690 --> 00:01:31,690
So we will come back and fill this up later.

28
00:01:31,690 --> 00:01:37,420
So at this point we have got our adjacency list and the Indegree array which has the indegree factor

29
00:01:37,420 --> 00:01:38,470
for each element.

30
00:01:38,470 --> 00:01:45,400
Now let's just loop through the Indegree array and identify the indices or the vertices where the indegree

31
00:01:45,400 --> 00:01:45,880
is zero.

32
00:01:45,880 --> 00:01:48,070
And let's push that to our stack.

33
00:01:48,070 --> 00:01:53,560
So we say for let I is equal to zero I less than.

34
00:01:54,510 --> 00:01:56,730
Indegree dot length.

35
00:01:58,780 --> 00:02:01,960
I plus plus or again in degree dot length.

36
00:02:01,960 --> 00:02:09,640
Or I can just say n and I say I plus plus right now for each of these indices let's check the indicator

37
00:02:09,670 --> 00:02:10,300
value.

38
00:02:10,300 --> 00:02:13,750
So if that is equal to zero we will push it to our stack.

39
00:02:13,750 --> 00:02:20,380
So if in degree at I if this is equal to zero then we will push it to our stack.

40
00:02:20,380 --> 00:02:22,750
So we can say stack dot push.

41
00:02:26,200 --> 00:02:28,690
I, which is the vertex itself.

42
00:02:28,690 --> 00:02:29,020
Right.

43
00:02:29,020 --> 00:02:34,810
So we are just getting all the vertices which have an indegree factor zero into our stack.

44
00:02:34,810 --> 00:02:37,450
Now let's have count is equal to zero.

45
00:02:37,480 --> 00:02:37,750
All right.

46
00:02:37,750 --> 00:02:39,940
So we initializing a variable count.

47
00:02:39,940 --> 00:02:41,590
And let's say that's equal to zero.

48
00:02:42,380 --> 00:02:48,350
And we will be incrementing it whenever we take something out from our stack, and we will have a while

49
00:02:48,350 --> 00:02:48,560
loop.

50
00:02:48,560 --> 00:02:51,050
So let's say while stack dot length.

51
00:02:51,050 --> 00:02:55,220
So as long as something is there in the stack, we will keep looping through.

52
00:02:55,670 --> 00:03:01,250
And at the end of this while loop, when we come out, we're just going to check whether count is equal

53
00:03:01,250 --> 00:03:03,200
to n right, which is the number of vertices.

54
00:03:03,200 --> 00:03:08,150
So if count is equal to n then we will return true which means that there is no cycle.

55
00:03:08,150 --> 00:03:10,400
And hence we can finish all the courses.

56
00:03:10,400 --> 00:03:16,760
And if it's false, if count is not equal to n, then we did not get every vertex into the stack.

57
00:03:16,760 --> 00:03:22,460
And that's because every vertex at no point, every vertex had the indegree factor equal to zero.

58
00:03:22,460 --> 00:03:24,740
And that is possible when there is a cycle, right.

59
00:03:24,740 --> 00:03:25,820
So let's proceed.

60
00:03:25,820 --> 00:03:31,250
So inside the while loop we are going to take from the stack from the end the element.

61
00:03:31,250 --> 00:03:32,600
So we are going to pop from the stack.

62
00:03:32,600 --> 00:03:36,080
So let's say current is equal to stack dot pop.

63
00:03:37,140 --> 00:03:41,040
But we're just taking one element which has indegree factor equal to zero.

64
00:03:41,040 --> 00:03:42,840
And then we are just incrementing count.

65
00:03:42,840 --> 00:03:44,370
So we say count plus plus.

66
00:03:44,940 --> 00:03:45,420
All right.

67
00:03:45,420 --> 00:03:51,990
Now what we will do is we will identify its neighbors and we will decrease the indegree factor of its

68
00:03:51,990 --> 00:03:53,520
neighbors by one by one.

69
00:03:53,580 --> 00:04:00,390
Say const neighbors is equal to adjacency list at current right.

70
00:04:01,790 --> 00:04:04,670
So we get the array of its neighbors.

71
00:04:04,700 --> 00:04:09,320
Now we are just going to loop through these and decrement their indegree factor by one.

72
00:04:09,320 --> 00:04:17,090
So for let I is equal to zero I less than neighbors dot length I plus plus.

73
00:04:19,390 --> 00:04:22,630
Now for each neighbor, let's say const neighbor.

74
00:04:23,830 --> 00:04:27,280
Is equal to neighbors at I to make our code a bit cleaner.

75
00:04:28,330 --> 00:04:35,710
Now for each neighbor, we will decrease their indegree factor by one so we can say indegree at neighbor

76
00:04:36,490 --> 00:04:37,720
minus minus.

77
00:04:38,260 --> 00:04:40,990
So we are decrementing the indegree factor by one.

78
00:04:40,990 --> 00:04:44,290
Now we will check if the indegree factor has become zero.

79
00:04:44,290 --> 00:04:46,570
So if indegree at neighbor.

80
00:04:47,380 --> 00:04:53,380
If this is equal to zero, then we will push it to our stack so we can say stack, dot, push.

81
00:04:55,210 --> 00:04:56,020
Neighbor.

82
00:04:57,840 --> 00:04:58,170
All right.

83
00:04:58,170 --> 00:04:58,920
So this is it.

84
00:04:58,920 --> 00:05:04,320
So now we when we come out of this while loop, we will just check what is the length of the count.

85
00:05:04,320 --> 00:05:08,340
So if the count is equal to n then that means that there is no cycle.

86
00:05:08,340 --> 00:05:11,850
That's why every element came to the stack at some point.

87
00:05:11,850 --> 00:05:13,830
So this is how we are going to implement this.

88
00:05:13,830 --> 00:05:16,380
Now we just have to finish our helper function.

89
00:05:16,890 --> 00:05:21,990
And the helper function is to build the adjacency list and the Indegree array together.

90
00:05:21,990 --> 00:05:24,630
Now let's say const adjacency list.

91
00:05:28,030 --> 00:05:30,010
Is equal to new array.

92
00:05:31,360 --> 00:05:37,210
Of length n, and then let's just fill every element with zero, every position with zero.

93
00:05:37,780 --> 00:05:40,690
And now we're just going to map through every position.

94
00:05:40,690 --> 00:05:43,120
And we are going to change it to an empty array.

95
00:05:47,470 --> 00:05:47,770
All right.

96
00:05:47,770 --> 00:05:51,340
So at this point we have an array of arrays which is the adjacency list.

97
00:05:51,340 --> 00:05:53,590
And every element is just an empty array.

98
00:05:53,620 --> 00:05:55,990
Now let's also say const indegree.

99
00:05:57,980 --> 00:06:01,550
This is also going to be a new array of length n.

100
00:06:03,100 --> 00:06:04,720
And let's just fill it with zero.

101
00:06:04,720 --> 00:06:09,310
So the indegree factor of every element at this point is taken as zero.

102
00:06:09,340 --> 00:06:09,850
All right.

103
00:06:09,850 --> 00:06:13,660
Now let's just loop through the prereqs which is given to us.

104
00:06:13,660 --> 00:06:17,830
So for let prereq of prereqs.

105
00:06:18,910 --> 00:06:20,860
So we take each prerequisite.

106
00:06:21,400 --> 00:06:27,520
And again, remember if we have an element something like this, like one comma two, this means that

107
00:06:27,520 --> 00:06:29,650
to take we have to take one.

108
00:06:29,650 --> 00:06:30,670
We have to first take two.

109
00:06:30,670 --> 00:06:30,940
Right.

110
00:06:30,940 --> 00:06:32,980
So this means the link is like this.

111
00:06:32,980 --> 00:06:35,590
So we have to first take two to take one.

112
00:06:35,590 --> 00:06:40,900
So for each prereq I can say const and let's have two variables.

113
00:06:40,900 --> 00:06:46,570
So I can say the first one is to take and the second variable I'm just naming it first take to make

114
00:06:46,570 --> 00:06:47,470
it meaningful.

115
00:06:49,620 --> 00:06:51,570
So we can say whatever we have over here.

116
00:06:51,570 --> 00:06:55,860
So to take one we have to first take two or the link is from 2 to 1.

117
00:06:55,860 --> 00:06:58,680
Now this is going to be equal to pre-req.

118
00:06:59,340 --> 00:06:59,730
All right.

119
00:06:59,730 --> 00:07:03,420
So the value at index zero is going to go to two take.

120
00:07:03,420 --> 00:07:07,710
And the value at index one is going to take is is going to the variable first take.

121
00:07:07,710 --> 00:07:09,480
So we're just doing it in this manner.

122
00:07:09,480 --> 00:07:11,760
So it's shorter the code is shorter.

123
00:07:11,760 --> 00:07:16,920
And then we are just going to push to our adjacency list the correct edge.

124
00:07:16,920 --> 00:07:17,100
Right.

125
00:07:17,100 --> 00:07:22,890
So in our adjacency list at first take we are going to push the value of to take.

126
00:07:22,890 --> 00:07:24,930
So dot push to take.

127
00:07:25,260 --> 00:07:26,160
Now why is that.

128
00:07:26,160 --> 00:07:28,800
So for example over here we have one comma two.

129
00:07:28,800 --> 00:07:30,390
Now the link is from 2 to 1.

130
00:07:30,390 --> 00:07:33,510
So at index two we are going to add the value one.

131
00:07:33,510 --> 00:07:35,370
So at index two we have an array.

132
00:07:35,370 --> 00:07:37,950
So to that array we are going to push this value one.

133
00:07:37,950 --> 00:07:39,780
So that is what is happening over here.

134
00:07:39,780 --> 00:07:40,410
All right.

135
00:07:40,410 --> 00:07:45,840
Now we also need to increment our indegree factor for to take right.

136
00:07:45,840 --> 00:07:48,960
Because over here you can see that to take is one right.

137
00:07:48,960 --> 00:07:50,880
And over here we have one.

138
00:07:50,880 --> 00:07:52,860
Now into one there is a link right.

139
00:07:52,860 --> 00:07:56,370
So we have to increment the indegree factor of to take.

140
00:07:56,370 --> 00:07:58,860
So we can say indegree.

141
00:08:00,440 --> 00:08:01,640
Add to take.

142
00:08:03,760 --> 00:08:04,570
Plus plus.

143
00:08:04,690 --> 00:08:09,310
So we are incrementing the indegree factor at to take plus by one.

144
00:08:09,340 --> 00:08:15,670
Now once we are out of this for loop, we have built our adjacency list and our indegree array and we

145
00:08:15,670 --> 00:08:17,410
just need to return both of these.

146
00:08:17,410 --> 00:08:22,000
So that's why just we are just making them into one array where these two are the elements.

147
00:08:22,000 --> 00:08:24,280
So adjacency list is the first element.

148
00:08:24,280 --> 00:08:26,890
And the second element is the indegree array.

149
00:08:26,890 --> 00:08:28,810
So that we can return them together.

150
00:08:28,810 --> 00:08:33,430
Because there is no way that you in JavaScript you can return two things separately, right?

151
00:08:33,430 --> 00:08:37,540
So we can just make both of the things into one array and return it as one array.

152
00:08:37,540 --> 00:08:41,740
So over here when we call the helper function we get back this array.

153
00:08:41,740 --> 00:08:47,260
And we have the first element over here at index zero we call it adjacency list.

154
00:08:47,260 --> 00:08:50,200
And the indegree is passed to this indegree over here.

155
00:08:50,200 --> 00:08:52,000
So this is how our function works.

156
00:08:52,000 --> 00:08:52,780
Now we are done.

157
00:08:52,780 --> 00:08:56,050
Now let's go ahead and test our function and see whether it's working.

158
00:08:56,050 --> 00:08:58,510
Now first let's just have a simple example.

159
00:08:58,510 --> 00:09:01,210
Let's say n is equal to two.

160
00:09:01,210 --> 00:09:07,510
And let's say the prerequisite bits are and it's an array of arrays.

161
00:09:07,510 --> 00:09:10,750
And the first element is going to be zero comma one.

162
00:09:11,290 --> 00:09:13,600
And let's say the second element is one comma zero.

163
00:09:13,600 --> 00:09:14,920
So there is a clear cycle.

164
00:09:14,920 --> 00:09:16,570
So we should be getting false.

165
00:09:16,570 --> 00:09:17,740
So let's.

166
00:09:18,860 --> 00:09:19,790
Call our function.

167
00:09:19,790 --> 00:09:23,930
So check if can finished and we will just pass in n and p.

168
00:09:26,350 --> 00:09:29,890
And let's call our function and let's see what is it that we are getting?

169
00:09:29,890 --> 00:09:31,540
We are expecting that we should get false.

170
00:09:31,540 --> 00:09:32,620
Yes, we are getting false.

171
00:09:32,620 --> 00:09:34,030
So yes, this is working.

172
00:09:34,030 --> 00:09:37,690
Now let's try one more example four comma three, which is the link from 3 to 4.

173
00:09:37,690 --> 00:09:42,610
Now the expectation is that we should get false because we can see there is a cycle over here.

174
00:09:42,610 --> 00:09:42,790
Right.

175
00:09:42,790 --> 00:09:45,760
So let's go ahead and let's try to run our code.

176
00:09:45,760 --> 00:09:47,680
And yes we are getting false over here.

177
00:09:47,680 --> 00:09:49,330
So yes our code is working.

178
00:09:49,330 --> 00:09:52,030
Now let's try to take this example.

179
00:09:52,030 --> 00:09:55,390
And let's walk through the code and let's try to see what's happening.