#210

Medium

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Course Schedule II

Solve the 'Course Schedule II' problem using graph indegree and topological ordering, utilizing DFS or BFS to find the correct course order.

depth first search breadth first search graph topological sort

Problem Statement

You have to take a series of courses, each labeled from 0 to numCourses - 1. The courses come with certain prerequisites, represented as an array, where prerequisites[i] = [ai, bi], meaning you must complete course bi before course ai. Your goal is to return a possible order of courses you can take to complete all courses.

If there are multiple valid orders, return any of them. However, if there is a cycle or no valid ordering due to conflicting prerequisites, return an empty array. The problem boils down to finding a valid topological order in a directed graph formed by the prerequisites.

Examples

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]

Output: [0,1]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output: [0,2,1,3]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3

Input: numCourses = 1, prerequisites = []

Output: [0]

Example details omitted.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
All the pairs [ai, bi] are distinct.

Solution Approach

Topological Sort using DFS

Use Depth-First Search (DFS) to explore the graph of courses. Track the courses in the current path to detect cycles, which would indicate an impossible schedule. If no cycle is detected, add the course to the topological order in reverse postorder traversal.

Topological Sort using BFS (Kahn's Algorithm)

An alternative approach is to use Breadth-First Search with Kahn's algorithm. Compute the in-degree for each course, then progressively add courses with no prerequisites (in-degree of 0) to the schedule. Continue until all courses are added or a cycle is detected.

Cycle Detection

Cycle detection is integral in this problem. If, after processing, some courses have non-zero in-degrees, it means a cycle exists, and no valid ordering is possible. In such cases, return an empty array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Both DFS and BFS solutions have a time complexity of O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges). The space complexity is also O(V + E) to store the graph and auxiliary data structures used for traversal and in-degree calculation.

What Interviewers Usually Probe

Understanding of graph traversal methods like DFS and BFS.
Ability to detect cycles in a directed graph.
Knowledge of topological sorting and its application in real-world scheduling problems.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check for cycles in the graph, which can lead to incorrect results.
Not handling the case where there are no prerequisites (empty prerequisite list).
Incorrectly assuming there is always one valid topological order, when multiple orders are possible.

Follow-up variants

Course Schedule III, where you are given a limited number of semesters to complete the courses.
Course Schedule IV, where some courses are optional, and you're tasked with finding the minimum set of courses to complete all prerequisites.
Course Schedule V, where the graph may contain additional constraints such as course dependencies that vary over time.

FAQ

How do I solve the 'Course Schedule II' problem using topological sort?

To solve 'Course Schedule II', use topological sorting with either DFS or BFS. The goal is to find a valid course order by detecting cycles in the graph.

Can I use DFS or BFS for solving 'Course Schedule II'?

Yes, both DFS and BFS are viable approaches. DFS allows for cycle detection via recursive calls, while BFS (Kahn's Algorithm) handles cycle detection using in-degree tracking.

What happens if there is no valid course order in 'Course Schedule II'?

If a cycle exists in the graph, no valid topological order exists. In such cases, you should return an empty array.

How do I handle a case where there are no prerequisites in 'Course Schedule II'?

If there are no prerequisites, the order is trivial, and you can return any order of courses, such as [0, 1, 2, ..., numCourses-1].

What is the time complexity for solving 'Course Schedule II'?

The time complexity for both DFS and BFS approaches is O(V + E), where V is the number of courses and E is the number of prerequisites.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        g = defaultdict(list)
        indeg = [0] * numCourses
        for a, b in prerequisites:
            g[b].append(a)
            indeg[a] += 1
        ans = []
        q = deque(i for i, x in enumerate(indeg) if x == 0)
        while q:
            i = q.popleft()
            ans.append(i)
            for j in g[i]:
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
        return ans if len(ans) == numCourses else []

Continue Practicing

#207 course schedule #310 minimum height trees #329 longest increasing path in a matrix