Skip to content

Leetcode 207 - Course Schedule

Understanding the Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a.

Return:

  • True if you can finish all courses.
  • False if it is impossible (i.e., a dependency cycle exists).

Key Data Structures

1. Adjacency List (preMap)

A hash map mapping each course to a list of its required prerequisites. This enables quick \(O(1)\) lookup for outgoing edges during graph traversal.

2. Recursion Stack Set (visiting)

A set used during Depth-First Search (DFS) to track courses currently on the active recursion path. If a node is re-visited while still in this set, a cycle is detected.

Optimal Approach Intuition

This problem can be modeled as finding a directed cycle in a Directed Graph:

  • Nodes: Courses (\(0\) to numCourses - 1).
  • Directed Edges: Prerequisites (\(a \to b\)).

If the graph contains a directed cycle (e.g., Course A requires B, B requires C, C requires A), it is impossible to complete all courses. If the graph is a Directed Acyclic Graph (DAG), a valid topological ordering exists.

Why DFS with Backtracking and Memoization?

1. Backtracking for Cycle Detection

Adding a course to visiting before traversing deeper and removing it upon return allows us to track nodes along the current traversal path. If DFS encounters a course already in visiting, a back-edge (cycle) has been hit.

2. Memoization via Graph Pruning

Once a course is verified as reachable and cycle-free (returns True), we clear its prerequisites list (preMap[crs] = []). If another traversal path reaches this course later, it returns True immediately in \(O(1)\) time without re-exploring downstream paths.

How the Optimal Approach Works

Step 1: Build the Adjacency Map

Map each course to its list of prerequisites.

prerequisites = [[0, 1], [0, 2], [1, 3], [2, 3]]

preMap:
0 -> [1, 2]
1 -> [3]
2 -> [3]
3 -> []

Step 2: DFS Traversal with Cycle Check

Iterate through all courses from \(0\) to numCourses - 1. Perform DFS on each course to verify no cycles exist:

  1. Base Case 1: If crs in visiting, a cycle is detected \(\to\) Return False.
  2. Base Case 2: If preMap[crs] == [], the course has no prerequisites (or was already fully validated) \(\to\) Return True.
  3. Add crs to visiting.
  4. Recursively run DFS on all prerequisites of crs. If any return False, propagate False.
  5. Remove crs from visiting (backtrack).
  6. Set preMap[crs] = [] to cache the result.
  7. Return True.

Solution Implementation

from typing import List


class Solution:

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Step 1: Map each course to its prerequisites
        preMap = {i: [] for i in range(numCourses)}
        for crs, pre in prerequisites:
            preMap[crs].append(pre)

        # Store all courses along the current DFS path (cycle detection)
        visiting = set()

        def dfs(crs):
            # Base Case 1: Cycle detected
            if crs in visiting:
                return False

            # Base Case 2: Fully validated or no prerequisites
            if preMap[crs] == []:
                return True

            visiting.add(crs)

            # Check all dependencies
            for pre in preMap[crs]:
                if not dfs(pre):
                    return False

            # Backtrack and memoize
            visiting.remove(crs)
            preMap[crs] = []
            return True

        # Step 2: Run DFS for each course (handles disconnected components)
        for c in range(numCourses):
            if not dfs(c):
                return False

        return True

Complexity Analysis

Let:

  • \(V\) = numCourses (Number of vertices)
  • \(E\) = len(prerequisites) (Number of edges)

Time Complexity: \(O(V + E)\)

  • Adjacency Map Construction: \(O(V + E)\) to build preMap.
  • DFS Traversal: Each node is visited once and each edge is traversed at most once because nodes are marked processed (preMap[crs] = []) after validation.

Overall Time Complexity: \(O(V + E)\)

Space Complexity: \(O(V + E)\)

  • Adjacency Map (preMap): Stores \(V\) keys and \(E\) total prerequisite entries \(\to O(V + E)\).
  • Recursion Stack & visiting set: Can grow up to \(O(V)\) depth in the worst-case linear dependency graph.

Overall Space Complexity: \(O(V + E)\)

Key Takeaways

  • Cycle Detection Pattern: A cycle exists in a directed graph if traversal hits a node currently residing on the active recursion stack (visiting set).
  • Pruning / Memoization: Resetting processed node edges (preMap[crs] = []) prevents re-exploring shared branches across DAG components, reducing runtime to linear \(O(V + E)\).
  • Handling Disconnected Graphs: An outer loop across \(0 \dots V-1\) ensures isolated nodes and independent components are evaluated.

Common Mistakes

Mistake 1: Confusing Global Visited with Path Visited

Using a global visited set without backtracking elements upon exit falsely identifies cycles on converging non-cyclic paths (e.g., \(A \to C\) and \(B \to C\)).

Fix:

  • Remove crs from visiting when returning from the recursive step.

Mistake 2: Missing the Memoization Step

Forgetting to prune preMap[crs] = [] upon completion forces DFS to re-explore shared dependencies repeatedly, leading to TLE (Time Limit Exceeded).

Fix:

  • Clear the node's list of dependencies once all sub-paths return True.

Mistake 3: Assuming Graph Connectivity

Running DFS starting only from vertex 0 assumes all courses are reachable from 0.

Fix:

  • Iterate through every course from 0 to numCourses - 1 in the outer loop.

Additional Resources