Skip to main content

16. Course Schedule

mediumAsked at Riot Games

Detect whether a set of prerequisite pairs forms a valid DAG — Riot evaluates topological reasoning to model champion-ability dependency graphs and rune unlocks.

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

Problem

There are numCourses courses labeled 0 to numCourses-1 and a list of prerequisites pairs [a,b] meaning to take a you must first take b. Return true if you can finish all courses (no cycle).

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000

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. Brute DFS from every node

Run DFS from every node tracking the call stack; if any cycle, return false.

Time
O(V * (V+E))
Space
O(V+E)
// For each course, DFS and track a fresh visited set
// Detect a cycle by hitting a node already in the current DFS path
// Wasted work re-walking subtrees from every start

Tradeoff:

2. Kahn's BFS topological sort

Compute in-degrees, enqueue zero-indegree nodes, decrement neighbors. If processed count equals numCourses, no cycle exists. Mirrors how Riot validates rune-unlock dependency DAGs during champion-select startup.

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

Tradeoff:

Riot Games-specific tips

Riot grades dependency-graph problems on whether you reach Kahn's in-degree BFS by yourself — the same algorithm their pipeline uses to resolve champion-ability load order without recursive stack pressure.

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

Practice these live with InterviewChamp.AI →