16. Course Schedule

mediumAsked at N26

Decide whether you can finish all courses given prerequisite pairs - really a cycle-detection question on a directed graph. N26 ports this to detecting circular dependencies in KYC verification step graphs.

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

Problem

There are numCourses labeled 0..numCourses-1 and a list of prerequisite pairs [a, b] meaning b must be taken before a. Return true if all courses can be finished.

Constraints

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

Examples

Example 1

Input

n=2, prereqs=[[1,0]]

Output

true

Example 2

Input

n=2, prereqs=[[1,0],[0,1]]

Output

false

Approaches

1. DFS with three-state visited

Mark each node UNVISITED / VISITING / DONE; hitting a VISITING node mid-DFS means a back edge and a cycle.

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

// graph[u] = list of dependents.
// state[v]: 0 unvisited, 1 visiting, 2 done.
// dfs(v): if state[v]===1 return false (cycle).
// recurse on neighbors, then state[v]=2.

Tradeoff:

2. Kahn's algorithm (BFS topological sort)

Compute in-degrees; repeatedly pop zero-in-degree nodes and decrement their successors. If you process all V nodes the graph is acyclic.

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

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

Tradeoff:

N26-specific tips

N26 wants you to draw the analogy to their KYC step graph - if document-check depends on selfie-check and selfie-check depends on document-check, the onboarding workflow must surface the cycle before launch.

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

Practice these live with InterviewChamp.AI →