Course Schedule (LC 207)

Pattern: Directed graph — Cycle detection / Topological sort
Difficulty: Medium
Key Concept: If you can order all courses respecting prerequisites, the prerequisite graph is a DAG; if there is a cycle, some course depends on itself indirectly and completion is impossible.

Problem Statement

You must take numCourses labeled 0 .. numCourses-1. You are given prerequisites where prerequisites[i] = [a, b] means: to take course a, you must first finish course b (edge b → a).

Return true if you can finish all courses; otherwise false.

Input: int numCourses, int[][] prerequisites
Output: boolean

Example: numCourses = 2, prerequisites = [[1,0]] → take 0 then 1 → true.
[[1,0],[0,1]] → cycle → false.

---

1. Algorithm & Pseudocode

Brute force

1. Try every permutation of course order (or repeatedly pick any valid next course without a global plan).
2. Check each permutation against all prerequisites.

Why bad: Factorial/exponential; impractical for numCourses up to 5000.

Optimal

A) DFS — three colors (state per node)

build adjacency list for b -> a edges (must complete b before a)

state[i] in {0=unvisited, 1=visiting, 2=done}

dfs(u):
  if state[u] == 1: cycle -> return false
  if state[u] == 2: return true
  state[u] = 1
  for each v in adj[u]:
    if !dfs(v): return false
  state[u] = 2
  return true

for each course c:
  if state[c] == 0 and !dfs(c): return false
return true

B) Kahn’s algorithm (BFS indegree)

indegree[v] = count of prerequisites still needed
queue all v with indegree[v] == 0
taken = 0
while queue not empty:
  u = pop
  taken++
  for each v in adj[u]:
    indegree[v]--
    if indegree[v] == 0: push v

return taken == numCourses

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Model b → a: “b comes before a.” The graph is directed.
• Cycle = deadlock: Along a cycle, every course waits on another; no starting point.
• DFS “visiting” flag: If you reach a node still on the current recursion path, you found a back edge → cycle.
• Kahn: Peeling off nodes with no remaining prerequisites is topological order; if you cannot peel all nodes, a cycle remains.

---

3. The Dry Run

numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]] → chain 0→1→2→3 (edges: 0→1, 1→2, 2→3).

Kahn

Step	Queue (indegree 0)	Popped	indegree update	taken
init	[0]	—	—	0
1	[1]	0	1: 0→0	1
2	[2]	1	2: 0	2
3	[3]	2	3: 0	3
4	[]	3	—	4

taken == 4 → true.

Cycle example [[0,1],[1,0]]: edges 1→0 and 0→1. Indegrees: both 1. Queue empty → taken = 0 → false.

---

4. Java Solution

Brute Force

import java.util.*;

class SolutionBrute {
    // Exponential: try all topological orderings via backtracking — NOT suitable for constraints
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] adj = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) adj[i] = new ArrayList<>();
        int[] indeg = new int[numCourses];
        for (int[] e : prerequisites) {
            int a = e[0], b = e[1];
            adj[b].add(a);
            indeg[a]++;
        }
        return dfsAllOrders(adj, indeg.clone(), new boolean[numCourses], 0, numCourses);
    }

    private boolean dfsAllOrders(List<Integer>[] adj, int[] indeg, boolean[] onPath, int taken, int n) {
        if (taken == n) return true;
        for (int i = 0; i < n; i++) {
            if (indeg[i] != 0 || onPath[i]) continue;
            onPath[i] = true;
            for (int v : adj[i]) indeg[v]--;
            if (dfsAllOrders(adj, indeg, onPath, taken + 1, n)) return true;
            for (int v : adj[i]) indeg[v]++;
            onPath[i] = false;
        }
        return false;
    }
}

Time: Worst-case exponential.
Space: O(V + E) for graph + recursion.

Optimal

DFS three-state

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] adj = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) adj[i] = new ArrayList<>();
        for (int[] e : prerequisites) {
            adj[e[1]].add(e[0]); // b -> a
        }

        int[] state = new int[numCourses]; // 0 unvisited, 1 visiting, 2 done

        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0 && hasCycle(i, adj, state)) return false;
        }
        return true;
    }

    private boolean hasCycle(int u, List<Integer>[] adj, int[] state) {
        state[u] = 1;
        for (int v : adj[u]) {
            if (state[v] == 1) return true;
            if (state[v] == 0 && hasCycle(v, adj, state)) return true;
        }
        state[u] = 2;
        return false;
    }
}

Kahn BFS

import java.util.*;

class SolutionKahn {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] adj = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) adj[i] = new ArrayList<>();
        int[] indeg = new int[numCourses];
        for (int[] e : prerequisites) {
            int a = e[0], b = e[1];
            adj[b].add(a);
            indeg[a]++;
        }

        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0) q.add(i);
        }

        int taken = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            taken++;
            for (int v : adj[u]) {
                if (--indeg[v] == 0) q.add(v);
            }
        }
        return taken == numCourses;
    }
}

DFS: Time O(V + E), Space O(V + E).
Kahn: Same time; space O(V) for queue and indegrees.

---

5. The “Java vs. Others” Edge

• List<Integer>[] adj = new ArrayList[n] is the standard Java pattern; generic array creation is disallowed, so use @SuppressWarnings("unchecked") in production if needed.
• ArrayDeque<Integer> for Kahn’s queue.
• Bit-packed states could shrink memory, but int[] with 0/1/2 is clearer in interviews.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute backtracking orders	Exponential	O(V + E)	Illustrative only
DFS 3-color / Kahn	O(V + E)	O(V + E)	Both standard

---

ASCII: DAG vs cycle

DAG (can finish):          Cycle (cannot):

   0 --> 1 --> 2              0 ----> 1
                              ^       |
                              |       v
                              +---<---+