The O(n) Club: Course Schedule II’s Topological Soap Opera

The O(n) Club: Course Schedule II’s Topological Soap Opera

⚡ TL;DR

LeetCode 210 is just course scheduling pretending to be about academics. The real star? Topological sort—the thing that lets you untangle prerequisite spaghetti. Here’s how the BFS (a.k.a. Kahn’s Algorithm) approach looks in Java when you haven’t had enough coffee:

// Find course order with Kahn's Algorithm
public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<list>> graph = new ArrayList<>();
    int[] indegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
    for (int[] pair : prerequisites) {
        graph.get(pair[1]).add(pair[0]);
        indegree[pair[0]]++;
    }
    Queue
<integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) queue.offer(i);
    int[] order = new int[numCourses]; int idx = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        order[idx++] = course;
        for (int next : graph.get(course)) if (--indegree[next] == 0) queue.offer(next);
    }
    return idx == numCourses ? order : new int[0];
}
</integer></list>

🧠 How Devs Usually Mess This Up

Panic-writing brute force? Welcome to common mistakes:

• Assume it’s a tree: Sorry, college isn’t that tidy. Some courses have multiple prerequisites. It’s a graph, not your grandma’s family tree.
• Missing cycles: Get stuck in “A before B before C before A” and you’re basically starring in a dystopian academic sitcom. No graduation for you.
• Ignoring lonely courses: Some have zero prerequisites. Don’t demand an ancestor for lone wolves—they won’t RSVP anyway.
• Expecting one correct answer: There are as many right orders as there are ways to pronounce “queue.” Any valid itinerary works, not just the one in the example output.

🔍 What’s Actually Going On

Picture a college course catalog as a Directed Acyclic Graph (DAG), which is nerd for “big bowl of dependency noodles.” Every course is a node, every prerequisite is a directed edge. If the graph has no cycles, you can schedule everything—otherwise, your advisor will recommend existential philosophy and wish you luck.
Topological sort untangles this mess: it identifies which classes you can start (no prereqs), and repeatedly “takes” them, unlocking other classes until you’re either done or hopelessly deadlocked in an academic loop.

🛠️ PseudoCode

• Build the graph:

  For each [next, prev] in prerequisites:
    graph[prev] = list of courses unlocked after prev
    indegree[next]++

  Every course, every arrow. Count number of arrows pointing to each course.

• Find courses with zero prerequisites:

  For each course c:
    if indegree[c] == 0: queue.offer(c)

  All the “freebies” that let you get started—no strings attached, for now.

• Process courses:

  While queue not empty:
    take = queue.poll()
    add take to result
    for each neighbor in graph[take]:
      indegree[neighbor]--
      if indegree[neighbor] == 0:
        queue.offer(neighbor)

  It’s basically a school version of whack-a-mole, but with fewer tickets.

• Check for cycles:

  If result.length == numCourses:
    return result
  else:
    return []  // Caught in an infinite loop. Time to change majors?

  If you scheduled everything—congrats! If not, you found a cycle and everyone drops out.

💻 The Code

// The straight-shooting BFS topological sort
public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<list>> graph = new ArrayList<>();
    int[] indegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
    for (int[] pair : prerequisites) {
        graph.get(pair[1]).add(pair[0]);
        indegree[pair[0]]++;
    }
    Queue
<integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) queue.offer(i);
    int[] order = new int[numCourses];
    int idx = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        order[idx++] = course;
        for (int next : graph.get(course)) {
            if (--indegree[next] == 0) queue.offer(next);
        }
    }
    return idx == numCourses ? order : new int[0];
}
</integer></list>

⚠️ Pitfalls, Traps & Runtime Smacks

• Cycles: Circles of doom in your graph. Detect and bail early, or prepare for algorithmic heartache.
• Disconnected courses: Input might have several islands—your code must cover the whole archipelago, not just the one with palm trees.
• Multiple valid orders: Trust the algorithm—don’t sweat over a single sequence.
• Complexity: Performance is O(V + E). Unless you’re planning every course ever offered worldwide, this is a non-issue.
• Space: Yes, storing the graph and indegrees uses space. No, Java will not burst into flames.

🧠 Interviewer Brain-Tattoo

“Topological sort: because even dependency chaos can have order—unless cycles send you back to academic Groundhog Day.”