Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Course Schedule II

Hard
0/120
Average time to solve is 50m
profile
Contributed by
27 upvotes
Asked in companies
AppleUberPhone Pe

Problem statement

You have been given ‘N’ courses and some courses may have prerequisites. Now consider a matrix ‘PREREQUISITES’ of size 'M' x 2 which represents that you must complete the course 'PREREQUISITES[i][1]' before the course 'PREREQUISITES[i][0]'.


Your task is to return the order of courses you should take to finish all courses.


Note:
If it is impossible to finish all courses, return an empty array. If there are multiple answers, return any one.


For example:
Input:
3 2
1 2
2 3

There are three courses to take. To start with, First course 3 is taken. Then course 2 is taken for which course 3 must be completed. 

At last course 1 is taken for which course 2 must be completed. So the correct course order is [3,2,1].    
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1:
4 4
2 1
3 1
4 2
4 3
Sample Output 1:
1
Explanation of Sample Output 1:
There are a total of 4 courses to take. To take course 4 you should have finished both courses 2 and 3. 

Both courses 2 and 3 should be taken after you finish course 1. So one correct course order is [1,2,3,4]. Another correct ordering is [1,3,2,4]. 

When the ordering is one of the above two sets then output is 1.
Sample Input 2:
2 1
2 1
Sample Output 2:
1
Constraints :
2 <= 'N' <= 10^5
0 <= 'M' <= 10^5

Where ‘PREREQUISITES’ denotes the prerequisites matrix.

Time limit: 1 sec
Full screen
Console