Leetcode Problem - Parallel Courses

Problem link: https://leetcode.com/problems/parallel-courses/
Difficulty: Hard
Category: Graphs

Step 1: Grasping the Problem

There are N courses with a prerequisites relationship among them. Our task is to determine the number of semester needed to complete all the courses. Here are the key points that will help us get started:

We cannot take a course whose prerequisites are not yet taken.
We cannot take a course whose prerequisites are even taken in this semester.
We have to start with the course that has no prerequisites.
If there is a cycle in the prerequisites relationship, there will be no solution.

As there are relationship among courses and we need to pick and complete each course at semesters, we know that it is a graph problem. We need to check if there is any cycle or not, if there isn’t, then we will need to get the course whose prerequisites are all complete. This is exactly what Topological Sorting does.

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

So the answer of our problem is to make a topological ordering of the courses. And if we cannot make the ordering, then we will need to return -1.

Step 2: Build the Graph

To solve the problem with topological sorting, we need a graph first. In this graph, the nodes will be courses and the edges will be the relationships. The relationships are already given as edges relations. We will convert these into adjacency matrix representation.

So the graph will be a dictionary where, keys are courses and values are lists having courses that are dependent on the keys. We loop through relations and put them in the graph accordingly.

1
2
3
4
5
6
graph = {}
for relation in relations:
    # Make sure we don't get KeyError
    if relation[0] not in graph:
        graph[relation[0]] = []
    graph[relation[0]].append(relation[1])

Step 3: Topological Sorting Initialization

Topological Sorting requires us to track the in degrees of all nodes. For this, we will create an array named in_degree of size N+1. The courses in the problem is given in 1-indexed notation, for this, we have to create the extra unused index at 0.

1
2
in_degree = [0] * (N+1)
# Or: in_degree = [0 for _ in range(N+1)]

We can track the degrees while building the graph. Each time we find a relation, we increase the in degree of the descendant node.

1
2
3
4
5
6
7
8
# in_degree of N nodes, 1 indexed
in_degree = [0]*(N+1) # in_degree initialization
graph = {}
for relation in relations:
    if relation[0] not in graph:
        graph[relation[0]] = []
    graph[relation[0]].append(relation[1])
    in_degree[relation[1]] += 1 # update in_degree

Topological Sorting is very similar to BFS (Breadth First Search) or DFS (Depth First Search). Except that BFS/DFS starts from a source, topological sorting starts from all the nodes that has in_degree = 0. We will do a BFS. To do this, we will need a queue. For implementation, we will use pythons built-in collections.deque data structure. Start a loop through all the N courses, and put the courses that has in_degree = 0 into the queue.

1
2
3
4
5
# Collect all 0 in degree nodes
queue = deque()
for i in range(1, N+1):
    if in_degree[i] == 0:
        queue.append(i)

Step 4: Topological Sorting

Topological Sorting will keep running a loop until the queue is empty. At the beginning of the loop, we will keep track of how many courses we have in the queue. Because that will be the number of courses we can take in this semester (this_semester). this_semester is not used in anywhere, it is named so, for understanding purposes only.

At each semester, we will take each course from the queue, and decrease the in_degrees of all the courses that depend on current course. If in_degree for a course becomes 0, we push it into the queue to mark it available for the next semester. After doing this for all the queue elements, we will increament the semester by 1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# Topological sort
semesters = 0
courses_taken = 0
while queue:
    # len(queue) courses in 1 semester
    for this_semester in range(len(queue)):
        course = queue.popleft()
        courses_taken += 1

        if course in graph:
            for neighbor in graph[course]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
    semesters += 1

courses_taken another variable is used to count the number of courses popped from the queue. This will be used after the topological sorting to test if we could take all the courses or not. Here, courses_taken != N will be True when there is a cycle detected in the graph and there is no topological sorting possible.

Below is a demonstration of the topological sorting process.

topsort demo

