LeetCode 207 - Course Schedule

This problem models course dependencies as a directed graph. Each course is represented as a node, and each prerequisite relationship is represented as a directed edge. If prerequisites[i] = [a, b], that means course b must be completed before course a.

leetcodemediumdepth-first-searchbreadth-first-searchgraph-theorytopological-sort

LeetCode Problem 207

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Solution

Problem Understanding

This problem models course dependencies as a directed graph. Each course is represented as a node, and each prerequisite relationship is represented as a directed edge.

If prerequisites[i] = [a, b], that means course b must be completed before course a. In graph terms, there is a directed edge from b to a.

The task is to determine whether it is possible to complete all courses. This is equivalent to asking whether the dependency graph contains a cycle.

A cycle means there is a circular dependency. For example:

  • Course 0 requires Course 1
  • Course 1 requires Course 0

In this situation, neither course can ever be taken first, so finishing all courses becomes impossible.

The input consists of:

  • numCourses, the total number of courses labeled from 0 to numCourses - 1
  • prerequisites, a list of prerequisite relationships

The expected output is:

  • true if all courses can eventually be completed
  • false if at least one cyclic dependency exists

The constraints are important because they guide the choice of algorithm:

  • Up to 2000 courses
  • Up to 5000 prerequisite relationships

A brute-force simulation would become inefficient as the graph grows. These constraints strongly suggest using graph traversal algorithms such as Depth-First Search (DFS), Breadth-First Search (BFS), or topological sorting.

Several edge cases are important:

  • No prerequisites at all, every course can be completed immediately
  • A direct cycle between two courses
  • A longer cycle involving multiple courses
  • Multiple disconnected groups of courses
  • Courses that never appear in the prerequisite list
  • A graph where many courses depend on the same prerequisite

The problem also guarantees that all prerequisite pairs are unique, so duplicate edges do not need special handling.

Approaches

Brute Force Approach

A naive approach would repeatedly search for courses whose prerequisites are already satisfied, remove them, and continue until either all courses are processed or no progress can be made.

Conceptually, this works as follows:

  • Scan every course
  • Check whether all of its prerequisites are completed
  • If so, mark it as completed
  • Repeat until no new courses can be completed

This approach is correct because it simulates the actual process of taking courses in valid order. If at some point no course can be taken while unfinished courses still remain, then a cycle must exist.

However, this repeated scanning becomes inefficient. In the worst case, every iteration may scan all courses and all prerequisite relationships again. With up to 2000 courses and 5000 edges, the repeated work becomes unnecessarily expensive.

Optimal Approach

The key observation is that this problem is fundamentally a cycle detection problem in a directed graph.

If the graph has no cycle, then a valid topological ordering exists, meaning courses can be completed in some order.

A very efficient way to detect cycles is to use topological sorting with Breadth-First Search, commonly known as Kahn's Algorithm.

The idea is:

  • Count how many prerequisites each course has, this is called the indegree
  • Any course with indegree 0 can be taken immediately
  • Once a course is completed, remove its outgoing edges
  • This may unlock additional courses whose indegree becomes 0
  • Continue until no more courses can be processed

If all courses are processed, the graph is acyclic.

If some courses remain unprocessed, they must belong to a cycle.

Approach Time Complexity Space Complexity Notes
Brute Force O(V × E) O(V + E) Repeatedly scans prerequisites to find available courses
Optimal O(V + E) O(V + E) Uses BFS topological sort and indegree tracking

Here, V is the number of courses and E is the number of prerequisite relationships.

Algorithm Walkthrough

Optimal Algorithm, Kahn's Topological Sort

  1. Build an adjacency list representing the graph.

For every prerequisite pair [a, b], add an edge from b to a.

This structure allows us to quickly find which courses become available after completing another course. 2. Create an indegree array.

indegree[i] stores how many prerequisites course i still requires before it can be taken.

Every time we add an edge b -> a, increment indegree[a]. 3. Initialize a queue with all courses that have indegree 0.

