Course Schedule II

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

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.

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

Medium DFS

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

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. The postorder traversal of DFS naturally produces a valid topological order when no cycles exist.

Optimal Approach

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.

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

Pattern Spotlight

DFS (Cycle Detection and Topological Sort)

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.

Solution

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

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.

Perform DFS with Cycle Detection to Validate and Order Courses

8visit, cycle = set(), set()
9def 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

Objective

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

Key Insight

DFS explores dependencies deeply, and tracking nodes in the current recursion stack detects cycles by identifying back edges. Adding a course to the output only after all its prerequisites are processed ensures the output respects prerequisite ordering. This postorder traversal naturally produces a valid topological sort if no cycles exist.

Interview Quick-Check

Core Logic

DFS uses two sets: one to track visited nodes to avoid redundant work, and one to track the recursion stack to detect cycles. The postorder appending ensures prerequisites come before dependent courses.

State & Boundaries

Return False immediately upon detecting a cycle to abort further exploration and signal no valid ordering.

Common Pitfalls & Bugs

Failing to remove nodes from the recursion stack after exploration leads to false cycle detection or infinite recursion.

Iterate Over All Courses to Trigger DFS and Return Final Ordering

24for c in range(numCourses):
25    if not dfs(c):
26        return []
27return output

Objective

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

Key Insight

Since the graph may be disconnected, DFS must be initiated from every course. If any DFS call detects a cycle, the function returns an empty list immediately. Otherwise, the accumulated output list contains a valid order of courses respecting all prerequisites.

Interview Quick-Check

Core Logic

Iterating over all courses guarantees that disconnected components are processed, ensuring a complete topological ordering.

State & Boundaries

Returning an empty list upon cycle detection signals no valid course order exists.

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.

Line 15 Critical

cycle.add(crs)

Add the current course to the recursion stack to track the current path.

Marking the node as in the current path is essential for detecting cycles during DFS traversal.

Line 18 Critical

return False

Return False if any prerequisite DFS call detects a cycle.

Propagating cycle detection upwards aborts the entire ordering process as no valid solution exists.

Line 19 Critical

cycle.remove(crs)

Remove the current course from the recursion stack after exploring all prerequisites.

Removing the node from the current path is critical to avoid false cycle detection in other DFS branches.

Line 26 Critical

return []

Return an empty list immediately if a cycle is detected.

No valid course order exists if any cycle is found, so the function must terminate early.

Line 5 Core

prereq[crs].append(pre)

Append the prerequisite course to the current course's adjacency list.

This correctly models the dependency that the current course depends on the prerequisite, establishing the directed edge.

Line 8 Core

visit, cycle = set(), set()

Initialize sets to track visited courses and the recursion stack for cycle detection.

The visited set prevents redundant DFS calls, while the recursion stack set detects cycles by tracking the current path of exploration.

Line 12 Core

if crs in visit:

Check if the current course has already been visited and processed.

Avoiding reprocessing visited nodes improves efficiency and prevents infinite recursion.

Line 17 Core

if not dfs(pre):

Recursively perform DFS on each prerequisite.

Deep exploration of dependencies is necessary to detect cycles and build a valid ordering.

Line 20 Core

visit.add(crs)

Mark the current course as visited to avoid reprocessing.

This memoization step ensures each course is processed once, improving efficiency.

Line 25 Core

if not dfs(c):

Invoke DFS on each course and check for cycles.

Triggering DFS from each course detects cycles and builds the ordering for all components.

Line 27 Core

return output

Return the list of courses in a valid order after processing all courses.

The output list contains a topological ordering of courses respecting all prerequisites, representing a valid schedule.

Line 3 Core

prereq = {c: [] for c in range(numCourses)}

Initialize the adjacency list mapping each course to an empty list of prerequisites.

This creates a graph representation where each course is a node, and edges point to its prerequisites, enabling efficient traversal.

Line 9 Core

def dfs(crs):

Define the DFS function to explore prerequisites of a given course.

Encapsulating DFS logic allows recursive exploration of dependencies and cycle detection in a clean, reusable manner.

Line 13 Core

return True

Return True if the course was already processed successfully.

Indicates that this course and its prerequisites have been validated and added to the output, so no further action is needed.

Line 16 Core

for pre in prereq[crs]:

Iterate over all prerequisites of the current course.

Exploring all dependencies ensures that the course ordering respects all prerequisite constraints.

Line 22 Core

return True

Return True indicating successful processing of the current course.

Signals that no cycles were found and the course was added to the ordering correctly.

Line 24 Core

for c in range(numCourses):

Iterate over all courses to ensure complete processing.

Since the graph may be disconnected, this loop ensures all courses are considered for ordering.

Line 4 Standard

for crs, pre in prerequisites:

Iterate over each prerequisite pair to populate the adjacency list.

Filling the adjacency list with actual prerequisite edges sets up the graph structure needed for DFS traversal.

Test Your Understanding

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

Because nodes in the recursion stack represent the current path of exploration; encountering a node already in this stack indicates a cycle. Visited nodes outside the recursion stack have been fully processed and do not indicate cycles.

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`

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

Problem

Example

Approach

Solution

Step-by-Step Solution

Build Adjacency List Mapping Courses to Prerequisites

Perform DFS with Cycle Detection to Validate and Order Courses

Iterate Over All Courses to Trigger DFS and Return Final Ordering

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.