1
00:00:00,850 --> 00:00:01,690
Hi everyone.

2
00:00:01,690 --> 00:00:03,160
Let's do this question.

3
00:00:03,160 --> 00:00:08,710
You have to take a total of N courses labeled from zero to n minus one.

4
00:00:08,710 --> 00:00:13,750
Before you can take some courses, you need to take its prerequisite courses.

5
00:00:13,750 --> 00:00:20,200
You are given an array prerequisites where each element x comma y indicates that to take course x,

6
00:00:20,200 --> 00:00:22,270
you have to take y first.

7
00:00:22,270 --> 00:00:27,820
For example, two comma three indicates that to take course two, one has to first take course three.

8
00:00:27,820 --> 00:00:33,070
Write a function that takes in n and the prerequisite array and returns true.

9
00:00:33,070 --> 00:00:36,580
If you can complete all courses, else return false.

10
00:00:36,580 --> 00:00:38,770
So let's go ahead and understand this question.

11
00:00:38,770 --> 00:00:44,080
Now over here it's mentioned that two comma three indicates that to take course two one has to first

12
00:00:44,080 --> 00:00:45,070
take course three.

13
00:00:45,070 --> 00:00:47,470
So we can visualize this in this manner.

14
00:00:47,470 --> 00:00:51,190
So two comma three indicates we have a link from 3 to 2.

15
00:00:51,190 --> 00:00:51,400
Right.

16
00:00:51,400 --> 00:00:54,910
Because it says that to take two we have to do first three.

17
00:00:54,910 --> 00:00:58,360
So first two three then you can go ahead and do two.

18
00:00:58,360 --> 00:01:00,520
So this is how this can be visualized.

19
00:01:00,520 --> 00:01:03,610
Now let's take a few examples to understand this question.

20
00:01:03,610 --> 00:01:07,000
Now again we have to do courses from zero to n minus one.

21
00:01:07,000 --> 00:01:09,040
And then there are some prerequisites right.

22
00:01:09,040 --> 00:01:10,570
So let's take two examples.

23
00:01:10,570 --> 00:01:13,090
Let's say this is the graph which is given to us.

24
00:01:13,090 --> 00:01:15,880
Again we have to understand that this is actually a graph question.

25
00:01:15,880 --> 00:01:20,290
So if there is a link from 1 to 2 that is before doing two we have to do one.

26
00:01:20,290 --> 00:01:22,900
And then before doing three we have to do course two.

27
00:01:22,900 --> 00:01:26,110
And then before doing course five we have to do course four.

28
00:01:26,110 --> 00:01:27,820
So we can complete the courses.

29
00:01:27,820 --> 00:01:28,030
Right.

30
00:01:28,030 --> 00:01:29,170
We just need to do one.

31
00:01:29,170 --> 00:01:30,820
Then we can go ahead and do two.

32
00:01:31,360 --> 00:01:33,010
And then we can go ahead and do three.

33
00:01:33,010 --> 00:01:35,620
And after doing four we can go ahead and do five.

34
00:01:35,620 --> 00:01:38,020
So it's possible to complete all the courses.

35
00:01:38,020 --> 00:01:40,780
But let's say the graph is modeled like this.

36
00:01:40,780 --> 00:01:42,520
That is to do one.

37
00:01:42,520 --> 00:01:44,140
To do two you have to do one.

38
00:01:44,140 --> 00:01:44,560
All right.

39
00:01:44,560 --> 00:01:46,810
So this would be a link like this right.

40
00:01:46,810 --> 00:01:49,510
So you can write it like this two comma one.

41
00:01:49,510 --> 00:01:52,300
That means to do two you have to do one.

42
00:01:52,300 --> 00:01:52,720
All right.

43
00:01:52,750 --> 00:01:55,300
Now this two two from 2 to 3.

44
00:01:55,300 --> 00:01:58,270
This can be visualized as per what is given over here.

45
00:01:58,270 --> 00:02:00,850
This would be denoted as three comma two.

46
00:02:00,850 --> 00:02:03,430
So to do three you have to do two first.

47
00:02:03,430 --> 00:02:05,350
And then you have a link from 3 to 1.

48
00:02:05,350 --> 00:02:05,710
Right.

49
00:02:05,710 --> 00:02:07,750
So you have one comma three over here.

