Domain 2MediumCORE

Course Schedule II

We are given numCourses and a list of prerequisite pairs [a, b], where taking course b is required before taking course a. This defines a directed graph where an edge exists from b -> a. The goal is to find a linear ordering (topological sort) such that for every pair (u, v) in the prerequisites list, node v appears before node u in our output. If no such valid order exists—specifically if there is a cycle—we must return an empty array.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Depth-first Search#Breadth-first Search#Graph#Topological Sort

210. Course Schedule II

Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search,Graph,Topological Sort
FAANG asked: 1
Acceptance rate: 42.9%


Problem Breakdown

We are given numCourses and a list of prerequisite pairs [a, b], where taking course b is required before taking course a. This defines a directed graph where an edge exists from b -> a. The goal is to find a linear ordering (topological sort) such that for every pair (u, v) in the prerequisites list, node v appears before node u in our output. If no such valid order exists—specifically if there is a cycle—we must return an empty array.

Inputs:

  • numCourses: Integer (1 to 2000).
  • prerequisites: List of pairs [a, b].

Outputs:

  • A list representing the course ordering.
  • Empty list [] if a cycle exists or courses cannot be completed.

Implicit Constraints & Edge Cases:

  • Cycles: If there is a circular dependency (e.g., 0 needs 1, and 1 needs 0), it’s impossible to finish all courses.
  • Disconnected Components: Some courses might have no prerequisites at all; they should be included in the order naturally.
  • Single Course: Valid even with empty prerequisite list.

Intuition

A naive approach would try every possible permutation of course orders and check validity, which is O(N!)O(N!)—far too slow for numCourses up to 2000. We need a more efficient way to respect dependencies.

The core insight here is that this problem maps directly to Topological Sorting. If we view courses as nodes in a directed graph and prerequisites as edges, the solution exists if and only if the graph contains no cycles (i.e., it’s a Directed Acyclic Graph or DAG).

To find an ordering:

  1. We must process any course that has no pending dependencies first. In graph terms, these are nodes with an in-degree of 0.
  2. Once we “take” such a course, its dependent courses lose one prerequisite requirement (their in-degree decreases by 1). If a dependent course’s prerequisites drop to zero, it becomes available for processing next.

This suggests a Breadth-First Search (BFS) approach using Kahn’s Algorithm rather than Depth-First Search (DFS), as BFS naturally handles the “available now” logic via a queue and makes cycle detection explicit by checking if we processed all nodes.

Approach

  1. Graph Construction: Build an adjacency list to represent the graph where adj[b] contains neighbors [a]. Simultaneously, calculate the in-degree (number of prerequisites) for every course.
  2. Initialization: Create a queue and add all courses with an initial in-degree of 0 into it. These are our starting points.
  3. Processing Loop: While the queue is not empty:
    • Dequeue a node u. Add u to our result list (this represents taking course u).
    • For every neighbor v connected from u:
      • Decrement in_degree[v].
      • If in_degree[v] == 0, enqueue v.
  4. Cycle Check: After the loop, compare the length of our result list to numCourses. If they match, we found a valid topological order. If not (result is shorter), it means some nodes were never reachable because they are part of a cycle; return an empty array in that case.

Complexity Analysis

  • Time: O(V+E)O(V + E) where VV is numCourses and EE is the number of prerequisites. We iterate through each node once to initialize, then visit every edge exactly once during processing. Given constraints (N≤2000N \le 2000), this fits well within time limits.
  • Space: O(V+E)O(V + E) required for storing the adjacency list and in-degree array. The queue uses at most O(V)O(V).

Solution

from collections import deque, defaultdict

def findOrder(numCourses: int, prerequisites):
    # Build graph (adjacency list) and calculate in-degrees
    adj = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses
    
    for course_a, prereq_b in prerequisites:
        # Edge from prerequisite to dependent course
        adj[prereq_b].append(course_a)
        in_degree[course_a] += 1
        
    queue = deque()
    
    # Initialize with all courses having no prerequisites (in-degree == 0)
    for i in range(numCourses):
        if in_degree[i] == 0:
            queue.append(i)
            
    result = []
    
    while queue:
        u = queue.popleft()
        result.append(u)
        
        # Visit neighbors (courses that depend on current course 'u')
        for v in adj[u]:
            in_degree[v] -= 1
            
            # If all prerequisites are met, add to queue
            if in_degree[v] == 0:
                queue.append(v)
                
    # Check if we were able to order all courses (no cycle detected)
    return result if len(result) == numCourses else []

# Example usage for verification
print(findOrder(2, [[1,0]]))      # Output: [0, 1]
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]])) # Output: [0, 1, 2, 3] or similar valid order

Edge Cases Handled

  • No Prerequisites: All nodes start with in-degree 0. The queue processes them sequentially (order arbitrary but valid). Returns [0, 1, ..., n-1].
  • Cycle Detected: If a cycle exists, the loop terminates before all numCourses are added to result. We check len(result) == numCourses and return empty list if false.
  • Disconnected Graphs: Courses with no edges (isolated nodes) have in-degree 0 initially and get processed immediately alongside others, ensuring they appear in the output correctly without affecting dependency logic for other components.