Hi everyone.
Let's do this question.
You have to take a total of N courses labeled from zero to n minus one.
Before you can take some courses, you need to take its prerequisite courses.
You are given an array prerequisites where each element x comma y indicates that to take course x,
you have to take y first.
For example, two comma three indicates that to take course two, one has to first take course three.
Write a function that takes in n and the prerequisite array and returns true.
If you can complete all courses, else return false.
So let's go ahead and understand this question.
Now over here it's mentioned that two comma three indicates that to take course two one has to first
take course three.
So we can visualize this in this manner.
So two comma three indicates we have a link from 3 to 2.
Right.
Because it says that to take two we have to do first three.
So first two three then you can go ahead and do two.
So this is how this can be visualized.
Now let's take a few examples to understand this question.
Now again we have to do courses from zero to n minus one.
And then there are some prerequisites right.
So let's take two examples.
Let's say this is the graph which is given to us.
Again we have to understand that this is actually a graph question.
So if there is a link from 1 to 2 that is before doing two we have to do one.
And then before doing three we have to do course two.
And then before doing course five we have to do course four.
So we can complete the courses.
Right.
We just need to do one.
Then we can go ahead and do two.
And then we can go ahead and do three.
And after doing four we can go ahead and do five.
So it's possible to complete all the courses.
But let's say the graph is modeled like this.
That is to do one.
To do two you have to do one.
All right.
So this would be a link like this right.
So you can write it like this two comma one.
That means to do two you have to do one.
All right.
Now this two two from 2 to 3.
This can be visualized as per what is given over here.
This would be denoted as three comma two.
So to do three you have to do two first.
And then you have a link from 3 to 1.
Right.
So you have one comma three over here.
That is to do one you have to first do three.
All right.
So again to do two you have to do one.
Similarly to do one you have to do three.
And to do three you have to do two.
Again over here you can see there is no place you can start right.
You cannot start at one because you have to do three before that.
But then you cannot start at three because you have to do two before that.
And again, you cannot start at two because you have to do one before that.
So if there is a cycle in this manner, then the answer would be false or you are not able to complete
all the courses.
So this is the question.
All right.
So we will be given an array of prerequisites.
And then we will be given the value n which indicates that there are the courses from zero to n minus
one.
And then we need to write a function to check whether it's possible to complete all the courses, or
whether it's not possible to complete all the courses.
And we have seen that in the case that where there is a cycle, in that case, it will not be possible
to complete all the courses.
Now in the interview, if you are getting this question, make sure that you ask sufficient clarifying
questions so that you understand the question thoroughly and you and the interviewer are on the same
page.
Now, a possible question could be can there be courses that do not have a prerequisite, for example,
something like this.
Just six, right.
You could just have course six over here.
And let's say the interviewer says yes that's possible.
All right.
And again you could ask is is it possible that the graph is not there.
There can be unconnected components.
So again he would he or she would reply, yes.
Because over here you can see that this part and this part is not connected.
Now again you can ask as many questions as you want so that you you have understood the question very
thoroughly.
Now let's go ahead and write a few test cases, because we have developed a good understanding of the
question.
Now in the interview, you can always ask the interviewer whether it's okay, whether he or she can
come up with a few test cases together with you.
Right.
So this is a good practice so that again, this helps to ensure that you have thoroughly understood
the question and you know what the expectation is.
Now let's go ahead and write a few test cases.
Let's say the number of nodes are four.
And we.
So they are 012 and three.
So this would be n.
All right.
So this would be n n is equal to four.
And let's say the graph is modeled like this.
So there is a connection from 0 to 1 from 1 to 2 and from 1 to 3.
So in terms of the prerequisite array right which is given to us, it would be something like this.
Right.
So you have one comma zero which indicates that you have to do zero before you can do you can do one.
And then you have two comma one which indicates that you have to do one before you can do two.
And then you have three comma one over here, which indicates that you have to do one before you can
do three.
All right.
So in this case again we can reply true.
Right.
Because this is possible.
We can just start with zero.
And then we can go ahead and do one.
Then we can go ahead and two do two.
And then we can go ahead.
And do three.
So in this case, the answer would be true.
Now let's take another case.
Let's say n is equal to six.
In that case the vertices will be zero, one, two, three, four, and five.
And let's say the graph is modeled like this.
So we have zero over here, one over here which are not connected.
And then we have two, three, four and five in this manner.
So how would the prerequisite array look in this case.
It would be like this, right?
So from two before doing three you have to do two.
So you have three comma two over here.
And then before doing four you have to do three.
So you have four comma three.
Before you can do five you have to do four.
So you have five comma four.
And before you can do two you have to do five.
So you have two comma five over here.
So this is how these prerequisites would be mentioned.
And then nothing is mentioned about zero and one.
So they are just disconnected.
Now in this case we would have to return false because you can see a cycle is being formed.
So you cannot start anywhere right.
You cannot start at two because before doing two you would have to do five again.
You cannot do you cannot start at three because three before doing three you will have to do two.
So in this case we will have to return false and we will not be able to complete all the courses.
So we have developed a good understanding of the question and we have written out some test cases.
In the next video.
Let's see how we can solve this question.
First we will discuss the brute force method and then let's discuss the optimal solution.