Course Schedule

Why it belongs on this sheet

This is one of the most common directed-graph interview problems because it reduces nicely to cycle detection.

Pattern

Topological sort by indegree

Approach

Build the directed graph and count indegrees. Repeatedly take courses with zero indegree. If you can process all courses, there is no cycle.

Java solution

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

class Solution {
  public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] indegree = new int[numCourses];

    for (int i = 0; i < numCourses; i++) {
      graph.add(new ArrayList<>());
    }

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

    Deque<Integer> queue = new ArrayDeque<>();
    for (int course = 0; course < numCourses; course++) {
      if (indegree[course] == 0) {
        queue.offer(course);
      }
    }

    int completed = 0;
    while (!queue.isEmpty()) {
      int course = queue.poll();
      completed++;

      for (int next : graph.get(course)) {
        if (--indegree[next] == 0) {
          queue.offer(next);
        }
      }
    }

    return completed == numCourses;
  }
}

Complexity

• Time: O(V + E)
• Space: O(V + E)

Interview note

The problem becomes much simpler once you say "I only need to know whether a cycle exists."