View on NeetCode
View on LeetCode

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] = [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.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are 2 courses. 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 2 courses. 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.

Solution

Approach 1: DFS Cycle Detection

The key insight is that we can finish all courses if and only if the prerequisite graph has no cycles. We use DFS to detect cycles.

Implementation

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Build adjacency list
        graph = [[] for _ in range(numCourses)]
        for course, prereq in prerequisites:
            graph[course].append(prereq)

        # 0 = unvisited, 1 = visiting (in current path), 2 = visited
        visit = [0] * numCourses

        def dfs(course):
            if visit[course] == 1:  # Cycle detected
                return False
            if visit[course] == 2:  # Already checked, no cycle
                return True

            # Mark as visiting
            visit[course] = 1

            # Check all prerequisites
            for prereq in graph[course]:
                if not dfs(prereq):
                    return False

            # Mark as visited
            visit[course] = 2
            return True

        # Check each course
        for course in range(numCourses):
            if not dfs(course):
                return False

        return True

Approach 2: Topological Sort (Kahn’s Algorithm)

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Build adjacency list and in-degree array
        graph = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses

        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1

        # Start with courses that have no prerequisites
        queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
        completed = 0

        while queue:
            course = queue.popleft()
            completed += 1

            # Remove this course as a prerequisite
            for next_course in graph[course]:
                in_degree[next_course] -= 1
                if in_degree[next_course] == 0:
                    queue.append(next_course)

        # If we completed all courses, no cycle exists
        return completed == numCourses

Complexity Analysis

Both Approaches:

• Time Complexity: O(V + E), where V is number of courses and E is number of prerequisites. We visit each node and edge once.
• Space Complexity: O(V + E) for the adjacency list and auxiliary data structures.

Key Insights

1. Cycle Detection: The problem is essentially asking if the directed graph has a cycle. A cycle means impossible to complete all courses.

2. DFS States: Using three states (unvisited, visiting, visited) allows us to detect cycles in a single DFS pass.

3. Topological Sort: If we can produce a valid topological ordering of all courses, then there’s no cycle.

4. In-Degree Tracking: Kahn’s algorithm tracks in-degrees and processes nodes with in-degree 0, which represent courses with no remaining prerequisites.

5. Graph Direction: prerequisites[i] = [a, b] means b → a (b must come before a), so we add edge from b to a or a depends on b.