20. Course Schedule

mediumAsked at Swiggy

Decide whether you can finish all courses given prerequisite pairs.

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

Problem

There are numCourses courses labeled 0..numCourses-1. Given prerequisites where [a, b] means b must be taken before a, return true if you can finish every course, false if the prerequisite graph contains a cycle.

Constraints

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

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. DFS with recursion stack

Run DFS from each node; if the recursion stack revisits a node mid-traversal, cycle exists.

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

const adj=Array.from({length:numCourses},()=>[]);
for (const [a,b] of prerequisites) adj[b].push(a);
const color=new Array(numCourses).fill(0);
function dfs(u){if(color[u]===1)return false;if(color[u]===2)return true;color[u]=1;for(const v of adj[u])if(!dfs(v))return false;color[u]=2;return true;}
for (let i=0;i<numCourses;i++) if(!dfs(i)) return false;
return true;

Tradeoff:

2. Kahn topological sort

Build the graph plus in-degree array. Push all zero-in-degree nodes into a queue and pop them, decrementing neighbors. If the visited count equals numCourses, no cycle.

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 q = [];
  for (let i = 0; i < numCourses; 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 === numCourses;
}

Tradeoff:

Swiggy-specific tips

Swiggy uses topological sorting because their dispatch DAG (pick-up -> drop-off dependencies) has the same shape; verbalize the cycle definition before coding.

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

Practice these live with InterviewChamp.AI →