Skip to main content

14. Course Schedule

mediumAsked at GitHub

Topological sort / cycle detection on a directed graph, directly modeling how GitHub Actions resolves job dependencies and detects circular workflow references.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given numCourses and prerequisites pairs [a, b] meaning 'take b before a', determine whether it is possible to finish all courses (i.e., the graph is acyclic).

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2

Examples

Example 1

Input
numCourses = 2, prerequisites = [[1,0]]
Output
true

Example 2

Input
numCourses = 2, prerequisites = [[1,0],[0,1]]
Output
false

Approaches

1. DFS with three-color marking

Mark nodes as unvisited/visiting/visited; a back-edge (visiting→visiting) signals a cycle.

Time
O(V+E)
Space
O(V+E)
// Colors: 0=unvisited, 1=visiting, 2=done
// DFS: if we hit a node with color 1, return false (cycle)
// if all DFS calls return true, return true

Tradeoff:

2. Kahn's BFS topological sort

Compute in-degrees for all nodes, enqueue zero-in-degree nodes, process them reducing neighbors' in-degrees. If we process all numCourses nodes, no cycle exists.

Time
O(V+E)
Space
O(V+E)
function canFinish(numCourses, prerequisites) {
  const inDegree = new Array(numCourses).fill(0);
  const adj = Array.from({length: numCourses}, () => []);
  for (const [a, b] of prerequisites) {
    adj[b].push(a);
    inDegree[a]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (inDegree[i] === 0) queue.push(i);
  let processed = 0;
  while (queue.length) {
    const node = queue.shift();
    processed++;
    for (const next of adj[node]) {
      inDegree[next]--;
      if (inDegree[next] === 0) queue.push(next);
    }
  }
  return processed === numCourses;
}

Tradeoff:

GitHub-specific tips

GitHub's CI/CD pipeline resolution is exactly this problem — mention dependency graph validation for GitHub Actions jobs and how circular `needs:` references are rejected at parse time.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Course Schedule and other GitHub interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →