How do you solve Course Schedule?

Build an adjacency list mapping each course to its prerequisites. For each course, perform a DFS to check for cycles by tracking nodes in the current recursion stack. If a cycle is found, return false immediately. If no cycles are detected after processing all courses, return true. Clearing the prerequisites list after processing a course marks it as safe and avoids repeated DFS calls.

What pattern does Course Schedule use?

The Pattern: DFS (Cycle Detection in Directed Graph) The Heuristic: Use a recursion stack (visit set) to detect cycles by tracking nodes currently in the path; revisiting a node in this stack signals a cycle, enabling early termination.

Course Schedule — DFS

Q: What is the time complexity of Course Schedule?

O(V + E). Each course (vertex) is visited once, and each prerequisite (edge) is explored once during DFS. Memoization by clearing prerequisites ensures no repeated work, resulting in linear time relative to the graph size.

Problem

Given the total number of courses and a list of prerequisite pairs, determine if it is possible to finish all courses by taking them in an order that satisfies all prerequisites.

1 ≤ numCourses ≤ 10⁵
0 ≤ prerequisites.length ≤ 5000
prerequisites[i].length == 2
0 ≤ a_i, b_i < numCourses
All the pairs prerequisites[i] are unique.

Example

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

Output: true

There are two courses: 0 and 1. To take course 1, you must first take course 0. The order [0,1] satisfies the prerequisites, so it is possible to finish all courses.

Approach

Straightforward Solution

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

Core Observation

The problem reduces to detecting if a directed graph (courses as nodes, prerequisites as edges) contains a cycle. If a cycle exists, it is impossible to complete all courses because some courses depend on each other circularly.

Path to Optimal

Preview

Recognizing the problem as cycle detection in a directed graph leads to using DFS with a recursion stack (visit set) to detect back edges indicating cycles. Constructing an adjacency list from prerequisites allows efficient traversal…

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 to check for cycles by tracking nodes in the current recursion stack…

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) is visited once, and each prerequisite (edge) is explored once during DFS. Memoization by clearing prerequisites ensures no repeated work, resulting in linear time relative to the graph size.

Space

O(V + E)

The adjacency list stores all edges, requiring O(E) space. The recursion stack and visit set use O(V) space in the worst case, where V is the number of courses.

Solution

Python

1class Solution:
  def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
      pre_map = {i: [] for i in range(numCourses)}
      for crs, pre in prerequisites:
          pre_map[crs].append(pre)
      
      visit_set = set()
      def dfs(crs):
          if crs in visit_set:
              return False
          if pre_map[crs] == []:
              return True
          
          visit_set.add(crs)
          for pre in pre_map[crs]:
              if not dfs(pre): return False
          visit_set.remove(crs)
          pre_map[crs] = []
          return True
20
      for crs in range(numCourses):
          if not dfs(crs): return False
      return True

Step-by-Step Solution

1

Build Adjacency List Mapping Courses to Prerequisites

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

Objective

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

Key Insight

An adjacency list is a natural and efficient way to represent directed graphs, especially when edges are sparse. Mapping each course to its list of prerequisites allows quick access to dependencies during DFS. This structure transforms the problem into graph traversal and cycle detection.

Interview Quick-Check

Core Logic

The adjacency list stores all prerequisite edges, enabling O(1) access to a course's prerequisites during DFS.

Common Pitfalls & Bugs

Forgetting to initialize all courses in the adjacency list can cause key errors or missed nodes during traversal.

2

Use DFS with Recursion Stack to Detect Cycles

To recursively explore prerequisites and detect cycles by tracking the current path.

3

Iterate Over All Courses to Verify Completion Feasibility

To ensure all courses are checked for cycles and dependencies.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 9 Critical lines interviewers watch for.

Line 9 Critical

if crs in visit_set:

Check if the current course is already in the recursion stack.

Detecting a course in the current path signals a cycle, which invalidates the course completion order.

Line 17 Critical

visit_set.remove(crs)

Remove the current course from the recursion stack after exploration.

Removing the course restores state for other DFS paths and prevents false cycle detection in separate branches.

Line 7 Critical

visit_set = set()

Initialize a set to track courses currently in the recursion stack.

The visit_set tracks the current DFS path to detect cycles by identifying back edges, which is critical for correctness.

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

Test Your Understanding

Why does detecting a node already in the recursion stack during DFS indicate a cycle?

See the answer with Pro.

Don't just read it. Drill it.

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

Unlock the Course Schedule drill

or drill a free problem

1	`class Solution:`
2	`def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:`
3	`pre_map = {i: [] for i in range(numCourses)}`
4	`for crs, pre in prerequisites:`
5	`pre_map[crs].append(pre)`
6
7	`visit_set = set()`
8	`def dfs(crs):`
9	`if crs in visit_set:`
10	`return False`
11	`if pre_map[crs] == []:`
12	`return True`
13
14	`visit_set.add(crs)`
15	`for pre in pre_map[crs]:`
16	`if not dfs(pre): return False`
17	`visit_set.remove(crs)`
18	`pre_map[crs] = []`
19	`return True`
20
21	`for crs in range(numCourses):`
22	`if not dfs(crs): return False`
23	`return True`