These courses have no prerequisites and can be taken immediately.

A queue is ideal because we process courses in the order they become available. 4. Start processing the queue.

Remove one course from the queue and count it as completed.

Then look at all neighboring courses that depend on it. 5. Reduce the indegree of neighboring courses.

Completing the current course satisfies one prerequisite for each neighbor.

Therefore, decrement their indegree by 1. 6. Add newly unlocked courses to the queue.

If a neighbor's indegree becomes 0, it means all prerequisites are now satisfied.

Push it into the queue so it can be processed later. 7. Continue until the queue becomes empty.

At this point, either:

  • All courses were processed successfully
  • Some courses remain stuck in a cycle
  1. Compare the number of processed courses with numCourses.

If they match, return True.

Otherwise, return False.

Why it works

The algorithm maintains the invariant that only courses with all prerequisites satisfied enter the queue.

In a graph without cycles, repeatedly removing indegree-0 nodes eventually processes every node. This is a fundamental property of Directed Acyclic Graphs, also called DAGs.

If a cycle exists, every node inside the cycle will always have at least one remaining prerequisite. Therefore, none of them will ever reach indegree 0, and the algorithm will terminate early with unprocessed courses remaining.

Python Solution

from collections import deque
from typing import List

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

        # indegree[i] = number of prerequisites for course i
        indegree = [0] * numCourses

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

        # Start with courses that have no prerequisites
        queue = deque()

        for course in range(numCourses):
            if indegree[course] == 0:
                queue.append(course)

        completed_courses = 0

        while queue:
            current = queue.popleft()
            completed_courses += 1

            # Remove outgoing edges
            for neighbor in graph[current]:
                indegree[neighbor] -= 1

                # If all prerequisites are satisfied
                if indegree[neighbor] == 0:
                    queue.append(neighbor)

        return completed_courses == numCourses

The implementation begins by constructing the graph as an adjacency list. Each index represents a course, and the stored list contains courses that depend on it.

The indegree array tracks how many prerequisites remain for each course. Every prerequisite relationship increases the indegree of the dependent course.

The queue stores all currently available courses, meaning courses whose indegree is 0.

The BFS loop processes courses one by one. When a course is completed, all outgoing edges are effectively removed by decrementing the indegree of neighboring courses.

Whenever a neighbor's indegree becomes 0, it means every prerequisite has been satisfied, so the course becomes eligible for processing.

Finally, the algorithm checks whether the number of completed courses equals the total number of courses. If not, some courses were trapped in a cycle.

Go Solution

func canFinish(numCourses int, prerequisites [][]int) bool {
	graph := make([][]int, numCourses)
	indegree := make([]int, numCourses)

	// Build graph and indegree array
	for _, pair := range prerequisites {
		course := pair[0]
		prereq := pair[1]

		graph[prereq] = append(graph[prereq], course)
		indegree[course]++
	}

	// Queue for BFS
	queue := []int{}

	for course := 0; course < numCourses; course++ {
		if indegree[course] == 0 {
			queue = append(queue, course)
		}
	}

	completedCourses := 0

	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]

		completedCourses++

		for _, neighbor := range graph[current] {
			indegree[neighbor]--

			if indegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}

	return completedCourses == numCourses
}

The Go implementation follows the same algorithmic structure as the Python solution.

Instead of Python's deque, Go uses a slice as a queue. Removing the front element is done using queue = queue[1:].

Go slices are dynamically sized, making them appropriate for adjacency lists and BFS queues.

No special handling for integer overflow is necessary because all values remain well within Go's int range under the problem constraints.

An empty slice in Go behaves similarly to an empty list in Python, so no special nil handling is required.

Worked Examples

Example 1

Input:

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

Graph representation:

0 -> 1

Initial state:

Course Indegree
0 0
1 1

Initial queue:

[0]

Processing steps:

Step Current Course Queue After Processing Indegree State Completed
1 0 [1] [0, 0] 1
2 1 [] [0, 0] 2

At the end:

completed_courses = 2
numCourses = 2

