The O(n) Club: Course Schedule (LeetCode 207): How Not to Major in Infinite Loops

The O(n) Club: Course Schedule (LeetCode 207): How Not to Major in Infinite Loops

⚡ TL;DR

This is a “can you finish all your courses” problem, which is code for “does your graph have a cycle?” Brute force? Sure, if you enjoy stack overflows and existential dread.

// Bad idea: blindly check all combos
boolean canFinish(int numCourses, int[][] prerequisites) {
    // Scream quietly while you try to brute-force dependencies
}

🧠 How Devs Usually Mess This Up

Common detours on the road to despair:

• Treating the prerequisite list like a tree. Sorry, friend: this party has disconnected floors, loops, and secret trapdoors.
• Ignoring direction. [a, b] means “b before a”—flip it at your peril.
• One DFS for the whole thing? Unless your courses are in a cult, you’ll need to check every disconnected cluster.

🔍 What’s Actually Going On

Imagine a university where “Algorithms” is required for “Data Structures,” which is required for “Advanced Algorithms,” which is required for… “Algorithms.” Welcome to Sisyphean Studies!

We’re dealing with a directed graph: nodes as courses, edges as prerequisites. The only way you can finish is if these dependencies don’t create a single, nasty cycle—because once you’re caught, you never graduate.

The solution? Topological sort (Kahn’s Algorithm) or DFS cycle-checking. Either way, you make sure there are no loops tying your shoelaces together.

🛠️ PseudoCode

• Build adjacency lists for courses and prerequisites.

  List<Integer>[] graph = new List[numCourses];

• Track state: 0 = unvisited, 1 = visiting, 2 = totally done.

  int[] state = new int[numCourses];

• DFS for every course:
  • If you see a course marked as ‘visiting’, congrats: you found a cycle.
  • If you see ‘visited’, skip—your job here is done.

  boolean dfs(int course) {
      if (state[course] == 1) return false;
      if (state[course] == 2) return true;
      state[course] = 1;
      for (int dep : graph[course]) if (!dfs(dep)) return false;
      state[course] = 2;
      return true;
  }

• Don’t trust the graph to be whole— check every course:

  for (int i = 0; i < numCourses; i++)
      if (!dfs(i)) return false;
  return true;

💻 The Code

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++)
            graph[i] = new ArrayList<>();
        for (int[] p : prerequisites)
            graph[p[1]].add(p[0]);
        int[] state = new int[numCourses];
        for (int i = 0; i < numCourses; i++)
            if (!dfs(i, graph, state)) return false;
        return true;
    }
    private boolean dfs(int node, List<Integer>[] graph, int[] state) {
        if (state[node] == 1) return false;
        if (state[node] == 2) return true;
        state[node] = 1;
        for (int next : graph[node])
            if (!dfs(next, graph, state)) return false;
        state[node] = 2;
        return true;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge cases galore: Single course? Empty prereqs? Self-loops or ten disconnected mini-cycles? Test them all.
• Direction confusion: [a, b] really means “do b, then a.” That little arrow is never mutual.
• Complexity check: You’ll touch every node and edge—O(V + E). No ninja tricks, just clean graph crawling.

🧠 Interviewer Brain-Tattoo

“If your curriculum has a cycle, you might as well sign up for Endless Loops 101.”