LeetCode 210 - Course Schedule II

LeetCode Problem 210

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

Solution

Problem Understanding

This problem asks us to determine a valid order in which courses can be completed given prerequisite relationships between them.

You are given numCourses, which represents the total number of courses labeled from 0 to numCourses - 1. You are also given a list called prerequisites, where each entry [a, b] means that course b must be completed before course a.

In graph terminology, this forms a directed graph:

• Each course is a node.
• A prerequisite relationship is a directed edge.
• If [a, b] exists, we draw an edge b → a, meaning b must come before a.

The goal is to return one valid ordering of all courses such that every prerequisite requirement is satisfied. If multiple valid orderings exist, returning any one of them is acceptable. However, if no valid ordering exists because of a cycle in the dependency graph, we must return an empty array.

For example, if course 1 depends on course 0, then 0 must appear earlier in the output ordering. A valid answer for:

[[1,0],[2,0],[3,1],[3,2]]

could be:

[0,1,2,3]

or:

[0,2,1,3]

because both satisfy all prerequisite dependencies.

The constraints are important for selecting an efficient algorithm:

• numCourses <= 2000
• The number of prerequisite pairs can approach numCourses * (numCourses - 1)

This means the graph can become fairly dense. A brute-force strategy that repeatedly checks permutations would be computationally infeasible. Instead, we need an algorithm that scales close to linear time relative to the number of nodes and edges.

The major edge cases include:

• No prerequisites, where every course is immediately available.
• Cycles, where completing all courses becomes impossible.
• Disconnected components, where independent groups of courses exist.
• Courses with no dependencies and no dependents, which still must appear in the result.
• Multiple valid answers, where any correct ordering should be accepted.

Approaches

Brute Force Approach

A brute-force approach would attempt to generate all possible permutations of courses and check whether each permutation satisfies all prerequisite constraints.

For every ordering, we could verify whether every prerequisite [a, b] satisfies the condition that b appears before a. The first valid ordering would be returned.

This approach is correct because it exhaustively searches the entire solution space. If a valid ordering exists, it will eventually be found.

However, the problem is computationally infeasible because there are n! possible permutations for n courses. Even for relatively small values of n, this becomes astronomically expensive.

For example:

10! = 3,628,800
15! = 1,307,674,368,000

Since numCourses can reach 2000, brute force is entirely impractical.

Key Insight

The important observation is that this problem is actually asking for a topological ordering of a directed graph.

A topological sort exists only if the graph is a Directed Acyclic Graph (DAG). If a cycle exists, then no valid ordering can satisfy all prerequisite requirements.

We can solve this efficiently using Kahn's Algorithm, which is a Breadth-First Search based topological sorting technique.

The idea is:

1. Count how many prerequisites each course has, this is called the in-degree.
2. Any course with in-degree 0 can be taken immediately.
3. Once a course is completed, remove its outgoing dependencies by reducing the in-degree of dependent courses.
4. Newly unlocked courses become available.
5. Continue until all courses are processed.

