Leetcode 210. Course Schedule II

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)?

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.

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.

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 []

• 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.