How to Solve: Course Schedule (Topological Sort, Cycle Detection) – Complete Guide

How to Solve: Course Schedule (Topological Sort, Cycle Detection) – Complete Guide

? Introduction

"This pattern appears in 1 out of every 3 onsite interviews—nail it, and you prove you can model real-world dependencies, detect cycles, and optimize schedules—exactly what FAANG expects from senior engineers."

? WHAT YOU NEED TO KNOW FIRST

Before diving in, ensure you understand: 1. Graph Representations (Adjacency List vs. Matrix) 2. DFS/BFS Traversal (Visited states, recursion stack) 3. Indegree Concept (Number of incoming edges to a node)

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Repeat this checklist for every "Course Schedule" problem:

1. Model the Problem as a Graph
2. Represent courses as nodes.

3. Represent prerequisites as directed edges (A → B means A is a prerequisite for B).

4. Choose the Right Approach

5. Kahn’s Algorithm (BFS + Indegree): Best for counting courses or finding an order.

6. DFS + Cycle Detection: Best for checking feasibility (cycle = no valid order).

7. Initialize Data Structures

8. Adjacency List: graph = defaultdict(list)
9. Indegree Array: indegree = [0] numCourses

10. Visited Array (DFS): visited = [0] numCourses (0 = unvisited, 1 = processing, 2 = processed)

11. Build the Graph & Indegree

12. For each prerequisite [A, B], add B → A to the graph and increment indegree[A].

13. Execute the Algorithm

14. Kahn’s:
    • Enqueue all nodes with indegree = 0.
    • While queue is not empty:
    • Dequeue a node, add to result.
    • For each neighbor, decrement indegree. If indegree = 0, enqueue.

15. DFS:

    • For each unvisited node, run DFS.
    • If a node is encountered again in the current recursion stack (visited[node] == 1), a cycle exists.

16. Check for Cycles (DFS) or Valid Order (Kahn’s)

17. DFS: If cycle detected, return False.

18. Kahn’s: If result length ≠ numCourses, cycle exists.

19. Return the Result

20. Feasibility Check: Return True/False.
21. Ordering: Return the topological sort.

? WORKED EXAMPLES

Example 1 – Basic (LeetCode 207: Course Schedule)

Problem: Can you finish all courses given prerequisites? Return True if possible, else False.

Framework Application: 1. Model as Graph:
- numCourses = 2, prerequisites = [[1,0]] → 0 → 1. 2. Choose Approach: DFS (cycle detection). 3. Initialize:
- graph = {0: [1], 1: []}
- visited = [0, 0] 4. Build Graph: Already done. 5. DFS:
- Start at 0:
- visited[0] = 1 (processing).
- Visit 1:
- visited[1] = 1.
- No neighbors → backtrack, mark 1 as processed (visited[1] = 2).
- Backtrack, mark 0 as processed (visited[0] = 2). 6. Check Cycle: No cycle → return True.

Code (DFS):

def canFinish(numCourses, prerequisites):

    graph = defaultdict(list)

    for a, b in prerequisites:

        graph[b].append(a)


    visited = [0]  numCourses  # 0=unvisited, 1=processing, 2=processed


    def has_cycle(node):

        if visited[node] == 1:

            return True

        if visited[node] == 2:

            return False

        visited[node] = 1

        for neighbor in graph[node]:

            if has_cycle(neighbor):

                return True

        visited[node] = 2

        return False


    for node in range(numCourses):

        if has_cycle(node):

            return False

    return True

Time Complexity: O(V + E) (nodes + edges). Space Complexity: O(V + E) (graph + recursion stack).

Why This Works: - DFS detects cycles by tracking nodes in the current recursion stack (visited[node] == 1). - If a node is revisited while still processing, a cycle exists.

Example 2 – Medium (LeetCode 210: Course Schedule II)

Problem: Return an order of courses to take, or [] if impossible.

Framework Application: 1. Model as Graph: Same as Example 1. 2. Choose Approach: Kahn’s (BFS + Indegree). 3. Initialize:
- graph = {0: [1], 1: []}
- indegree = [0, 1]
- queue = deque([0]) 4. Build Graph: Already done. 5. Kahn’s:
- Dequeue 0, add to result.
- Decrement indegree[1] → indegree[1] = 0.
- Enqueue 1, dequeue 1, add to result. 6. Check Validity: Result length = numCourses → return [0, 1].

Code (Kahn’s):

from collections import deque

def findOrder(numCourses, prerequisites):

    graph = defaultdict(list)

    indegree = [0]  numCourses

    for a, b in prerequisites:

        graph[b].append(a)

        indegree[a] += 1


    queue = deque([node for node in range(numCourses) if indegree[node] == 0])

    result = []


    while queue:

        node = queue.popleft()

        result.append(node)

        for neighbor in graph[node]:

            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:

                queue.append(neighbor)


    return result if len(result) == numCourses else []

Time Complexity: O(V + E). Space Complexity: O(V + E).

Why This Works: - Kahn’s processes nodes with no dependencies first, ensuring a valid order. - If the result length ≠ numCourses, a cycle exists.

Example 3 – Hard/Follow-up (LeetCode 630: Course Schedule III)

Problem: Given courses with [duration, lastDay], return the max number of courses you can take without overlapping.

Framework Application: 1. Model as Graph: Not a direct topological sort, but uses greedy + priority queue. 2. Key Insight:
- Sort courses by lastDay.
- Use a max-heap to track durations.
- If adding a course exceeds lastDay, remove the longest course in the heap. 3. Algorithm:
- Sort courses by lastDay.
- Iterate, adding durations to a max-heap.
- If current_time + duration > lastDay, pop the longest course.

Code:

import heapq

def scheduleCourse(courses):

    courses.sort(key=lambda x: x[1])  # Sort by lastDay

    max_heap = []

    current_time = 0


    for duration, lastDay in courses:

        if current_time + duration <= lastDay:

            heapq.heappush(max_heap, -duration)

            current_time += duration

        elif max_heap and -max_heap[0] > duration:

            longest = -heapq.heappop(max_heap)

            current_time -= longest

            heapq.heappush(max_heap, -duration)

            current_time += duration


    return len(max_heap)

Time Complexity: O(N log N) (sorting + heap operations). Space Complexity: O(N) (heap).

Why This Works: - Greedy choice: Always prioritize courses with earlier deadlines. - Max-heap ensures we replace the longest course if needed.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. For ‘Course Schedule’ problems, always:

1. Model the problem as a graph—courses are nodes, prerequisites are edges.
2. Choose your weapon:
3. DFS + cycle detection if you need to check feasibility.
4. Kahn’s (BFS + indegree) if you need an order.
5. Initialize your tools:
6. Adjacency list for the graph.
7. Indegree array for Kahn’s.
8. Visited array for DFS.
9. Build the graph—don’t mix up A → B vs B → A.
10. Run the algorithm:
11. For DFS, track recursion stack to detect cycles.
12. For Kahn’s, process nodes with indegree = 0 first.
13. Check your result:
14. DFS: Cycle = False.
15. Kahn’s: Order length ≠ numCourses = cycle.
16. Handle edge cases—empty prerequisites, disconnected graphs.

You’ve got this. Walk in, sketch the graph, and crush it. Good luck!

Final Note: Practice with variations (e.g., weighted courses, parallel processing). The framework is your safety net—use it every time.