If we process all numCourses, we found a valid ordering. Otherwise, a cycle prevented completion.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × m)	O(n)	Tries every ordering and validates prerequisites
Optimal, Topological Sort (Kahn's Algorithm)	O(V + E)	O(V + E)	Processes each course and prerequisite once

Here:

• V = numCourses
• E = len(prerequisites)

Algorithm Walkthrough

1. Build the graph representation

Create an adjacency list where each course points to the courses that depend on it.

If [a, b] exists, then we add:

b → a

This direction matters because completing b unlocks a. 2. Compute in-degrees

Create an array called in_degree where in_degree[i] stores how many prerequisites course i still requires.

Every prerequisite edge increases the destination node's in-degree. 3. Initialize the queue

Add every course with in_degree == 0 into a queue.

These courses have no prerequisites, so they can be taken immediately. 4. Process courses using BFS

Repeatedly remove a course from the queue.

Add it to the result ordering because it is now considered completed.

For every dependent course:

• Reduce its in-degree by 1
• If its in-degree becomes 0, push it into the queue

This simulates unlocking new courses after prerequisites are completed. 5. Check for cycles

After processing, compare the result size with numCourses.

• If all courses were processed, return the ordering.
• Otherwise, a cycle exists, so return an empty list.

Why it works

The key invariant is that a course enters the queue only when all of its prerequisites have already been processed. This guarantees that when we append a course to the final ordering, every required dependency already appears earlier in the result.

If a cycle exists, no node in the cycle can ever reach in-degree 0, so some courses remain unprocessed. Detecting this condition allows us to correctly return an empty array.

Python Solution

from collections import deque
from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses

        # Build graph and calculate in-degrees
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1

        # Add all courses with no prerequisites
        queue = deque()

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

        order = []

        # Perform BFS topological sort
        while queue:
            current_course = queue.popleft()
            order.append(current_course)

            for neighbor in graph[current_course]:
                in_degree[neighbor] -= 1

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

        # Check if all courses were processed
        return order if len(order) == numCourses else []

Implementation Explanation

The implementation begins by constructing the graph using an adjacency list. Since each prerequisite pair [a, b] means b must come before a, we store a inside graph[b].

At the same time, we maintain an in_degree array that counts how many prerequisites remain for every course.

We then initialize a queue containing all courses with zero prerequisites. These are immediately eligible to be taken.

The BFS loop repeatedly removes a course from the queue and adds it to the final ordering. Once a course is completed, we reduce the in-degree of all dependent courses. Any course whose in-degree reaches zero becomes newly available and enters the queue.

Finally, we validate whether every course was processed. If the result contains fewer than numCourses items, some courses were trapped inside a cycle, making completion impossible.

Go Solution

func findOrder(numCourses int, prerequisites [][]int) []int {
	graph := make([][]int, numCourses)
	inDegree := make([]int, numCourses)

	// Build graph and calculate in-degrees
	for _, prereq := range prerequisites {
		course := prereq[0]
		required := prereq[1]

		graph[required] = append(graph[required], course)
		inDegree[course]++
	}

	// Initialize queue with zero in-degree nodes
	queue := make([]int, 0)

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

	order := make([]int, 0, numCourses)
	index := 0

	// BFS topological sort
	for index < len(queue) {
		currentCourse := queue[index]
		index++

		order = append(order, currentCourse)

		for _, neighbor := range graph[currentCourse] {
			inDegree[neighbor]--

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

	// Cycle detection
	if len(order) != numCourses {
		return []int{}
	}

	return order
}

Go-Specific Implementation Differences

The Go solution follows the exact same algorithm but differs slightly in implementation details.

Instead of using a deque structure, we simulate a queue with a slice and an index pointer. This avoids repeatedly removing elements from the front of a slice, which would be inefficient.

We use:

index := 0

to track the current front of the queue.

Go slices are dynamic, so appending newly unlocked courses is straightforward. Returning an empty result for cycles is done with:

return []int{}

instead of nil, which better matches LeetCode expectations.

Integer overflow is not a concern because the constraints remain well within Go's integer limits.

Worked Examples

Example 1

Input

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

Step 1: Build graph

Course	Neighbors
0	[1]
1	[]

In-degree array:

[0, 1]

Step 2: Initialize queue

Courses with in-degree 0:

queue = [0]

Step 3: BFS processing

Step	Queue	Current	In-degree	Result
1	[0]	0	[0,0]	[0]
2	[1]	1	[0,0]	[0,1]

Final result:

[0,1]

Example 2

Input

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

Step 1: Graph

Course	Neighbors
0	[1,2]
1	[3]
2	[3]
3	[]

In-degree:

[0,1,1,2]

Queue:

[0]

Step 2: BFS processing

Step	Queue	Current	In-degree	Result
1	[0]	0	[0,0,0,2]	[0]
2	[1,2]	1	[0,0,0,1]	[0,1]
3	[2]	2	[0,0,0,0]	[0,1,2]
4	[3]	3	[0,0,0,0]	[0,1,2,3]

A valid ordering is:

[0,1,2,3]

Another equally valid ordering could be:

[0,2,1,3]

Example 3

Input

numCourses = 1
prerequisites = []

Graph:

[[]]

In-degree:

[0]

Queue:

[0]

Processing:

Step	Queue	Current	Result
1	[0]	0	[0]

Final answer:

[0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(V + E)	Every course and prerequisite edge is processed once
Space	O(V + E)	Graph storage, queue, in-degree array, and result list

The adjacency list stores every prerequisite edge exactly once, giving O(E) space. The in-degree array, queue, and result list together require O(V) space. During BFS, each node enters the queue once and every edge is processed once, resulting in total linear complexity.

Test Cases

def is_valid_order(order, num_courses, prerequisites):
    if len(order) != num_courses:
        return False

    position = {course: i for i, course in enumerate(order)}

    for course, prereq in prerequisites:
        if position[prereq] > position[course]:
            return False

    return True

solution = Solution()

# Example 1
result = solution.findOrder(2, [[1, 0]])
assert is_valid_order(result, 2, [[1, 0]])  # simple dependency

# Example 2
result = solution.findOrder(4, [[1,0],[2,0],[3,1],[3,2]])
assert is_valid_order(
    result,
    4,
    [[1,0],[2,0],[3,1],[3,2]]
)  # multiple valid orderings

# Example 3
assert solution.findOrder(1, []) == [0]  # single course

# No prerequisites
result = solution.findOrder(5, [])
assert sorted(result) == [0,1,2,3,4]  # any ordering works

# Cycle detection
assert solution.findOrder(2, [[0,1],[1,0]]) == []  # impossible schedule

# Larger cycle
assert solution.findOrder(3, [[0,1],[1,2],[2,0]]) == []  # three-node cycle

# Disconnected graph
result = solution.findOrder(6, [[1,0],[3,2]])
assert is_valid_order(result, 6, [[1,0],[3,2]])  # independent components

# Chain dependency
assert solution.findOrder(4, [[1,0],[2,1],[3,2]]) == [0,1,2,3]  # linear chain

# Multiple independent starting nodes
result = solution.findOrder(4, [[2,0],[2,1]])
assert is_valid_order(result, 4, [[2,0],[2,1]])  # several zero in-degree nodes

Test	Why
2, [[1,0]]	Validates simple dependency ordering
4, [[1,0],[2,0],[3,1],[3,2]]	Tests branching dependencies
1, []	Minimum input size
5, []	No prerequisites
2, [[0,1],[1,0]]	Detects cycle
3, [[0,1],[1,2],[2,0]]	Detects larger cycle
6, [[1,0],[3,2]]	Handles disconnected components
4, [[1,0],[2,1],[3,2]]	Linear dependency chain
4, [[2,0],[2,1]]	Multiple independent prerequisites

Edge Cases

Cyclic Dependencies

A cycle is the most important edge case because it makes course completion impossible. For example:

0 → 1 → 0

Neither course can be taken first, since each depends on the other. A naive implementation might loop forever or return an invalid ordering. Our implementation detects this naturally because some courses never reach in-degree 0, meaning the final result length becomes smaller than numCourses.

Courses With No Prerequisites

If there are no prerequisite relationships, every course can be taken immediately. A fragile implementation might accidentally return only a subset of courses or assume dependencies exist. Since we initially enqueue every zero in-degree course, our algorithm correctly returns all courses.

Disconnected Components

The course graph may contain independent groups of courses. For example:

0 → 1

2 → 3

A naive DFS starting from a single node could miss entire sections of the graph. Our implementation iterates through all courses during queue initialization, ensuring every disconnected component is included.

Multiple Valid Orderings

Some inputs allow many valid schedules. For example:

[[2,0],[2,1]]

Both:

[0,1,2]

and

[1,0,2]

are correct. Our implementation does not force a unique answer. Instead, it returns whichever valid ordering naturally emerges from queue processing, which fully satisfies the problem requirements.