Course Schedule II

Hard
0/120
Average time to solve is 50m
profile
Contributed by
33 upvotes
Asked in companies
AmazonFacebookApple

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 )
Input Format: 
The first line contains two integers 'N' and 'M' representing the number of courses and the number of prerequisite pairs.

The next ‘M’ lines in each test case contain a matrix ‘PREREQUISITES’ containing two integers denoting a prerequisite pair.
Output Format: 
The only line contains a single integer 1 if the returned order of the courses is correct, otherwise 0.
Note: 
You don't need to print anything, it has already been taken care of. Just implement the given function.
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
Hint

Can you think of using the BFS approach?

Approaches (2)
Breadth-First Search

Our current algorithm is based on the idea of the BFS approach. We first process all the courses with 0 in-degree implying no prerequisite courses required. If we remove all these courses from the graph, along with their outgoing edges, we can find out the courses/nodes that should be processed next. These would again be the nodes with 0 in-degree. We can continuously do this until all the courses have been accounted for.

 

The steps are as follows:

 

  1. Firstly, initialize a queue, ‘Q’ to keep a track of all the nodes in the graph with 0 in-degree.
  2. Then Iterate over all the edges in the input and create an adjacency list and also a map of node v/s in-degree. Add all the nodes with 0 in-degree to ‘Q’.
  3. Keep following the below steps until the ‘Q’ becomes empty.
  4. Pop a node from the ‘Q’. Let's call this node, ‘N’.
  5. For all the neighbors of this node, ‘N’, reduce their in-degree by 1. If any of the nodes' in-degree reaches 0, add it to the ‘Q’.
  6. Add the node 'N' to the list maintaining topologically sorted order.
  7. Continue from step 3.
Time Complexity

O(N + M), where ‘N’ is the number of courses and ‘M’ is the number of prerequisites pairs.

 

Since the time complexity of this method is the same as the time complexity of the Breadth-First Search traversal i.e O(N + M) time, Thus the overall time complexity will be O(N + M).

Space Complexity

O(N), where ‘N’ is the number of courses.

 

Since we are storing the nodes with in-degree as 0 in a queue and the queue will be of size N, Thus the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Course Schedule II
Full screen
Console