LeetCode 207: Course Schedule

Problem Restatement

We are given:

• numCourses
• a list of prerequisite pairs

Each pair:

[a, b]

means:

to take course a, you must first complete course b

We need to determine whether it is possible to finish all courses.

The official statement says: there are numCourses courses 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. Return true if you can finish all courses. Otherwise return false.

Input and Output

Example function shape:

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    ...

Examples

Example 1:

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

Meaning:

0 -> 1

Take course 0 first, then course 1.

Possible ordering:

0, 1

Answer:

True

Example 2:

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

Graph:

0 -> 1
1 -> 0

This creates a cycle.

To take 0, we need 1.

To take 1, we need 0.

Impossible.

Answer:

False

Understanding the Graph

This problem is a directed graph problem.

Each course is a node.

Each prerequisite relation is a directed edge.

Example:

[1, 0]

means:

0 -> 1

because course 0 must happen before course 1.

The important observation:

• If the graph contains a cycle, the courses cannot be completed.
• If the graph is acyclic, the courses can be completed.

So the real problem becomes:

Does the directed graph contain a cycle?

Key Insight

A valid course ordering exists exactly when the graph is a Directed Acyclic Graph (DAG).

So we only need cycle detection.

There are two classic solutions:

We will start with BFS topological sorting because it is often easier to visualize.

Topological Sorting Idea

A course with indegree 0 has no remaining prerequisites.

So we can safely take it first.

After taking it:

• remove its outgoing edges
• reduce indegrees of dependent courses

Repeat until no more courses are available.

If we process every course, the graph had no cycle.

If some courses remain locked forever, there must be a cycle.

Algorithm (BFS / Kahn’s Algorithm)

1. Build the graph.
2. Compute indegree of every course.
3. Push every course with indegree 0 into a queue.
4. Repeatedly:
   • pop a course
   • count it as completed
   • reduce indegree of neighbors
   • if a neighbor becomes 0, push it into the queue
5. If completed course count equals numCourses, return True.
6. Otherwise return False.

Walkthrough

Use:

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

Graph:

0 -> 1
0 -> 2
1 -> 3
2 -> 3

Initial indegrees:

Queue starts with:

[0]

Process 0.

Reduce indegrees:

Push:

[1, 2]

Process 1.

Reduce indegree of 3:

2 -> 1

Process 2.

Reduce indegree of 3:

1 -> 0

Push 3.

Eventually all four courses are processed.

Answer:

True

Why Cycles Break the Process

Suppose:

prerequisites = [[1,0],[0,1]]

Indegrees:

No course has indegree 0.

The queue starts empty.

We cannot begin.

That means the graph contains a cycle.

Correctness

The algorithm repeatedly selects courses with indegree 0.

A course with indegree 0 has no unmet prerequisites, so it is safe to complete.

When the algorithm removes such a course, it also removes all outgoing edges from that course by decrementing neighbor indegrees. This correctly models completing the prerequisite.

If the graph is acyclic, there is always at least one node with indegree 0. Therefore the algorithm continues removing courses until all courses are processed.

If the graph contains a cycle, every node in the cycle always has at least one incoming edge from another node in the cycle. No node in the cycle can ever reach indegree 0.

Therefore the queue eventually becomes empty before all courses are processed.

So:

• processing all courses means the graph is acyclic
• failing to process all courses means the graph contains a cycle

Thus the algorithm correctly determines whether all courses can be completed.

Complexity

Where:

• V = numCourses
• E = number of prerequisite pairs

BFS Topological Sort Implementation

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        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

Code Explanation

Build adjacency list:

graph = [[] for _ in range(numCourses)]

Build indegree array:

indegree = [0] * numCourses

For every prerequisite:

graph[prereq].append(course)
indegree[course] += 1

Push all courses with no prerequisites:

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

Process courses:

current = queue.popleft()

Reduce indegrees of dependent courses:

indegree[neighbor] -= 1

If a course becomes available:

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

Finally:

return completed == numCourses

If every course was processed, there was no cycle.

DFS Cycle Detection Solution

We can also detect cycles directly using DFS.

Each node has three states:

If DFS reaches a node already marked 1, we found a cycle.

DFS Implementation

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

        for course, prereq in prerequisites:
            graph[prereq].append(course)

        state = [0] * numCourses

        def dfs(node):
            if state[node] == 1:
                return False

            if state[node] == 2:
                return True

            state[node] = 1

            for neighbor in graph[node]:
                if not dfs(neighbor):
                    return False

            state[node] = 2

            return True

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

        return True

DFS Explanation

When entering a node:

state[node] = 1

This means the node is currently inside the recursion stack.

If DFS reaches another node already marked 1, then we returned to an unfinished ancestor, which forms a cycle.

After fully processing a node:

state[node] = 2

This means the node is safe and fully explored.

Testing

def run_tests():
    s = Solution()

    assert s.canFinish(2, [[1,0]]) is True
    assert s.canFinish(2, [[1,0],[0,1]]) is False
    assert s.canFinish(4, [[1,0],[2,0],[3,1],[3,2]]) is True
    assert s.canFinish(1, []) is True
    assert s.canFinish(3, [[1,0],[2,1],[0,2]]) is False

    print("all tests passed")

run_tests()