50
00:02:07,750 --> 00:02:11,350
That is to do one you have to first do three.

51
00:02:11,350 --> 00:02:11,740
All right.

52
00:02:11,740 --> 00:02:13,990
So again to do two you have to do one.

53
00:02:13,990 --> 00:02:16,210
Similarly to do one you have to do three.

54
00:02:16,210 --> 00:02:18,310
And to do three you have to do two.

55
00:02:18,340 --> 00:02:21,580
Again over here you can see there is no place you can start right.

56
00:02:21,580 --> 00:02:24,280
You cannot start at one because you have to do three before that.

57
00:02:24,280 --> 00:02:27,610
But then you cannot start at three because you have to do two before that.

58
00:02:27,610 --> 00:02:30,850
And again, you cannot start at two because you have to do one before that.

59
00:02:30,850 --> 00:02:37,510
So if there is a cycle in this manner, then the answer would be false or you are not able to complete

60
00:02:37,510 --> 00:02:38,440
all the courses.

61
00:02:38,440 --> 00:02:39,610
So this is the question.

62
00:02:39,610 --> 00:02:39,970
All right.

63
00:02:39,970 --> 00:02:42,700
So we will be given an array of prerequisites.

64
00:02:42,700 --> 00:02:48,760
And then we will be given the value n which indicates that there are the courses from zero to n minus

65
00:02:48,760 --> 00:02:49,060
one.

66
00:02:49,060 --> 00:02:54,940
And then we need to write a function to check whether it's possible to complete all the courses, or

67
00:02:54,940 --> 00:02:57,460
whether it's not possible to complete all the courses.

68
00:02:57,460 --> 00:03:02,740
And we have seen that in the case that where there is a cycle, in that case, it will not be possible

69
00:03:02,740 --> 00:03:04,180
to complete all the courses.

70
00:03:04,180 --> 00:03:09,520
Now in the interview, if you are getting this question, make sure that you ask sufficient clarifying

71
00:03:09,520 --> 00:03:14,500
questions so that you understand the question thoroughly and you and the interviewer are on the same

72
00:03:14,500 --> 00:03:14,950
page.

73
00:03:14,950 --> 00:03:21,070
Now, a possible question could be can there be courses that do not have a prerequisite, for example,

74
00:03:21,070 --> 00:03:22,090
something like this.

75
00:03:22,090 --> 00:03:23,020
Just six, right.

76
00:03:23,020 --> 00:03:25,000
You could just have course six over here.

77
00:03:25,000 --> 00:03:28,000
And let's say the interviewer says yes that's possible.

78
00:03:28,000 --> 00:03:28,450
All right.

79
00:03:28,450 --> 00:03:32,680
And again you could ask is is it possible that the graph is not there.

80
00:03:32,680 --> 00:03:34,480
There can be unconnected components.

81
00:03:34,480 --> 00:03:37,300
So again he would he or she would reply, yes.

82
00:03:37,300 --> 00:03:41,140
Because over here you can see that this part and this part is not connected.

83
00:03:41,140 --> 00:03:46,270
Now again you can ask as many questions as you want so that you you have understood the question very

84
00:03:46,270 --> 00:03:46,810
thoroughly.

85
00:03:46,810 --> 00:03:51,490
Now let's go ahead and write a few test cases, because we have developed a good understanding of the

86
00:03:51,490 --> 00:03:52,060
question.

87
00:03:52,060 --> 00:03:57,160
Now in the interview, you can always ask the interviewer whether it's okay, whether he or she can

88
00:03:57,160 --> 00:04:00,010
come up with a few test cases together with you.

89
00:04:00,010 --> 00:04:00,250
Right.

90
00:04:00,250 --> 00:04:04,600
So this is a good practice so that again, this helps to ensure that you have thoroughly understood

91
00:04:04,600 --> 00:04:07,480
the question and you know what the expectation is.

92
00:04:07,480 --> 00:04:09,730
Now let's go ahead and write a few test cases.

93
00:04:09,730 --> 00:04:13,060
Let's say the number of nodes are four.

94
00:04:13,060 --> 00:04:14,380
And we.

95
00:04:14,380 --> 00:04:16,300
So they are 012 and three.

96
00:04:16,300 --> 00:04:17,290
So this would be n.

