1136. Parallel Courses
Problem Description
The problem presents a scenario where you have n
courses numbered from 1
to n
. You are also given a list of pairs, relations
, representing the prerequisite relationships between the courses. Each pair [prevCourse, nextCourse]
indicates that prevCourse
must be completed before nextCourse
can be taken.
The goal is to determine the minimum number of semesters required to complete all n
courses, given that you can take any number of courses in a single semester, but you must have completed their prerequisites in the previous semester. If it's not possible to complete all courses due to a circular dependency or any other reason, the result should be -1
.
Intuition
To solve this problem efficiently, we use a graph-based approach known as Topological Sorting, which is usually applied to scheduling tasks or finding a valid order in which to perform tasks with dependencies.
Here's a step-by-step breakdown of the intuition behind the solution:
-
We consider each course as a node in a directed graph where an edge from node
prevCourse
to nodenextCourse
indicates thatprevCourse
is a prerequisite fornextCourse
. -
We construct an in-degree list to track the number of prerequisite courses for each course. A course with an in-degree of
0
means it has no prerequisite and can be taken immediately. -
We then use a queue to keep track of all courses that have no prerequisites (in-degree of
0
). This set represents the courses we can take in the current semester. -
For each semester, we dequeue all available courses (i.e., those with no prerequisites remaining) and decrease the in-degree of their corresponding next courses by 1, representing that we have taken one of their prerequisites.
-
If the in-degree of these next courses drops to
0
, it means they have no other prerequisites left, so we add them to the queue to be available for the next semester. -
We continue this process, semester by semester, keeping a counter to track the number of semesters necessary until there are no courses left to take.
-
If at the end of this process, there are still courses left (i.e.,
n
is not zero), it implies that there is a cycle or unsatisfiable dependency, and we return-1
. Otherwise, we return the counter, which now holds the minimum number of semesters needed to take all courses.
Learn more about Graph and Topological Sort patterns.
Solution Approach
The implementation follows the topological sorting approach using the Kahn's algorithm pattern. Here's how the algorithm unfolds:
-
Graph Representation: The graph is represented using an adjacency list,
g
, which maps each course to a list of courses that depend on it (i.e., the courses that have it as a prerequisite). Additionally, an in-degree list,indeg
, is maintained to keep track of the number of prerequisites for each course. -
Initialization: An initial scan of the
relations
array is performed to populate the adjacency list and in-degree list. Each relation[prev, next]
increments the in-degree of thenext
course to indicate an additional prerequisite. -
Queue of Available Courses: A queue,
q
, is initialized with all the courses that have an in-degree of0
. These are the courses that can be taken in the first semester as they have no prerequisites. -
Iterating Over Semesters: We use a while loop to simulate passing semesters. In each iteration, we process all courses in the queue:
- Increment the
ans
variable, which represents the number of semesters. - For each course taken (dequeued), decrement
n
to reflect that one course has been completed. - Update the in-degree of all "child" courses (i.e., courses that the current course is a prerequisite for) by decrementing their respective in-degree count.
- If any "child" course's in-degree becomes
0
, enqueue it, meaning it can be taken in the next semester.
- Increment the
-
Detecting Cycles or Infeasible Conditions: After processing all possible courses, if the
n
counter is not zero, it suggests that not all courses can be taken due to cycles (circular prerequisites) or other unsolvable dependencies. In such a case, we return-1
. -
Returning the Result: If the loop completes successfully and
n
is zero, theans
variable contains the minimum number of semesters needed to take all courses, which is then returned.
The data structures employed in this solution are:
- A
defaultdict
for constructing the adjacency list graph representation. - A list to maintain in-degree counts.
- A
deque
to efficiently add and remove available courses as we iterate over semesters.
The algorithms and patterns used are part of graph theory and include:
- Topological sorting to determine a valid order to take the courses.
- Kahn's algorithm for detecting cycles and performing the sort iteratively by removing nodes with zero in-degree.
Throughout the process, we maintain a balance between the courses taken and the updates to the graph's state, ensuring that courses are only considered available once all their prerequisites have been fulfilled.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Suppose we have n = 4
courses and the relations
list as [[1,2], [2,3], [3,4]]
. According to this list, you must complete course 1 before taking course 2, course 2 before course 3, and course 3 before course 4.
Using the approach described above, let's proceed step by step:
-
Graph Representation: We construct a graph such that
g = {1: [2], 2: [3], 3: [4]}
, and the in-degree listindeg = [0, 1, 1, 1]
(since the numbering starts at 1, you might need to adjust the indices accordingly). -
Initialization: We perform an initial scan and find that course 1 has no prerequisites (
in-degree = 0
), so it can be taken immediately. -
Queue of Available Courses: We initialize a queue
q
with course 1 in it, ready to be taken in the first semester. -
Iterating Over Semesters:
- First Semester: We dequeue course 1 and decrement
n
to 3 (as we have one less course to complete). We then decrease the in-degree of course 2 to 0 and enqueue it for the next semester. - Second Semester: We dequeue course 2 from
q
and decrementn
to 2. We update the in-degree of course 3 to 0 and enqueue it for the next semester. - Third Semester: Course 3 is dequeued,
n
is decremented to 1, the in-degree of course 4 is now 0, and it gets enqueued for the next semester. - Fourth Semester: Finally, we dequeue course 4, and
n
is now 0, which means all courses have been accounted for.
- First Semester: We dequeue course 1 and decrement
-
Detecting Cycles or Infeasible Conditions: Through our iterations, we didn't encounter any cycles, and all indegree counts could be reduced to 0 properly, indicating that we can plan courses without conflict.
-
Returning the Result: We've successfully queued and completed all courses, one per semester. Therefore, the minimum number of semesters required is 4, which is the value of our counter after the last course is taken.
The result is 4
semesters to complete the given courses following the pre-defined prerequisites-order.
Solution Implementation
1from collections import defaultdict, deque
2from typing import List
3
4class Solution:
5 def minimumSemesters(self, total_courses: int, prerequisites: List[List[int]]) -> int:
6 # Create a default dictionary to hold the adjacency list representation of the graph
7 graph = defaultdict(list)
8 # Initialize a list for incoming degree count of each node
9 incoming_degree = [0] * total_courses
10
11 # Populate the graph and update the incoming degree counts
12 for prereq, course in prerequisites:
13 # Adjust indices to be 0-based instead of 1-based
14 prereq -= 1
15 course -= 1
16 graph[prereq].append(course)
17 incoming_degree[course] += 1
18
19 # Initialize a queue with all courses having 0 incoming degree
20 queue = deque([i for i, degree in enumerate(incoming_degree) if degree == 0])
21 # Initialize a variable to count the number of semesters
22 semesters = 0
23
24 # Process nodes level by level (BFS)
25 while queue:
26 # Increment the semester count
27 semesters += 1
28 # Process all nodes in the current level
29 for _ in range(len(queue)):
30 course = queue.popleft()
31 total_courses -= 1 # Decrement the number of courses remaining
32 # Decrease the incoming degree of all adjacent courses
33 for next_course in graph[course]:
34 incoming_degree[next_course] -= 1
35 # If adjacent course has no more prerequisites, add it to the queue
36 if incoming_degree[next_course] == 0:
37 queue.append(next_course)
38
39 # If all courses are covered, return the number of semesters
40 # If there are still courses remaining with nonzero incoming degree,
41 # it means there's a cycle, and we return -1 to indicate it's not possible to finish
42 return semesters if total_courses == 0 else -1
43
1class Solution {
2 public int minimumSemesters(int n, int[][] relations) {
3 // Create an adjacency list to represent the graph structure.
4 List<Integer>[] graph = new List[n];
5 // Initialize each list within 'graph'.
6 Arrays.setAll(graph, k -> new ArrayList<>());
7 // Array to keep track of in-degrees (number of prerequisites).
8 int[] indegree = new int[n];
9
10 // Build the graph and count the in-degrees for each course.
11 for (int[] relation : relations) {
12 int prevCourse = relation[0] - 1; // Convert to 0-based index.
13 int nextCourse = relation[1] - 1; // Convert to 0-based index.
14 graph[prevCourse].add(nextCourse);
15 indegree[nextCourse]++;
16 }
17
18 // Queue to store courses with no prerequisites (in-degree of 0).
19 Deque<Integer> queue = new ArrayDeque<>();
20 // Enqueue all courses with no prerequisites.
21 for (int i = 0; i < n; ++i) {
22 if (indegree[i] == 0) {
23 queue.offer(i);
24 }
25 }
26
27 // Variable to keep count of the minimum number of semesters.
28 int semesters = 0;
29 // Perform BFS to process courses.
30 while (!queue.isEmpty()) {
31 semesters++; // Increase semester count.
32 // Process courses in the current semester.
33 for (int k = queue.size(); k > 0; --k) {
34 // Dequeue the front course.
35 int course = queue.poll();
36 n--; // Decrease the count of the remaining courses.
37 // Decrease in-degree for the subsequent courses and check if they become ready to take.
38 for (int nextCourse : graph[course]) {
39 if (--indegree[nextCourse] == 0) {
40 queue.offer(nextCourse);
41 }
42 }
43 }
44 }
45
46 // If there are no more courses to take, return semesters, otherwise return -1 to indicate the graph is not acyclic.
47 return n == 0 ? semesters : -1;
48 }
49}
50
1class Solution {
2public:
3 int minimumSemesters(int N, vector<vector<int>>& relations) {
4 // Graph representation where each node points to its successors
5 vector<vector<int>> graph(N);
6
7 // In-degree array to keep track of the number of prerequisites for each course
8 vector<int> inDegree(N);
9
10 // Build the graph and fill in the in-degree array
11 for (auto& relation : relations) {
12 int prevCourse = relation[0] - 1; // Convert to 0-indexed
13 int nextCourse = relation[1] - 1; // Convert to 0-indexed
14
15 // Add edge from prevCourse to nextCourse
16 graph[prevCourse].push_back(nextCourse);
17
18 // Increment the in-degree of the nextCourse
19 ++inDegree[nextCourse];
20 }
21
22 // Queue to perform topological sorting
23 queue<int> queue;
24
25 // Enqueue all the courses that have no prerequisites (in-degree of 0)
26 for (int i = 0; i < N; ++i) {
27 if (inDegree[i] == 0) {
28 queue.push(i);
29 }
30 }
31
32 int semesters = 0; // Number of semesters needed to complete all the courses
33
34 // Perform the topological sort using BFS
35 while (!queue.empty()) {
36 // Increment the semester count as all the nodes in the queue can be taken in the current semester
37 ++semesters;
38
39 // Process all nodes in the current level of the queue
40 for (int levelSize = queue.size(); levelSize > 0; --levelSize) {
41 int course = queue.front();
42 queue.pop();
43 --N; // One less course to consider
44
45 // Check all the next courses that current course points to
46 for (int nextCourse : graph[course]) {
47 // Decrement the in-degree and if it drops to 0, add it to the queue
48 if (--inDegree[nextCourse] == 0) {
49 queue.push(nextCourse);
50 }
51 }
52 }
53 }
54
55 // If all courses are processed, we return the number of semesters, otherwise it's impossible (-1)
56 return N == 0 ? semesters : -1;
57 }
58};
59
1function minimumSemesters(totalCourses: number, prerequisitePairs: number[][]): number {
2 // Create an adjacency list to represent the course graph, initialized with empty arrays
3 const courseGraph = Array.from({ length: totalCourses }, () => []);
4
5 // Initialize an array to keep track of how many prerequisites each course has
6 const inDegree = new Array(totalCourses).fill(0);
7
8 // Build the graph and fill in the inDegree array by iterating over the prerequisitePairs
9 for (const [prerequisite, course] of prerequisitePairs) {
10 courseGraph[prerequisite - 1].push(course - 1);
11 inDegree[course - 1]++;
12 }
13
14 // Queue for courses that have no prerequisites, hence can be taken
15 const queue: number[] = [];
16
17 // Find the initial courses with no prerequisites and add them to the queue
18 for (let index = 0; index < totalCourses; ++index) {
19 if (inDegree[index] === 0) {
20 queue.push(index);
21 }
22 }
23
24 // "ans" will keep track of the total number of semesters required
25 let semesters = 0;
26
27 // Perform a breadth-first search (BFS) on the course graph
28 while (queue.length > 0) {
29 semesters++; // Start a new semester
30 // Process all courses that are available to be taken in this semester
31 for (let count = queue.length; count > 0; --count) {
32 const currentCourse = queue.shift(); // Take the course (remove from queue)
33 --totalCourses; // Decrement the count of courses remaining to be taken
34 for (const nextCourse of courseGraph[currentCourse]) {
35 // Decrement the in-degree of the adjacent courses
36 if (--inDegree[nextCourse] === 0) {
37 queue.push(nextCourse); // If no more prerequisites, add to the queue
38 }
39 }
40 }
41 }
42
43 // If all courses have been taken, return the total number of semesters needed, otherwise return -1
44 return totalCourses === 0 ? semesters : -1;
45}
46
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be analyzed step by step:
-
Creating the graph
g
and the indegree arrayindeg
: This involves iterating over each relation once. If there areE
relations, this operation has a complexity ofO(E)
. -
Building the initial queue
q
with vertices of indegree 0: This involves a single scan through theindeg
array ofn
elements, which gives a complexity ofO(n)
. -
The while loop to reduce the indegrees and find the order of courses: Within the loop, each vertex is processed exactly once, as it gets removed from the queue, and each edge is considered exactly once, as it gets decremented when the previous vertex is processed. So, the complexity related to processing all vertices and edges is
O(V + E)
, whereV
is the number of vertices andE
is the number of edges.
Thus, the overall time complexity is O(E) + O(n) + O(V + E)
. Since V = n
, we can simplify this to O(n + E)
.
Space Complexity
The space complexity of the code:
-
The graph
g
has a space complexity ofO(E)
, as it stores all the edges. -
The indegree array
indeg
has a space complexity ofO(n)
as it stores an entry for each vertex. -
The queue
q
could potentially store alln
vertices in the worst case, which gives a space complexity ofO(n)
.
As such, the overall space complexity is the sum of the complexities of g
, indeg
, and q
, which gives O(E + n)
. Note that even though E
could be as large as n * (n-1)
in a dense graph, we do not multiply by n
in the space complexity as we consider distinct elements within the data structure.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.