How do you solve Course Schedule II?

Build an adjacency list mapping each course to its prerequisites. For each course, perform a DFS that returns False if a cycle is detected. Maintain two sets: one for visited nodes and one for nodes in the current recursion stack. Append courses to the output list after visiting all their prerequisites. If any DFS call detects a cycle, return an empty list. Otherwise, return the reversed output list as the valid course order.

What pattern does Course Schedule II use?

The Pattern: DFS (Cycle Detection and Topological Sort) The Heuristic: Use DFS with a recursion stack to detect cycles in a directed graph; append nodes to the output list only after all their dependencies are resolved, ensuring a valid topological order if no cycles exist.

Course Schedule II — DFS

Q: What is the time complexity of Course Schedule II?

O(V + E). Each course (vertex) and each prerequisite pair (edge) is visited once during DFS. Cycle detection and adjacency list traversal are linear in the size of the graph.

Problem

Given the number of courses and a list of prerequisite pairs, return a valid order in which to take all courses such that all prerequisites are satisfied, or return an empty list if no such order exists.

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

Example

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

Output: [0,2,1,3]

The algorithm builds a graph where each course points to its prerequisites. It performs a DFS on each course, tracking the recursion stack to detect cycles. For course 3, it recursively visits prerequisites 1 and 2, which themselves depend on 0. The DFS postorder appends courses after all their prerequisites are visited, resulting in a valid order such as [0,2,1,3]. If a cycle is detected, the function returns an empty list.

Approach

Straightforward Solution

A brute-force approach might try all permutations of courses and check if prerequisites are satisfied, which is factorial time and infeasible for large inputs.

Core Observation

The problem reduces to finding a topological ordering of a directed graph where nodes are courses and edges represent prerequisites. A valid ordering exists if and only if the graph is a Directed Acyclic Graph (DAG). Detecting cycles is essential to determine feasibility.

Path to Optimal

Preview

Recognizing the problem as topological sorting on a graph, the key insight is to use DFS with cycle detection. By tracking nodes currently in the recursion stack, the algorithm detects cycles efficiently…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build an adjacency list mapping each course to its prerequisites. For each course, perform a DFS that returns False if a cycle is detected…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(V + E)

Each course (vertex) and each prerequisite pair (edge) is visited once during DFS. Cycle detection and adjacency list traversal are linear in the size of the graph.

Space

O(V + E)

The adjacency list requires O(V + E) space. The recursion stack and visited sets require O(V) space. The output list stores all courses, also O(V).

Solution

Python

1class Solution:
  def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
      prereq = {c: [] for c in range(numCourses)}
      for crs, pre in prerequisites:
          prereq[crs].append(pre)
6
      output = []
      visit, cycle = set(), set()
      def dfs(crs):
          if crs in cycle:
              return False
          if crs in visit:
              return True
          
          cycle.add(crs)
          for pre in prereq[crs]:
              if not dfs(pre):
                  return False
          cycle.remove(crs)
          visit.add(crs)
          output.append(crs)
          return True
      
      for c in range(numCourses):
          if not dfs(c):
              return []
      return output

Step-by-Step Solution

1

Build Adjacency List Mapping Courses to Prerequisites

3prereq = {c: [] for c in range(numCourses)}
4for crs, pre in prerequisites:
5    prereq[crs].append(pre)

Objective

To represent the course prerequisites as a graph for efficient traversal.

Key Insight

Representing the problem as a graph is essential. Using a dictionary mapping each course to a list of its prerequisites allows quick access to dependencies during DFS. This structure supports efficient cycle detection and ordering.

Interview Quick-Check

Core Logic

The adjacency list stores for each course the list of courses that must be taken before it, enabling direct traversal of dependencies.

Common Pitfalls & Bugs

Confusing the direction of edges (course to prerequisite vs prerequisite to course) can lead to incorrect traversal and cycle detection.

2

Perform DFS with Cycle Detection to Validate and Order Courses

To recursively explore each course's prerequisites, detect cycles, and build a valid course order.

3

Iterate Over All Courses to Trigger DFS and Return Final Ordering

To ensure all courses are processed and to return the computed valid order or an empty list if impossible.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 7 Critical lines interviewers watch for.

Line 10 Critical

if crs in cycle:

Check if the current course is already in the recursion stack, indicating a cycle.

Detecting a node in the recursion stack signals a back edge and thus a cycle, which invalidates any course ordering.

Line 21 Critical

output.append(crs)

Append the current course to the output list after all prerequisites are processed.

Postorder appending guarantees that prerequisites appear before dependent courses in the final ordering.

Line 11 Critical

return False

Return False immediately upon cycle detection.

Aborting DFS on cycle detection prevents further exploration and signals that no valid ordering exists.

Full line-by-line criticality + rationale for all 21 lines available on Pro.

Test Your Understanding

Why is it necessary to track nodes currently in the recursion stack (the 'cycle' set) separately from the visited nodes?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Course Schedule II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Course Schedule II drill

or drill a free problem

1	`class Solution:`
2	`def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:`
3	`prereq = {c: [] for c in range(numCourses)}`
4	`for crs, pre in prerequisites:`
5	`prereq[crs].append(pre)`
6
7	`output = []`
8	`visit, cycle = set(), set()`
9	`def dfs(crs):`
10	`if crs in cycle:`
11	`return False`
12	`if crs in visit:`
13	`return True`
14
15	`cycle.add(crs)`
16	`for pre in prereq[crs]:`
17	`if not dfs(pre):`
18	`return False`
19	`cycle.remove(crs)`
20	`visit.add(crs)`
21	`output.append(crs)`
22	`return True`
23
24	`for c in range(numCourses):`
25	`if not dfs(c):`
26	`return []`
27	`return output`