Since all courses were processed, the answer is true.

Example 2

Input:

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

Graph representation:

0 -> 1
1 -> 0

Initial state:

Course Indegree
0 1
1 1

Initial queue:

[]

No course has indegree 0, so the queue starts empty.

Processing steps:

Step Current Course Queue Completed
None None [] 0

At the end:

completed_courses = 0
numCourses = 2

Not all courses could be processed, meaning a cycle exists.

The answer is false.

Complexity Analysis

Measure Complexity Explanation
Time O(V + E) Each course and prerequisite edge is processed once
Space O(V + E) The adjacency list, indegree array, and queue require additional storage

The graph construction phase processes every prerequisite once. The BFS traversal also visits every node and edge at most once.

The adjacency list stores all edges, the indegree array stores one value per course, and the queue can contain up to all courses in the worst case.

Test Cases

from typing import List

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        from collections import deque

        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

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

        queue = deque()

        for course in range(numCourses):
            if indegree[course] == 0:
                queue.append(course)

        completed = 0

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

            for neighbor in graph[current]:
                indegree[neighbor] -= 1

                if indegree[neighbor] == 0:
                    queue.append(neighbor)

        return completed == numCourses

solution = Solution()

assert solution.canFinish(2, [[1, 0]]) == True  # Simple valid dependency
assert solution.canFinish(2, [[1, 0], [0, 1]]) == False  # Direct cycle
assert solution.canFinish(1, []) == True  # Single course, no prerequisites
assert solution.canFinish(3, [[1, 0], [2, 1]]) == True  # Linear dependency chain
assert solution.canFinish(3, [[1, 0], [2, 1], [0, 2]]) == False  # Three-node cycle
assert solution.canFinish(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) == True  # Multiple dependencies
assert solution.canFinish(5, []) == True  # No prerequisites at all
assert solution.canFinish(4, [[1, 0], [2, 1]]) == True  # Disconnected graph
assert solution.canFinish(6, [[1, 0], [2, 1], [3, 2], [1, 3]]) == False  # Larger cycle
assert solution.canFinish(2000, []) == True  # Maximum courses, no dependencies
Test Why
2, [[1,0]] Basic valid dependency
2, [[1,0],[0,1]] Smallest possible cycle
1, [] Minimum input size
3, [[1,0],[2,1]] Simple chain structure
3, [[1,0],[2,1],[0,2]] Multi-node cycle detection
4, [[1,0],[2,0],[3,1],[3,2]] Multiple prerequisites converging
5, [] Entirely disconnected graph
4, [[1,0],[2,1]] Some courses unused in prerequisites
6, [[1,0],[2,1],[3,2],[1,3]] Larger cyclic structure
2000, [] Upper boundary for course count

Edge Cases

No prerequisites

A common edge case is when prerequisites is empty.

In this scenario, every course has indegree 0 and can immediately enter the queue. The algorithm correctly processes all courses and returns True.

Naive implementations sometimes forget to initialize isolated nodes properly, but this solution explicitly iterates through all courses when building the initial queue.

Cycles involving multiple courses

Cycles are not always direct two-course loops. A longer cycle such as:

0 -> 1 -> 2 -> 0

can be harder to detect with simplistic logic.

This implementation handles such cases naturally because none of the nodes in the cycle can ever reach indegree 0. As a result, the BFS traversal stops early, leaving unprocessed nodes behind.

Disconnected graph components

The graph may contain several completely separate groups of courses.

For example:

0 -> 1

2 -> 3

A buggy implementation might only traverse from one starting point and miss another component entirely.

This solution avoids that issue by initially inserting every indegree-0 course into the queue, ensuring all disconnected components are explored.

Courses not appearing in prerequisites

Some courses may never appear in the prerequisite list at all.

For example:

numCourses = 5
prerequisites = [[1,0]]

Courses 2, 3, and 4 are completely independent.

The algorithm handles this correctly because every course starts with indegree 0 unless explicitly assigned prerequisites. Independent courses are therefore processed normally.