[Medium] 207. Course Schedule

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] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Examples

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

Thinking Process

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] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

• Model entities as nodes and relationships as edges.
• Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
• Union-Find helps when connectivity updates are frequent.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
BFS / DFS traversal (this problem)	O(V+E)	O(V)	Connectivity, flood fill
Dijkstra	O((V+E)log V)	O(V)	Non-negative edge weights
Union-Find (DSU)	O(α(n))	O(n)	Dynamic connectivity
Topological sort	O(V+E)	O(V)	DAG ordering, cycle detection

Solution

Solution 1: Topological Sort (Kahn’s Algorithm)

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        indegree = [0] * numCourses
        adj = [[] for _ in range(numCourses)]

        for course, pre in prerequisites:
            adj[pre].append(course)
            indegree[course] += 1

        q = deque()

        for i in range(numCourses):
            if indegree[i] == 0:
                q.append(i)

        count = 0

        while q:
            course = q.popleft()
            count += 1

            for next_course in adj[course]:
                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    q.append(next_course)

        return count == numCourses

Solution Explanation

Approach: BFS / DFS traversal (this problem)

Key idea: 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] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

How the code works:

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
• Model entities as nodes and relationships as edges.
• Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
• Union-Find helps when connectivity updates are frequent.

Walkthrough — input numCourses = 2, prerequisites = [[1,0]], expected output true:

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Solution 2: DFS Cycle Detection

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        adj = [[] for _ in range(numCourses)]

        for p in prerequisites:
            adj[p[1]].append(p[0])

        # 0 = unvisited, 1 = visiting, 2 = visited
        state = [0] * numCourses

        for i in range(numCourses):
            if self.hasCycle(i, adj, state):
                return False

        return True

    def hasCycle(self, node: int, adj: list[list[int]], state: list[int]) -> bool:
        if state[node] == 1:  # cycle found
            return True

        if state[node] == 2:  # already processed
            return False

        state[node] = 1  # mark as visiting

        for neighbor in adj[node]:
            if self.hasCycle(neighbor, adj, state):
                return True

        state[node] = 2  # mark as fully processed
        return False

Algorithm Explanation:

Topological Sort Approach:

1. Build graph: Create adjacency list and calculate indegrees
2. Initialize queue: Add all courses with indegree 0 (no prerequisites)
3. Process: Remove course from queue, decrement indegrees of its neighbors
4. Add to queue: If neighbor’s indegree becomes 0, add to queue
5. Check completion: If count equals numCourses, all courses can be completed

DFS Cycle Detection Approach:

1. Three states: 0=unvisited, 1=visiting, 2=visited
2. DFS from each unvisited node: Check for cycles
3. Cycle detection: If we encounter a “visiting” node during DFS, cycle exists
4. State transitions: unvisited → visiting → visited

Example Walkthrough:

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

Graph:
0 → 1 → 3
  ↘ 2 ↗

Topological Sort:
1. Indegrees: [0,1,1,2]
2. Start with course 0 (indegree=0)
3. Remove 0: indegrees become [0,0,0,2]
4. Add courses 1,2 to queue
5. Remove 1: indegrees become [0,0,0,1]
6. Remove 2: indegrees become [0,0,0,0]
7. Add course 3 to queue
8. Remove 3: count=4, return true

DFS Cycle Detection:
1. Start DFS from course 0
2. Visit 0: state[0]=1 (visiting)
3. Visit 1: state[1]=1 (visiting)
4. Visit 3: state[3]=1 (visiting)
5. No more neighbors, state[3]=2 (visited)
6. Back to 1: state[1]=2 (visited)
7. Back to 0: state[0]=2 (visited)
8. Continue with courses 2,3...
9. No cycles found, return true

Time Complexity: O(V + E)

• V: Number of courses (numCourses)
• E: Number of prerequisites
• Graph building: O(E)
• Traversal: O(V + E)
• Total: O(V + E)

Space Complexity: O(V + E)

• Adjacency list: O(V + E)
• Indegree array: O(V)
• Queue/Stack: O(V)
• State array: O(V)
• Total: O(V + E)

  Key Points

1. Graph problem: Courses and prerequisites form a directed graph
2. Cycle detection: Cycle means impossible to complete all courses
3. Two approaches: Topological sort and DFS both work
4. Topological sort: More intuitive for this problem
5. DFS: More general approach for cycle detection

Comparison: Topological Sort vs DFS

Aspect	Topological Sort	DFS Cycle Detection
Approach	Indegree counting	Three-state coloring
Intuition	Process courses in order	Detect cycles directly
Space	Queue + Indegree array	Recursion stack + State array
Code	More straightforward	More elegant
Performance	Similar	Similar

Common Mistakes

• Skipping edge cases (empty input, single element, boundaries).
• Off-by-one errors in loops and index ranges.
• Forgetting to handle the case when no valid answer exists.

Related Problems

• 210. Course Schedule II - Return actual schedule
• 802. Find Eventual Safe States - Similar cycle detection
• 329. Longest Increasing Path in a Matrix - DAG longest path

Tags

Graph, Topological Sort, Cycle Detection, DFS, Medium

Key Takeaways

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
• Model entities as nodes and relationships as edges.
• Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.

References

• LC 207: Course Schedule on LeetCode
• LeetCode Discuss — LC 207: Course Schedule
• LeetCode Editorial (may require premium)

Template Reference

• Graph