LeetCode Solutions Blog

Course Schedule

Number: 207

Difficulty: Medium

Paid? No

Problem Description

We are given the total number of courses (labeled 0 to numCourses - 1) and a list of prerequisite pairs. For each pair [a, b], you must complete course b before course a. The task is to determine if it is possible to finish all courses given these prerequisites. This is equivalent to checking if the directed graph (where courses are nodes and prerequisites are directed edges) contains a cycle.

Key Insights

This problem can be modeled as a directed graph where courses are nodes and prerequisites are edges.
If the graph has a cycle, then it is not possible to complete all courses.
We can detect cycles using either Topological Sort (BFS/Kahn’s algorithm) or DFS-based cycle detection.
The time complexity is O(V + E), where V is the number of courses and E is the number of prerequisite pairs.

Space and Time Complexity

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

Solution

We solve the problem using the Topological Sort algorithm (BFS/Kahn’s algorithm). First, we build a graph (using an adjacency list) and track the indegree (number of prerequisites) for each course. We then find all courses with an indegree of zero (courses with no prerequisites) and add them to a processing queue. While the queue is not empty, we remove a course from the queue, reduce the indegree for its neighboring courses, and if any neighbor’s indegree becomes zero, we add it to the queue as well. If we successfully process all courses, then it means that the graph was acyclic and a valid schedule exists, returning true. If not, a cycle exists, and we return false.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with detailed inline comments.

from collections import deque

def canFinish(numCourses, prerequisites):
    # Create a list to hold the number of prerequisites (indegree) for each course.
    indegree = [0] * numCourses
    # Create an adjacency list for each course.
    graph = {i: [] for i in range(numCourses)}
    
    # Build the graph and update indegree for each course.
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    # Initialize a queue with courses that have no prerequisites.
    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    
    # Counter for courses that can be completed.
    visited = 0
    
    while queue:
        course = queue.popleft()  # Remove course with no remaining prerequisites.
        visited += 1  # Increment count of completed courses.
        # For each neighbor course, reduce its indegree.
        for neighbor in graph[course]:
            indegree[neighbor] -= 1  # Remove dependency.
            # If no more prerequisites, add to queue.
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    
    # If we processed all courses, it's possible to finish.
    return visited == numCourses

# Example usage:
print(canFinish(2, [[1,0]]))  # Expected output: True
print(canFinish(2, [[1,0],[0,1]]))  # Expected output: False