1136. Parallel Courses

MediumGraphTopological Sort
Leetcode Link

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:

  1. We consider each course as a node in a directed graph where an edge from node prevCourse to node nextCourse indicates that prevCourse is a prerequisite for nextCourse.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

Solution Approach

The implementation follows the topological sorting approach using the Kahn's algorithm pattern. Here's how the algorithm unfolds:

  1. 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.

  2. 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 the next course to indicate an additional prerequisite.

  3. Queue of Available Courses: A queue, q, is initialized with all the courses that have an in-degree of 0. These are the courses that can be taken in the first semester as they have no prerequisites.

  4. 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.

  5. 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.

  6. Returning the Result: If the loop completes successfully and n is zero, the ans 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Example 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 list indeg = [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 decrement n 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.

  • 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
Not Sure What to Study? Take the 2-min Quiz：

Which type of traversal does breadth first search do?

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be analyzed step by step:

  1. Creating the graph g and the indegree array indeg: This involves iterating over each relation once. If there are E relations, this operation has a complexity of O(E).

  2. Building the initial queue q with vertices of indegree 0: This involves a single scan through the indeg array of n elements, which gives a complexity of O(n).

  3. 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), where V is the number of vertices and E 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:

  1. The graph g has a space complexity of O(E), as it stores all the edges.

  2. The indegree array indeg has a space complexity of O(n) as it stores an entry for each vertex.

  3. The queue q could potentially store all n vertices in the worst case, which gives a space complexity of O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Graph Fundamentals

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 Introduction

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