If courses_taken == N, we know that we have taken all the courses, so we return the number of semesters.

1
2
3
4
5
# Make sure all courses are taken
if courses_taken != N:
    return -1

return semesters

This is a pure algorithm of topological sorting with no overhead. So the time and space complexity for this problem is that of topological sorting, O(N+|relations|) and O(N). The complete solution is given below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from collections import deque
from typing import List

class Solution:
    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
        # in_degree of N nodes, 1 indexed
        in_degree = [0]*(N+1)
        graph = {}
        for relation in relations:
            # Make sure we don't get KeyError
            if relation[0] not in graph:
                graph[relation[0]] = []
            graph[relation[0]].append(relation[1])
            in_degree[relation[1]] += 1

        # Collect all 0 in degree nodes
        queue = deque()
        for i in range(1, N+1):
            if in_degree[i] == 0:
                queue.append(i)
        
        # Topological sort
        semesters = 0
        courses_taken = 0
        while queue:
            # len(queue) courses in 1 semester
            for this_semester in range(len(queue)):
                course = queue.popleft()
                courses_taken += 1

                if course in graph:
                    for neighbor in graph[course]:
                        in_degree[neighbor] -= 1
                        if in_degree[neighbor] == 0:
                            queue.append(neighbor)
            semesters += 1

        # Make sure all courses are taken
        if courses_taken != N:
            return -1

        return semesters

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int minimumSemesters(int N, vector<vector<int>> &relations) {
        // in_degree of N nodes, 1 indexed
        vector<int> inDegree(N+1);
        map<int, vector<int>> graph;
        for(auto relation: relations) {
            graph[relation[0]].push_back(relation[1]);
            inDegree[relation[1]]++;
        }

        // Collect all 0 in degree nodes
        queue<int> q;
        for(int i = 1; i < N+1; i++)
            if(inDegree[i] == 0)
                q.push(i);
        
        // Topological sort
        int semesters = 0;
        int coursesTaken = 0;
        while(!q.empty()) {
            // q.size() courses in 1 semester
            int thisSemesterCourses = q.size();
            for(int thisSemester = 0; thisSemester < thisSemesterCourses; thisSemester++) {
                int course = q.front();
                q.pop();
                coursesTaken++;

                if(graph.find(course) != graph.end()) {
                    for(auto neighbor: graph[course]) {
                        inDegree[neighbor]--;
                        if(inDegree[neighbor] == 0)
                            q.push(neighbor);
                    }
                }
            }
            semesters++;
        }

        // Make sure all courses are taken
        if(coursesTaken != N)
            return -1;

        return semesters;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int minimumSemesters(int N, List<List<Integer>> relations) {
        // in_degree of N nodes, 1 indexed
        int[] inDegree = new int[N+1];
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for(List<Integer> relation: relations) {
            List<Integer> descendants = graph.getOrDefault(relation.get(0), new ArrayList<>());
            descendants.add(relation.get(1));
            graph.put(relation.get(0), descendants);
            inDegree[relation.get(1)]++;
        }

        // Collect all 0 in degree nodes
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i < N+1; i++)
            if(inDegree[i] == 0)
                queue.add(i);
        
        // Topological sort
        int semesters = 0;
        int coursesTaken = 0;
        while(!queue.isEmpty()) {
            // queue.size() courses in 1 semester
            int thisSemesterCourses = queue.size();
            for(int thisSemester = 0; thisSemester < thisSemesterCourses; thisSemester++) {
                int course = queue.remove();
                coursesTaken++;

                if(graph.containsKey(course)) {
                    for(int neighbor: graph.get(course)) {
                        inDegree[neighbor]--;
                        if(inDegree[neighbor] == 0)
                            queue.add(neighbor);
                    }
                }
            }
            semesters++;
        }

        // Make sure all courses are taken
        if(coursesTaken != N)
            return -1;

        return semesters;
    }
}