Skip to main content
Talentd

Course Schedule II - Solution & Explanation

MediumDepth-First SearchBreadth-First SearchGraphTopological Sort11 min readAsked at: Amazon, Microsoft, Apple +33
Practice this problem

Problem Statement

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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

 

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai != bi
  • All the pairs [ai, bi] are distinct.

Approach Overview

Problem Overview: You are given numCourses and a list of prerequisite pairs where [a, b] means you must take course b before a. The task is to return a valid ordering of all courses so every prerequisite is satisfied. If a cycle exists in the dependency graph, no valid order exists and you return an empty array.

This problem is a classic application of graph traversal and topological sort. Each course is a node and each prerequisite forms a directed edge. A valid schedule is simply a topological ordering of the directed graph.

Approach 1: Topological Sort using Kahn's Algorithm (BFS) (Time: O(V + E), Space: O(V + E))

Model the courses as a directed graph using an adjacency list and maintain an indegree array for each node. The indegree represents how many prerequisites a course still needs. Initialize a queue with all courses whose indegree is zero because they can be taken immediately. Repeatedly pop from the queue, append the course to the result, and decrease the indegree of its neighbors. Whenever a neighbor's indegree becomes zero, push it into the queue.

If you process all numCourses nodes, the result list is a valid ordering. If some nodes remain unprocessed, the graph contains a cycle. This approach works well because it explicitly tracks dependency resolution and processes nodes in dependency order using Breadth-First Search.

Approach 2: DFS with Cycle Detection (Time: O(V + E), Space: O(V + E))

This approach performs depth-first traversal while tracking node states to detect cycles. Each node can be marked as unvisited, visiting, or visited. During DFS, mark the current node as visiting and recursively explore its neighbors. If you encounter another visiting node, a cycle exists and scheduling is impossible.

After exploring all neighbors, mark the node as visited and push it into the result list. The final ordering is obtained by reversing the post-order traversal. This method naturally constructs a topological ordering while ensuring cycles are detected during recursion.

Recommended for interviews: Kahn’s Algorithm (BFS topological sort) is usually the expected solution because it clearly models prerequisite counts and processes nodes in dependency order. DFS with cycle detection demonstrates deeper understanding of graph traversal and recursion. Showing both approaches signals strong command of topological sorting problems.

Approach 1: Topological Sort using Kahn's Algorithm

Consider courses as nodes in a directed graph, and prerequisites as directed edges. We can apply Kahn's algorithm for topological sorting to find the order of courses to take. The algorithm works by using an in-degree array that tracks the number of prerequisites for each course. Courses with zero in-degrees can be taken immediately. As our course order is populated, we decrement the in-degree of their dependent courses, allowing them to be taken in subsequent steps.

This solution uses a breadth-first search (BFS) starting from courses with zero prerequisites. As courses are completed, they are removed from their neighbors' prerequisites, enabling further courses to be completed in order. This ensures the result represents a valid topological sort of the course schedule.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(V + E), where V is the number of courses, and E is the number of prerequisites.
Space Complexity: O(V + E), where V and E account for the graph and the in-degree array.

Try this approach in the editor →

Approach 2: DFS with Cycle Detection

Similar to the Kahn's algorithm approach, but using a depth-first search (DFS) to detect cycles and determine the order of courses. In this method, courses are visited, and if a course is revisited while still in the recursion stack, it indicates a cycle, making course completion impossible. The order is determined by recording the exit point of each node during the DFS.

The Java solution implements DFS to perform topological sorting while checking for cycles in the graph. During the recursive traversal, we maintain a recursion stack to detect back-edges, alerting us to any cycles in the graph.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(V + E), where V is the number of courses, and E is the number of prerequisites.
Space Complexity: O(V + E), where V and E account for the graph structure and visited array.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Topological Sort using Kahn's Algorithm

Time Complexity: O(V + E), where V is the number of courses, and E is the number of prerequisites.
Space Complexity: O(V + E), where V and E account for the graph and the in-degree array.

DFS with Cycle Detection

Time Complexity: O(V + E), where V is the number of courses, and E is the number of prerequisites.
Space Complexity: O(V + E), where V and E account for the graph structure and visited array.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Topological Sort (Kahn's Algorithm / BFS)O(V + E)O(V + E)Most common interview solution; easy way to process nodes with zero prerequisites
DFS with Cycle DetectionO(V + E)O(V + E)When using recursive graph traversal or when detecting cycles during DFS

Video Solution

Course Schedule II - Topological Sort - Leetcode 210 • NeetCode • 245,772 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Course Schedule II easy or hard?
Course Schedule II is considered a Medium difficulty problem. The main challenge is recognizing that the prerequisites form a directed graph and that the solution requires topological sorting with cycle detection.
Course Schedule II Python/Java solution
Python solutions typically implement Kahn's Algorithm using collections.deque for the queue and adjacency lists for edges. Java implementations often use ArrayList for the graph and either a Queue for BFS or recursion for DFS cycle detection. Both approaches run in O(V + E) time.
How to solve Course Schedule II in O(n)?
Model the input as a directed graph and perform topological sorting. Using Kahn's Algorithm, compute indegrees for all nodes, push zero‑indegree nodes into a queue, and iteratively remove them while updating neighbors. Because each edge and node is processed once, the runtime becomes O(V + E).
What is the best approach for Course Schedule II?
Topological sorting using Kahn's Algorithm (BFS) is the most common solution. It tracks the number of prerequisites for each course using an indegree array and processes courses with zero prerequisites first. The algorithm runs in O(V + E) time where V is the number of courses and E is the number of prerequisite relations.
Is Course Schedule II asked at Google/Amazon/Meta?
Course Schedule II is a well-known graph interview question and variations appear in interviews at companies like Amazon, Google, and Meta. It tests understanding of topological sorting, dependency graphs, and cycle detection in directed graphs.
What data structure is used in Course Schedule II?
The core structure is a directed graph represented using an adjacency list. Kahn's Algorithm additionally uses an indegree array and a queue for BFS processing. DFS solutions use recursion and a state array to track visiting and visited nodes for cycle detection.
What is the time complexity of Course Schedule II?
Both common solutions run in O(V + E) time where V represents courses and E represents prerequisite edges. Each node and edge is processed at most once during BFS or DFS traversal. Space complexity is also O(V + E) due to the adjacency list and auxiliary structures like queues or recursion stacks.

Ready to solve this problem?

Practice Course Schedule II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Alien Dictionary

Next

Build a Matrix With Conditions