Skip to main content

207. Course Schedule

mediumAsked at LinkedIn

Determine if a set of courses with prerequisites can all be finished — this is cycle detection on a directed graph, the exact algorithm LinkedIn runs to validate skill-path dependency chains and surface circular credential requirements in their learning platform.

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

Problem

There are numCourses courses labeled 0 to numCourses-1. You are given an array prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses, false otherwise (i.e., detect a cycle in the directed prerequisite graph).

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= a, b < numCourses
  • All prerequisites pairs are distinct

Examples

Example 1

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

Explanation: Course 0 must be taken before 1. No cycle — both are completable.

Example 2

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

Explanation: Course 0 requires 1 and course 1 requires 0 — a cycle, so neither can be finished.

Approaches

1. DFS with 3-color cycle detection

Color each node: white (unvisited), gray (in current DFS path), black (fully processed). If DFS reaches a gray node, a cycle exists. O(V+E), but recursive — can blow stack on large inputs.

Time
O(V+E)
Space
O(V+E)
function canFinishDFS(numCourses, prerequisites) {
  const adj = Array.from({length: numCourses}, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);
  const color = new Array(numCourses).fill(0); // 0=white,1=gray,2=black
  function hasCycle(u) {
    color[u] = 1;
    for (const v of adj[u]) {
      if (color[v] === 1) return true;
      if (color[v] === 0 && hasCycle(v)) return true;
    }
    color[u] = 2;
    return false;
  }
  for (let i = 0; i < numCourses; i++) {
    if (color[i] === 0 && hasCycle(i)) return false;
  }
  return true;
}

Tradeoff:

2. Kahn's algorithm (BFS topological sort) — optimal

Build in-degree counts. Queue all zero-in-degree nodes. BFS reduces neighbors' in-degrees; re-enqueue when they hit zero. If processed count equals numCourses, no cycle exists.

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

Tradeoff:

LinkedIn-specific tips

LinkedIn prefers Kahn's BFS answer here because it matches their actual infrastructure model: skill-path validation is a queue-draining topological sort, not a recursive traversal. Name the algorithm by name — 'Kahn's algorithm' signals seniority. The follow-up is almost always Course Schedule II (LC 210): return the actual order of courses, not just a boolean. Kahn's makes that trivial — push each dequeued node into a result array.

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 LinkedIn interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →