210. Course Schedule II


Problem Description

In this problem, you are tasked with finding an order in which you can take a set number of courses such that for every course you are taking, you have already completed all its prerequisites. You are given two inputs:

  • numCourses which is an integer representing the total number of courses you need to take, numbered from 0 to numCourses - 1.
  • prerequisites which is a list of pairs [a_i, b_i], where a_i is a course that you want to take and b_i is the course that must be taken before a_i.

Your objective is to return a list representing the order in which you can take the courses. If there are multiple correct orders, any one of them is a valid answer. If it's impossible to complete all the courses (for example, because of a cycle in the prerequisite structure), you should return an empty list.

This problem can be thought of as a graph problem where each course is a node in the graph, and the prerequisites are directed edges between nodes. The task is to find a topological sort of this graph, which is an ordering of its nodes such that for every directed edge u → v, node u comes before node v in the ordering.

Intuition

The solution to this problem involves using a graph data structure to represent the prerequisite courses relationship and then performing a topological sort on this graph. The key steps to solve this problem are as follows:

  1. Create a graph representation.

    • Each course is represented as a node.
    • A directed edge from node b_i to node a_i is added for each prerequisite pair [a_i, b_i]. This indicates that course b_i is a prerequisite for course a_i.
  2. Determine the in-degree for each node.

    • The in-degree of a node is the number of edges coming into it. In this scenario, it represents the number of prerequisites for a course.
  3. Initiate a queue and add all nodes with an in-degree of 0 to it.

    • These are the courses that don't have any prerequisites, which can be taken first.
  4. While the queue is not empty, process the nodes:

    • Dequeue a node (a course with no prerequisites) and add it to the solution list, indicating the course can be taken.
    • For each neighbor (course that has the just-taken course as prerequisite), decrement its in-degree (since one of its prerequisites has been taken).
    • If a neighbor's in-degree becomes 0, enqueue it. This signifies that all its prerequisites are met, and it can be taken.
  5. Check if the number of courses taken matches the total number of courses.

    • If they match, return the solution list as a valid order.
    • If they do not match, a cycle must exist in the graph, and thus it is impossible to complete all courses. Return an empty list.

Using this strategy, the given implementation builds the graph using a hashmap (g) for adjacency lists and an array (indeg) for in-degree counts. It then uses a queue (q) to identify courses with no prerequisites and processes them to uncover an acceptable course order (ans), which is returned as the solution.

Learn more about Depth-First Search, Breadth-First Search, Graph and Topological Sort patterns.

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

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Solution Approach

The solution approach for finding the course order takes advantage of several concepts in computer science, such as graph theory, topological sorting, and queue-based breadth-first search (BFS). Here's a detailed breakdown of the implementation steps:

  1. Graph Representation: The code begins by using a defaultdict(list) to represent the graph g. The graph stores key-value pairs where each key is a course with prerequisites (b_i), and the associated value is a list of all courses (a_i) that require it as a prerequisite. This graph is directional—the presence of an edge from b to a means you must take course b before course a.

  2. In-Degree Calculation: The number of prerequisites (indeg) for each course is stored in a list where the index corresponds to the course number and the value at each index is the count of how many prerequisites it has. This list is populated by iterating over each pair in the prerequisites and incrementing the in-degree for the course a_i.

  3. Queue Initialization: q is instantiated as a deque, which is a double-ended queue supporting efficient insertions and deletions from both ends. The initialization loops through the indeg array, adding the index (course number) to q only if that course has an in-degree of 0, which means it doesn't depend on any other courses and can be taken immediately.

  4. Processing Nodes with a Queue (BFS): A while loop runs as long as q is not empty. Inside the loop:

    • The course at the front of the queue is dequeued with popleft(), signifying that this course is now being taken, and it's appended to the ans list.

    • A for loop then iterates over each course j that depends on the recently taken course i. For each of those, the in-degree is decremented since one of their prerequisites has been fulfilled by completing course i.

    • After decreasing the in-degree, if any course's in-degree reaches 0, it means all its prerequisites have been taken, and therefore it is enqueued into q for future processing.

  5. Checking for Valid Solution: After processing, if the length of the ans array is equal to numCourses, all courses have been ordered and taken, indicating that there was a possible way to finish all courses. In this case, ans is returned.

    If not all courses are taken, meaning len(ans) is not equal to numCourses, the code concludes there is a cycle, and it's impossible to take all the courses. To reflect this, an empty list [] is returned, denoting no valid ordering exists.