97
00:04:17,290 --> 00:04:17,650
All right.

98
00:04:17,650 --> 00:04:19,780
So this would be n n is equal to four.

99
00:04:19,780 --> 00:04:21,970
And let's say the graph is modeled like this.

100
00:04:21,970 --> 00:04:26,170
So there is a connection from 0 to 1 from 1 to 2 and from 1 to 3.

101
00:04:26,170 --> 00:04:30,880
So in terms of the prerequisite array right which is given to us, it would be something like this.

102
00:04:30,880 --> 00:04:31,180
Right.

103
00:04:31,180 --> 00:04:37,750
So you have one comma zero which indicates that you have to do zero before you can do you can do one.

104
00:04:37,750 --> 00:04:43,240
And then you have two comma one which indicates that you have to do one before you can do two.

105
00:04:43,240 --> 00:04:47,860
And then you have three comma one over here, which indicates that you have to do one before you can

106
00:04:47,860 --> 00:04:48,430
do three.

107
00:04:48,430 --> 00:04:48,790
All right.

108
00:04:48,790 --> 00:04:52,810
So in this case again we can reply true.

109
00:04:52,810 --> 00:04:53,110
Right.

110
00:04:53,110 --> 00:04:54,190
Because this is possible.

111
00:04:54,190 --> 00:04:55,510
We can just start with zero.

112
00:04:55,510 --> 00:04:57,520
And then we can go ahead and do one.

113
00:04:57,520 --> 00:04:59,530
Then we can go ahead and two do two.

114
00:04:59,530 --> 00:05:00,430
And then we can go ahead.

115
00:05:00,680 --> 00:05:01,520
And do three.

116
00:05:01,520 --> 00:05:04,340
So in this case, the answer would be true.

117
00:05:04,850 --> 00:05:06,380
Now let's take another case.

118
00:05:06,380 --> 00:05:08,420
Let's say n is equal to six.

119
00:05:08,600 --> 00:05:14,120
In that case the vertices will be zero, one, two, three, four, and five.

120
00:05:14,120 --> 00:05:16,460
And let's say the graph is modeled like this.

121
00:05:16,460 --> 00:05:19,550
So we have zero over here, one over here which are not connected.

122
00:05:19,550 --> 00:05:22,340
And then we have two, three, four and five in this manner.

123
00:05:22,340 --> 00:05:25,430
So how would the prerequisite array look in this case.

124
00:05:26,010 --> 00:05:27,180
It would be like this, right?

125
00:05:27,180 --> 00:05:30,240
So from two before doing three you have to do two.

126
00:05:30,270 --> 00:05:31,920
So you have three comma two over here.

127
00:05:31,920 --> 00:05:34,620
And then before doing four you have to do three.

128
00:05:34,620 --> 00:05:35,880
So you have four comma three.

129
00:05:35,880 --> 00:05:38,130
Before you can do five you have to do four.

130
00:05:38,130 --> 00:05:39,720
So you have five comma four.

131
00:05:39,720 --> 00:05:42,030
And before you can do two you have to do five.

132
00:05:42,030 --> 00:05:43,620
So you have two comma five over here.

133
00:05:43,620 --> 00:05:46,530
So this is how these prerequisites would be mentioned.

134
00:05:46,530 --> 00:05:49,020
And then nothing is mentioned about zero and one.

135
00:05:49,020 --> 00:05:50,430
So they are just disconnected.

136
00:05:50,430 --> 00:05:55,770
Now in this case we would have to return false because you can see a cycle is being formed.

137
00:05:55,770 --> 00:05:57,360
So you cannot start anywhere right.

138
00:05:57,360 --> 00:06:01,230
You cannot start at two because before doing two you would have to do five again.

139
00:06:01,230 --> 00:06:05,910
You cannot do you cannot start at three because three before doing three you will have to do two.

140
00:06:05,940 --> 00:06:11,640
So in this case we will have to return false and we will not be able to complete all the courses.

141
00:06:11,640 --> 00:06:16,410
So we have developed a good understanding of the question and we have written out some test cases.

142
00:06:16,410 --> 00:06:17,580
In the next video.

143
00:06:17,580 --> 00:06:20,160
Let's see how we can solve this question.

144
00:06:20,160 --> 00:06:24,840
First we will discuss the brute force method and then let's discuss the optimal solution.