Skip to main content

10. Course Schedule

mediumAsked at Rappi

Determine if all courses can be finished given prerequisite pairs — Rappi frames this as validating that a multi-stop delivery route has no circular pickup-then-drop dependency.

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

Problem

You have numCourses to take, labeled 0..numCourses-1. Given prerequisites as pairs [a,b] meaning b must be taken before a, return true if you can finish all courses.

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 repeated scan

Repeatedly remove courses with no prereqs; if none can be removed but some remain, return false.

Time
O((V+E)^2)
Space
O(V+E)
// each pass scans all courses to find one with zero indegree — quadratic in worst case.

Tradeoff:

2. Kahn's topological sort

Build an indegree array and a queue of zero-indegree nodes; pop nodes and decrement neighbors — if you process all V, the graph is a DAG.

Time
O(V+E)
Space
O(V+E)
function canFinish(n, pre) {
  const g = Array.from({length:n},()=>[]);
  const ind = new Array(n).fill(0);
  for (const [a,b] of pre) { g[b].push(a); ind[a]++; }
  const q = [];
  for (let i=0;i<n;i++) if (!ind[i]) q.push(i);
  let seen = 0;
  while (q.length) {
    const x = q.shift(); seen++;
    for (const y of g[x]) if (--ind[y]===0) q.push(y);
  }
  return seen === n;
}

Tradeoff:

Rappi-specific tips

Rappi cares that you recognize this as cycle detection in a DAG — they reject hand-waved 'recursive DFS' answers without an explicit visited/visiting tri-color or indegree scheme.

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

Practice these live with InterviewChamp.AI →