This algorithm essentially performs a topological sort using BFS and the concept of in-degree to find a valid linear ordering of the courses. If such an ordering is not possible, it correctly identifies this by checking the result against the total number of courses.

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

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's go through an example to illustrate the solution approach.

Suppose we have 4 courses to complete, with numCourses equal to 4, and our list of prerequisites is given as [[1,0],[2,0],[3,1],[3,2]]. This means that:

  • To take course 1, you must first complete course 0.
  • To take course 2, you must first complete course 0.
  • To take course 3, you must first complete courses 1 and 2.

Following the solution approach:

  1. Graph Representation: We create a graph where:

    • 0 has no outgoing edges (since no course requires 0 as a prerequisite), so it's not a key in the graph.
    • 1 has a single outgoing edge to course 0.
    • 2 has a single outgoing edge to course 0.
    • 3 has outgoing edges to courses 1 and 2.

    The graph (g) will be: {1: [0], 2: [0], 3: [1, 2]}

  2. In-Degree Calculation: We determine the in-degree counts as follows:

    • Course 0 has an in-degree of 0 (it's not a prerequisite for any course).
    • Course 1 has an in-degree of 1 (course 3 depends on it).
    • Course 2 has an in-degree of 1 (course 3 depends on it).
    • Course 3 has an in-degree of 2 (courses 1 and 2 must be taken before it).

    The indeg array will be: [0, 1, 1, 2]

  3. Queue Initialization: We initiate a queue (q) and add courses with an in-degree of 0. In this case, we add course 0.

  4. Processing Nodes with a Queue (BFS): We start processing the queue. Since course 0 is in q and has no prerequisites, we dequeue it, take it (add to the ans), and then look at its neighbors:

    • Course 1 and 2 are considered neighbors (since their prerequisites include course 0), so we decrement their in-degree by 1. Now both courses 1 and 2 have an in-degree of 0, so they are added to the queue.

    • Next, we process course 1, decrement the in-degree of course 3 (its neighbor) to 1, and add course 1 to ans.

    • Similarly, we process course 2, decrement the in-degree of course 3 to 0 (now that both its prerequisites are taken), and add course 2 to ans.

    • Finally, we process course 3 (its in-degree is now 0), and add it to ans.

  5. Checking for Valid Solution: By the end of the process, we have the order in which the courses were taken as [0, 1, 2, 3] and this matches numCourses. Therefore, we successfully found a valid order and no cycle was detected.

Our output for the given problem is [0, 1, 2, 3], which represents a valid ordering in which we can take all the courses satisfying the prerequisites.

Not Sure What to Study? Take the 2-min Quiz:

Which technique can we use to find the middle of a linked list?

Python Solution

1from collections import defaultdict, deque
2from typing import List
3
4class Solution:
5    def findOrder(self, num_courses: int, prerequisites: List[List[int]]) -> List[int]:
6        # Initialize a graph using a dictionary to map each course to its list of dependent courses
7        graph = defaultdict(list)
8      
9        # Initialize a list to count incoming edges (prerequisites) for each course
10        incoming_edges_count = [0] * num_courses
11      
12        # Build the graph and update the count of incoming edges for each course
13        for course, prerequisite in prerequisites:
14            graph[prerequisite].append(course)
15            incoming_edges_count[course] += 1
16      
17        # List to store the course order
18        course_order = []
19      
20        # Queue to manage the courses with no incoming edges (no prerequisites)
21        queue = deque(course for course, count in enumerate(incoming_edges_count) if count == 0)
22      
23        # Process the courses using a topological sort via BFS (Breadth-First Search)
24        while queue:
25            current_course = queue.popleft()
26            course_order.append(current_course) # add the current course to the course order
27          
28            # Reduce the incoming edge count of dependent courses by 1
29            for dependent_course in graph[current_course]:
30                incoming_edges_count[dependent_course] -= 1
31              
32                # If a dependent course now has no incoming edges, add it to the queue
33                if incoming_edges_count[dependent_course] == 0:
34                    queue.append(dependent_course)
35      
36        # Check if the number of courses in the order list matches the total number of courses
37        # If not, it means not all courses can be completed (cycle detected)
38        return course_order if len(course_order) == num_courses else []
39

Java Solution

1class Solution {
2    public int[] findOrder(int numCourses, int[][] prerequisites) {
3        // Create an adjacency list to represent the graph of courses
4        List<Integer>[] graph = new List[numCourses];
5        Arrays.setAll(graph, x -> new ArrayList<>());
6      
7        // Create an array to keep track of the number of incoming edges (in-degrees) to each node (course)
8        int[] inDegree = new int[numCourses];
9      
10        // Build the graph and update in-degree count
11        for (int[] prerequisite : prerequisites) {
12            int course = prerequisite[0];
13            int prerequisiteCourse = prerequisite[1];
14            graph[prerequisiteCourse].add(course);
15            ++inDegree[course];
16        }
17      
18        // Queue for courses with no prerequisites (in-degree of 0)
19        Deque<Integer> queue = new ArrayDeque<>();
20      
21        // Add all courses with no incoming edges to the queue
22        for (int i = 0; i < numCourses; ++i) {
23            if (inDegree[i] == 0) {
24                queue.offer(i);
25            }
26        }
27      
28        // Array for storing the course ordering
29        int[] order = new int[numCourses];
30        int courseCount = 0;
31      
32        // Perform BFS on the graph
33        while (!queue.isEmpty()) {
34            int currentCourse = queue.poll();
35            order[courseCount++] = currentCourse;
36          
37            // Go through all the adjacent courses and reduce their in-degrees
38            for (int adjacentCourse : graph[currentCourse]) {
39                if (--inDegree[adjacentCourse] == 0) {
40                    // If in-degree becomes 0, add it to the queue
41                    queue.offer(adjacentCourse);
42                }
43            }
44        }
45      
46        // If we have added all courses in order, return the order. 
47        // Otherwise, there is a cycle and we return an empty array.
48        return courseCount == numCourses ? order : new int[0];
49    }
50}
51

C++ Solution

1#include <vector>
2#include <queue>
3
4class Solution {
5public:
6    // Function to find the order of courses you should take to finish all courses.
7    std::vector<int> findOrder(int numCourses, std::vector<std::vector<int>>& prerequisites) {
8        // Adjacency list representation of graph
9        std::vector<std::vector<int>> graph(numCourses);
10        // Vector to store the number of incoming edges for each node
11        std::vector<int> inDegree(numCourses, 0);
12
13        // Build the graph and fill inDegree data
14        for (const auto& pre : prerequisites) {
15            int course = pre[0];
16            int prerequisiteCourse = pre[1];
17            graph[prerequisiteCourse].push_back(course); // Edge from prereq to course
18            ++inDegree[course]; // Increase in-degree of course
19        }
20
21        // Queue for BFS
22        std::queue<int> queue;
23
24        // Enqueue all courses that don't require prerequisites
25        for (int i = 0; i < numCourses; ++i) {
26            if (inDegree[i] == 0) {
27                queue.push(i);
28            }
29        }
30
31        // Vector to store the order of courses to take
32        std::vector<int> order;
33
34        // Process nodes with no incoming edges
35        while (!queue.empty()) {
36            int currentCourse = queue.front();
37            queue.pop();
38            order.push_back(currentCourse);
39
40            // For each course that comes after the current course
41            for (int nextCourse : graph[currentCourse]) {
42                // Decrease the in-degree and if it becomes zero, add it to the queue.
43                if (--inDegree[nextCourse] == 0) {
44                    queue.push(nextCourse);
45                }
46            }
47        }
48
49        // If we were able to include all courses in the order list, return it,
50        // otherwise, the prerequisites form a cycle and we cannot complete all courses.
51        if (order.size() == numCourses) {
52            return order;
53        } else {
54            return std::vector<int>(); // empty vector, signaling it's not possible to finish all courses
55        }
56    }
57};
58

Typescript Solution

1function findCourseOrder(numCourses: number, prerequisites: number[][]): number[] {
2    // Create an adjacency list to represent the graph
3    const graph: number[][] = Array.from({ length: numCourses }, () => []);
4    // Initialize an array to store indegrees of each course
5    const indegrees: number[] = new Array(numCourses).fill(0);
6  
7    // Build the graph and update indegrees
8    for (const [course, prereq] of prerequisites) {
9        graph[prereq].push(course);
10        indegrees[course]++;
11    }
12  
13    // Initialize a queue to keep track of courses with no prerequisites
14    const queue: number[] = [];
15    // Find all the courses with indegree of 0 and add them to the queue
16    for (let i = 0; i < numCourses; i++) {
17        if (indegrees[i] === 0) {
18            queue.push(i);
19        }
20    }
21  
22    // Initialize an array to store the order of courses
23    const courseOrder: number[] = [];
24    // Process the queue until it is empty
25    while (queue.length > 0) {
26        // Dequeue an element
27        const current = queue.shift()!;
28        // This course can now be taken, so add it to courseOrder
29        courseOrder.push(current);
30      
31        // For each course that depends on the current course
32        for (const dependentCourse of graph[current]) {
33            // Decrease the indegree of the dependent course
34            indegrees[dependentCourse]--;
35            // If the indegree is 0, it means it has no more prerequisites, add it to the queue
36            if (indegrees[dependentCourse] === 0) {
37                queue.push(dependentCourse);
38            }
39        }
40    }
41  
42    // If all courses are in the order, return the courseOrder, otherwise, return an empty array
43    return courseOrder.length === numCourses ? courseOrder : [];
44}
45
Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the minimum element can be found in:

Time and Space Complexity

The given code implements a topological sort using Kahn's Algorithm to find an order in which courses can be taken given their prerequisites.

Time Complexity:

The time complexity of the code is primarily determined by the number of courses (numCourses) and the number of prerequisites (len(prerequisites)).

  1. Building the graph and the in-degree list (where indeg keeps the count of dependencies for each course) iterates over all prerequisites once, which is O(E) where E is the number of edges or prerequisites in this case.
  2. The queue (q) at most contains all courses without dependencies at once. The while loop dequeues each course once and enqueues courses that become free of dependencies. Each edge in the graph is considered once when reducing the in-degree count for dependent courses. The overall process of continuously adding and removing from the queue and updating the in-degree of dependent courses is O(V+E) where V is the number of vertices or courses, and E is the number of edges or prerequisites.

Therefore, the total time complexity is O(V+E), where V is numCourses and E is len(prerequisites).

Space Complexity:

The space complexity is determined by the space needed to store the graph, the in-degree list, the queue, and the final answer list.

  1. The graph (g) will hold at most all prerequisites, which is O(E).
  2. The in-degree list (indeg) holds an entry for each course, taking O(V).
  3. The queue (q) can at most hold all vertices with zero in-degree at once, in the worst case O(V).
  4. The answer list (ans) also takes O(V) since it contains all courses in the topological order.

As all these structures are needed simultaneously, we add them together to get the space complexity. Thus, the total space complexity is O(V+E), where V is numCourses and E is len(prerequisites).

Learn more about how to find time and space complexity quickly.


Recommended Readings


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 👨‍🏫