21. Course Schedule

mediumAsked at Postman

Decide whether all courses can be completed given prerequisite pairs (cycle detection).

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

There are numCourses labeled 0..numCourses-1. You are given an array prerequisites where prerequisites[i] = [a, b] means you must take b before a. Return true if you can finish all courses.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
All pairs are distinct

Examples

Example 1

Input

numCourses = 2, prereq = [[1,0]]

Output

true

Example 2

Input

numCourses = 2, prereq = [[1,0],[0,1]]

Output

false

Approaches

1. DFS with 3-color marking

Mark nodes WHITE/GREY/BLACK; a back-edge to GREY means a cycle.

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

// recursive dfs; if encounter GREY return false; mark BLACK after

Tradeoff:

2. Kahn topological sort

Compute in-degrees, queue all zero-in-degree nodes, pop them and decrement their successors. If you process all nodes, no cycle.

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

function canFinish(n, pre) {
  const deg = new Array(n).fill(0);
  const adj = Array.from({length: n}, () => []);
  for (const [a, b] of pre) { adj[b].push(a); deg[a]++; }
  const q = [];
  for (let i = 0; i < n; i++) if (deg[i] === 0) q.push(i);
  let seen = 0;
  while (q.length) {
    const u = q.shift(); seen++;
    for (const v of adj[u]) if (--deg[v] === 0) q.push(v);
  }
  return seen === n;
}

Tradeoff:

Postman-specific tips

Postman's Newman runner depends on resolving request dependencies via topo sort — interviewers will pivot to ordering output, so prefer Kahn for the iterative-extension story.

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

Practice these live with InterviewChamp.AI →