Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 210. Course Schedule II

Given numCourses and prerequisite pairs, return any ordering of courses that satisfies all prerequisites or an empty array if impossible — this is essentially computing a topological sort of a directed graph and detecting cycles.

Asked at:

DESCRIPTION

Input:

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

Output:

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

Explanation: Course 0 has no prerequisites. After taking 0, courses 1 and 2 become available. After taking both 1 and 2, course 3 becomes available. Multiple valid orderings exist.

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All prerequisite pairs are unique
No self-loops (a course cannot be a prerequisite of itself)

Understanding the Problem

Let's understand what we're being asked to do. We have numCourses courses labeled from 0 to numCourses-1, and a list of prerequisite pairs like [[1,0], [2,1]].

Each pair [a, b] means: to take course a, you must first complete course b. So [1,0] means course 0 is a prerequisite for course 1.

For example, with numCourses=4 and prerequisites=[[1,0], [2,0], [3,1], [3,2]], one valid ordering is [0,1,2,3] or [0,2,1,3]. Course 0 has no prerequisites (can start immediately), courses 1 and 2 both require course 0, and course 3 requires both 1 and 2.

Critical constraint: If there's a cycle (like [[1,0], [0,1]]), it's impossible to complete all courses, so return an empty array [].

Edge cases to consider: What if there are no prerequisites? (any order works). What if a course has multiple prerequisites? What if the graph is disconnected (some courses have no relation to others)?

Building Intuition

Think of this as a dependency graph: each course is a node, and each prerequisite creates a directed edge. Course a depends on course b means there's an edge from b to a.

The key insight: we can only take a course when all its prerequisites are completed. This means we should process courses with zero remaining prerequisites first, then remove them from the graph, which may free up other courses.

By repeatedly selecting courses with no remaining prerequisites, we naturally build a valid ordering. If at any point we can't find such a course but haven't processed all courses yet, we've detected a cycle (circular dependency).

This approach processes each course exactly once and checks each prerequisite edge exactly once, making it very efficient.

Imagine you're planning your college schedule. Some classes require prerequisites:

Math 101 has no prerequisites (take it first!)
Physics 201 requires Math 101
Chemistry 201 also requires Math 101
Advanced Physics 301 requires Physics 201

You'd naturally take Math 101 first (no dependencies), then Physics 201 and Chemistry 201 become available (their only dependency is satisfied), and finally Advanced Physics 301.

But what if Math 101 required Physics 201, and Physics 201 required Math 101? You'd be stuck - that's a cycle, making it impossible to complete both courses.

Common Mistakes

Confusing the direction of edges: [a,b] means b -> a (b is prerequisite of a), not a -> b. Building the graph incorrectly leads to wrong orderings.

Forgetting to check if all courses were processed: if the result array has fewer than numCourses elements, a cycle exists. Simply returning the partial result is incorrect.

Not handling disconnected components: some courses may have no prerequisites and no dependents. They should still be included in the result.

Modifying in-degree counts incorrectly: only decrement in-degree when processing a course's neighbors, not when adding to the queue. Decrementing too early can cause incorrect cycle detection.

Using the wrong data structure: trying to use DFS without proper visited/recursion stack tracking can miss cycles or produce incorrect orderings.

Optimal Solution

The optimal approach uses Kahn's algorithm for topological sorting with BFS. First, build an adjacency list representing the course dependency graph and count the in-degree (number of prerequisites) for each course. Initialize a queue with all courses that have zero in-degree (no prerequisites). Process courses from the queue one by one: add each to the result ordering, and for each course that depends on it, decrement its in-degree. When a course's in-degree reaches zero, add it to the queue. If we process all courses, return the ordering; otherwise, a cycle exists, so return an empty array.

Visualization

from collections import deque, defaultdict
def find_order(numCourses, prerequisites):
    """
    Find a valid course ordering using topological sort (Kahn's algorithm).
    Returns ordering if possible, empty list if cycle exists.
    """
    # Build adjacency list and in-degree count
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    # Initialize queue with courses having no prerequisites
    queue = deque()
    for course in range(numCourses):
        if in_degree[course] == 0:
            queue.append(course)
    
    # Process courses in topological order
    result = []
    
    while queue:
        current = queue.popleft()
        result.append(current)
        
        # Reduce in-degree for dependent courses
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check if all courses were processed (no cycle)
    if len(result) == numCourses:
        return result
    else:
        return []

Start topological sort using Kahn's algorithm

0 / 28

Test Your Knowledge

Complexity Analysis

Time Complexity: O(V + E) We visit each course (vertex) once and examine each prerequisite (edge) once. V is the number of courses, E is the number of prerequisite pairs.

Space Complexity: O(V + E) We store the adjacency list (O(E) space for edges), in-degree array (O(V) space), queue (O(V) worst case), and result array (O(V) space).

What We've Learned

Topological sort for dependency resolution: When you see prerequisites, dependencies, or ordering constraints between items, think topological sort - it's specifically designed to linearize directed acyclic graphs (DAGs) where some elements must come before others.
Kahn's algorithm with in-degree tracking: Maintain an in-degree array counting incoming edges for each node, then use a queue to process all nodes with in-degree 0 - this BFS approach naturally builds the ordering while detecting cycles when fewer than numCourses nodes are processed.
Cycle detection through count verification: After processing, if your result contains fewer elements than the total number of nodes, a cycle exists - this works because nodes in a cycle will never reach in-degree 0, making them impossible to process.
Adjacency list construction pattern: Build the graph as Map<prerequisite, List<courses>> where each prerequisite points to courses it unlocks - this forward direction makes it efficient to decrement in-degrees of dependent courses as you process each node.
Queue-based level processing: Using a queue (not stack) ensures you process all available courses at each level before moving to newly unlocked courses - this guarantees a valid topological ordering and runs in O(V + E) time with O(V + E) space for the graph structure.
Real-world scheduling applications: This exact pattern solves build systems (compile dependencies), task scheduling (project management), package managers (npm, pip dependencies), and course planning - any system where tasks have prerequisite relationships needs topological sorting.

Test Your Understanding

Why is graph the right data structure for this problem?

graph provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid December, 2025

Intuit

Senior

Interview was for the Quickbooks team, reworded Course Schedule II question https://leetcode.com/problems/course-schedule-ii/

Mid October, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More