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.

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.

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.

Solution Implementation

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 using problem constraints.