ProblemMediumLeetCode #2076 min read

Course Schedule

Cycle detection in a directed graph via Kahn's algorithm — the canonical topological sort problem.

graphtopological-sortbfs

Intro

You have n courses with prerequisite edges. Determine whether it's possible to finish all of them — i.e., whether the prerequisite graph is a DAG.

Key insight

Run Kahn's algorithm. If you successfully topologically sort all n nodes, no cycle exists.

Approach

1Build adjacency list and in-degree array from `prerequisites[i] = [course, pre]`.
2Push all nodes with in-degree 0 onto a queue.
3Pop u, decrement in-degree of each neighbour v; push v if in-degree becomes 0.
4Return whether the number of popped nodes equals n.

Complexity

Time

O(V + E)

Space

O(V + E)

Code

Snippetjava

boolean canFinish(int n, int[][] prereq) {
    List<List<Integer>> g = new ArrayList<>();
    int[] indeg = new int[n];
    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
    for (int[] e : prereq) { g.get(e[1]).add(e[0]); indeg[e[0]]++; }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
    int seen = 0;
    while (!q.isEmpty()) {
        int u = q.poll(); seen++;
        for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);
    }
    return seen == n;
}

Pitfalls

Confusing the direction of the prerequisite edge.
Using DFS-based cycle detection but not tracking 'on stack' state — leads to false negatives.

Variants & follow-ups

Course Schedule II (LC 210)
Alien Dictionary (LC 269)