Problem Statement

Given the number of courses and prerequisite pairs, determine if all courses can be completed.

Why This Problem Matters

• Classic application of topological sorting and cycle detection.
• Reinforces understanding of in-degree counts and graph traversal.
• Serves as the basis for scheduling and dependency resolution problems.

Thought Process

Step-by-Step Reasoning

1. Build adjacency list and in-degree array.
2. Seed queue with all nodes having in-degree zero.
3. Pop queue, decrement in-degree of neighbors; enqueue when they reach zero.
4. Return true if processed count equals numCourses.

Dry Run

Complexity Analysis

Annotated Solution

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class CourseSchedule {
  public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i += 1) {
      graph.add(new ArrayList<>());
    }

    int[] indegree = new int[numCourses];
    for (int[] edge : prerequisites) {
      int course = edge[0];
      int prereq = edge[1];
      graph.get(prereq).add(course);
      indegree[course] += 1;
    }

    ArrayDeque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i += 1) {
      if (indegree[i] == 0) {
        queue.addLast(i);
      }
    }

    int processed = 0;
    while (!queue.isEmpty()) {
      int node = queue.removeFirst();
      processed += 1;
      for (int neighbor : graph.get(node)) {
        indegree[neighbor] -= 1;
        if (indegree[neighbor] == 0) {
          queue.addLast(neighbor);
        }
      }
    }

    return processed == numCourses;
  }
}

Kahn’s algorithm systematically removes nodes without prerequisites, revealing cycles when nodes remain with non-zero in-degree.

Common Pitfalls

• Building edges in wrong direction prevents correct in-degree computations.
• Forgetting to increment processed count or to check equality leads to false positives.
• DFS alternatives require three-color marking; ignoring state leads to infinite recursion.

Follow-Up Questions

• How would you output a valid order if it exists? (Return the topological order.)
• Can you detect which courses are part of the cycle?

Key Takeaways