Skip to main content

22. Course Schedule II

mediumAsked at Nubank

Topologically order n courses given prerequisite edges; Nubank uses Kahn's algorithm as a stand-in for ordering dependent steps in a settlement DAG.

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

Problem

There are numCourses labeled 0..numCourses-1. prerequisites[i] = [a, b] means course b must be taken before a. Return a valid order in which to finish all courses, or an empty array if no valid order exists.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • All prerequisite pairs are unique

Examples

Example 1

Input
numCourses = 2, prerequisites = [[1,0]]
Output
[0,1]

Example 2

Input
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output
[0,1,2,3] or [0,2,1,3]

Approaches

1. DFS post-order

DFS each node, push to result on post-order, detect cycles via three-color marks. Reverse result.

Time
O(V+E)
Space
O(V+E)
// color[] white=0, gray=1, black=2; on gray during dfs -> cycle, return []; else post-order push, then reverse.

Tradeoff:

2. Kahn BFS

Compute in-degrees; queue zero-indegree nodes; pop, append to order, decrement neighbors. If output length < n there is a cycle.

Time
O(V+E)
Space
O(V+E)
function findOrder(n, prerequisites) {
  const adj = Array.from({ length: n }, () => []);
  const indeg = Array(n).fill(0);
  for (const [a, b] of prerequisites) { adj[b].push(a); indeg[a]++; }
  const q = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
  const order = [];
  while (q.length) {
    const c = q.shift();
    order.push(c);
    for (const nxt of adj[c]) if (--indeg[nxt] === 0) q.push(nxt);
  }
  return order.length === n ? order : [];
}

Tradeoff:

Nubank-specific tips

Nubank loves Kahn for this because it naturally yields the order in which independent settlement jobs can fan out — mention that connection.

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

Practice these live with InterviewChamp.AI →