Problem :
Given an integer array representing prerequisites of different courses and the total number of courses , find out the order in which the courses should be taken.
For example,
if the given input is [1,0]
It means to take course 1 you should have completed course 0.
Or in other words,
Course 0 is followed by Course 1.
So in the above case the output is [0,1]
If the input is [0,1] ,[1,0]
Then it means course 1 should be completed to do course 0.
And course 0 should be completed to do course 1.
This forms a cycle.
So the courses cannot be completed.
In this case return an empty integer array.
Try out the solution here:
https://leetcode.com/problems/course-schedule-ii
Solution:
This is very similar to the below problem:
In the above problem we are finding out if all the courses can be taken.
In the current problem we need to find out the order in which the courses can be taken if at all they all can be taken.
We are going to use the same algorithm here with little modification to prepare the output array of courses.
Approach 1 – Depth First Search
In this approach we are going to model the course requisites into a graph.
We will do a Depth First Traversal of each node .
As we visit each node we will also visit their neighbours.
When there are no more neighbors (reached the leaf node) we will add the node to a stack.
Finally we will pop all the nodes from the stack and add it to the output.
During this process we need to check two things:
- There is no cycle in the graph
- We are not visiting the same nodes again
First let’s see what are the data structures we need to solve this problem.
Data Structures :
- Adjacency List
We said we are going to model the dependencies of courses into a graph.
How to represent a graph ?
Let’s use the data structure – Adjacency List
What is an adjacency list ?
An adjacency list represents each course and their follow up courses.
So if course 1 follows course 0 (Course 1 is dependent on Course 0)
Then the adjacency list is :
0 -> 1
Also if course 2 also can be immediately taken after course 0 ,
Then the above adjacency list would be :
0 -> 1,2
How to represent an adjacency list?
you can represent an adjacency list in different ways:
- You can use a map with the node number as key and its dependants as a list
- You can use a list of list where each index of the parent list denotes the node and the child list represents the dependencies
- You can use a two dimensional integer array where the first dimension represents the node and the second represents the dependencies.
In this example we will use a list of lists.
Here is that data structure:
List<List<Integer>> adjNodes = new ArrayList<List<Integer>>();
We will go through the prerequisite array and populate this adjacency list.
2. Bitmaps
We are going to use two bitmaps.
Once to see if the same node is visited again while doing DFS for a particular node and its neighbors thereby forming a cycle.
Another to see if the same node is checked at any point during DFS.
3. Output stack / array
The solution requires us to return the output as an array.
We can use a stack to push elements into the stack at the end of each DFS iteration.
This way when we pop out the elements the elements at the top (who have no dependents) are added to the output first.
Instead of a stack we can also use an integer array.
But we have to start filling the array from the end instead of the beginning to simulate a stack.
We will use this approach to save some space complexity.
4. Boolean Flag
To represent if a cycle has been detected we will use a boolean flag.
Algorithm:
- Prepare an adjacency list with the given prerequisites data
- For each node , check if the node has been already visited and there is no cycle detected already
- If cycle is detected return empty array
- Else if the node has not already been checked do DFS:
- Check if there is any cycle , if so return
- Mark the current node as visited to do backtracking
- For each neighbor of the current node do DFS recursively (provided it is not already checked)
- During this process if the same node is visited again then there is a cycle , mark the cycle flag as true
- Once backtracking is done mark the current node as not visited to consider it again for further iterations
- Mark the current node as checked and add it to the output at the end .
Code:
class Solution {
boolean isCyclic = false;
int[] output ;
boolean[] visited;
boolean[] checked;
int outputIndex;
List<List<Integer>> adjNodes = new ArrayList<List<Integer>>();
public int[] findOrder(int numCourses, int[][] prerequisites) {
for(int i=0;i<numCourses;i++){
adjNodes.add(new ArrayList<Integer>());
}
for(int[] i:prerequisites){
adjNodes.get(i[1]).add(i[0]);
}
this.visited = new boolean[numCourses];
this.checked = new boolean[numCourses];
this.outputIndex = numCourses-1;
this.output = new int[numCourses];
for(int i=0;i<numCourses;i++){
if(this.isCyclic)return new int[]{};
if(!checked[i])
dfs(i);
}
return output;
}
public void dfs(int courseNo){
if(this.isCyclic) return;
visited[courseNo] = true;
List<Integer> relations = adjNodes.get(courseNo);
for(Integer i:relations){
if(visited[i]){
this.isCyclic = true;
}else if(!checked[i]){
dfs(i);
}
}
visited[courseNo] = false;
checked[courseNo] = true;
output[outputIndex--] = courseNo;
}
}
Time complexity :
We go through each node and its edges , so time complexity is O(V + E) where V represent the number of vertices and E represent the number of edges.
Space complexity:
We use an adjacency list to represent each node and its edges.
This contains each node and its edges .
So space complexity is O( V + E)
We also do recursive calls which in the worst case can be equal to O(V) for a tree which has only a single node at each level. At each level we will be making a recursive call (since for each neighbor we make recursive call in the code)
Approach 2 – Kahn’s algorithm:
Another approach is using Kahn’s algorithm.
In this algorithm also we make use of adjacency list.
In addition we make use of one more data structure named indegrees .
This will contain the number of incoming connections to each node.
We will also be using a queue to add nodes with no incoming connections.
Algorithm:
- Prepare an adjacency list to represent the course dependencies
- Prepare an indegree list to represent the number of incoming connections for each node.
- Push all the nodes with no incoming edges to the queue. These courses have no dependencies so they can be taken first. Also add them to the output array
- Poll the top node from the queue and check its neighbors.
- Reduce the incoming count by one for these neighbors.
- if during these process any of their indegree becomes 0 add them to the queue.
- Finally if the number of courses equals the size of the output array then there is no cycle so return the output
- Else there is a cycle so return an empty array
Code:
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] indegrees = new int[numCourses];
List<List<Integer>> adjList = new ArrayList<>();
int[] output = new int[numCourses];
for(int i=0;i<numCourses;i++){
adjList.add(new ArrayList<Integer>());
}
for(int[] node:prerequisites){
adjList.get(node[1]).add(node[0]);
indegrees[node[0]]++;
}
Queue<Integer> q = new LinkedList<Integer>();
for(int i=0;i<indegrees.length;i++){
if(indegrees[i] == 0){
q.add(i);
}
}
int index = 0;
while(!q.isEmpty()){
int n = q.poll();
output[index++] = n;
List<Integer> neighbors = adjList.get(n);
for(int i:neighbors){
indegrees[i]--;
if(indegrees[i] == 0){
q.add(i);
}
}
}
if(index != numCourses) return new int[0];
return output;
}
}
Time complexity :
Since we go through each node and its neighbors (edges) once, time complexity is O(V + E)
Space complexity:
We use an adjacency list which stores each node and its edges O( V + E)
We use a queue where in the worst case we put all the nodes in O(V)
Total space complexity is O(V+E)
That’s it!
Leave a Reply