parikshan

course-schedule-ii

Difficulty: Medium  ·  Topic: Graphs  ·  Practice it on parikshan: /practice/course-schedule-ii/start

The story

The registrar's office is satisfied that the catalogue contains no circular prerequisites. The next request is concrete: print an order in which a student can take every course. When several orders are valid, prefer the one that takes the lower-numbered courses first, so that the freshly enrolled student sees the same lex-smallest order in every counsellor's portal.

This is course-schedule-ii. The same algorithm computes the build order in Bazel and Gradle, the install order in pip and npm, the migration order in Flyway and Liquibase, the resource-creation order in AWS CloudFormation, and the initContainer launch order in kubernetes Pod scheduling. Whenever software needs to do things in a valid topological order with a deterministic tiebreak, this is the algorithm.

What's actually being asked

n courses labelled 0..n-1, m prerequisite rules u v meaning "course u requires course v". Print the lexicographically smallest topological order. If the prerequisites form a cycle, print a single empty line.

The naive approach

Try every permutation; for each, check whether every prerequisite is respected; among the valid ones, take the lex-smallest. O(n!). Useless even at n = 15.

The key insight

Topological sort with Kahn's algorithm picks an in-degree-0 node at every step. Multiple in-degree-0 nodes can coexist; which one you pick is your choice, and that choice fully determines the output order. Replace the FIFO queue in Kahn's with a min-heap keyed on label. The heap always returns the smallest-labelled in-degree-0 node, which is exactly the lex-smallest greedy choice. Greedy is optimal here because the decision at each position depends only on the current in-degree-0 set; once you place a node, the remaining problem is a strictly smaller instance of the same problem.

If the heap empties before n nodes are placed, the un-placed nodes form a sub-graph with a cycle. Emit a single empty line.

That is the whole algorithm. It is exactly course-schedule with one substitution (deque -> heapq) and one extra step (collect the popped labels into a list to print).

Step-by-step approach

  1. Read n, m. Allocate indeg = [0] * n, adj = [[] for _ in range(n)].
  2. For each rule u v: adj[v].append(u), indeg[u] += 1.
  3. Initialise a min-heap with every i where indeg[i] == 0.
  4. out = [].
  5. While the heap is non-empty:
    • Pop the smallest u. Append u to out.
    • For each w in adj[u]: indeg[w] -= 1. If indeg[w] == 0, push w.
  6. If len(out) == n: print ' '.join(map(str, out)). Else: print() (one empty line).

The empty-line cycle signal is the canonical Python convention: print() writes exactly \n to stdout.

Worked example

n = 4, m = 4
1 0
2 0
3 1
3 2

Adjacency adj = [[1,2], [3], [3], []]. In-degrees [0, 1, 1, 2].

  • Heap starts as [0].
  • Pop 0. out = [0]. Decrement indeg[1] -> 0, indeg[2] -> 0. Push both. Heap [1, 2].
  • Pop 1 (smaller). out = [0, 1]. Decrement indeg[3] -> 1. Heap [2].
  • Pop 2. out = [0, 1, 2]. Decrement indeg[3] -> 0. Push 3. Heap [3].
  • Pop 3. out = [0, 1, 2, 3]. Heap empty.
  • len(out) == 4. Print 0 1 2 3.

A cycle example: 1 0 and 0 1. In-degrees [1, 1]. Heap starts empty. The loop never runs. out = []. len(out) < n. Print one empty line.

A "no edges" example: n = 4, m = 0. Heap starts as [0, 1, 2, 3]. The heap pops them in order. Output 0 1 2 3, which is also the natural lex-smallest order.

Complexity

  • Time: O((n + m) log n). Each node enters and leaves the heap once; each enter/leave is O(log n). The adjacency walk contributes O(n + m).
  • Space: O(n + m) for the adjacency, O(n) for the heap and in-degree array.

Common pitfalls

  • Using a sorted list instead of a heap: each insert is O(n) worst case, so the algorithm degrades to O(n^2 + m). The functional answer is identical but the stress test times out.
  • Using a deque (FIFO): Kahn's still produces a valid order, but not the lex-smallest one. The public tests with no ties pass; the private tests with multiple in-degree-0 nodes diverging fail.
  • Forgetting the empty-line convention for a cycle: a cycle should produce one \n exactly. print('') produces \n (correct); print() also produces \n (correct); writing 'false' or [] fails the grader.
  • Edge direction: same trap as course-schedule. Course u requires course v -> edge v -> u. Get it backwards and you get a valid topological order of the reverse graph, which is the reverse of the order the student should take.
  • Self-loops: add 1 to indeg[u] with no offset. The node never enters the heap. len(out) < n. The cycle answer fires. Correct without special handling.

Where this shows up in the enterprise

  • Bazel and Gradle build DAGs: the order in which to build targets is a topological sort of the dependency graph; deterministic builds need a stable tiebreak (often label-sorted), which is precisely this algorithm.
  • npm and pip install order: package managers compute the install order with topological sort over the dependency graph. The lex-smallest convention gives reproducible install logs.
  • AWS CloudFormation stack creation order: resources are provisioned in topological order; ties broken by LogicalId for stable plan output.
  • Database migration runners (Flyway, Liquibase): forward-only migrations form a chain; the migration order is a topological sort.
  • kubernetes Pod scheduling: initContainers run in topological order according to declared dependencies.
  • Spreadsheet recalculation (Excel, Google Sheets): formulas form a DAG; recalculation visits cells in topological order to avoid stale reads.
  • Datadog service maps and CI/CD pipeline visualisation: deterministic rendering order of stages is topological.
  • University catalogue tools: the literal story from the top.

The "deterministic topological order with a lex tiebreak" is the difference between a reproducible build/install/deploy and a "works on my machine" mystery. The heap-based Kahn is the codified version of that determinism.

Variants you'll see elsewhere

  • course-schedule: the predecessor problem (just "is it possible?", no order).
  • alien-dictionary: derive the edges from string comparisons, then run topological sort.
  • parallel-courses: same DAG, return the minimum number of semesters when any number of in-degree-0 courses can run in parallel.
  • minimum-height-trees: a topological-sort-like algorithm that peels leaves layer by layer until at most two remain.
  • find-order-of-characters (alphabet ordering from sorted words): derive edges then topo-sort.

The unifying pattern: DAG order with a tiebreak, derived from a custom edge construction. The hard part is usually building the graph correctly; the topological sort itself is 15 lines.

How parikshan turns this into a learning loop

The recommended flow leverages your course-schedule muscle memory:

  1. Practice mode for course-schedule: solve with Kahn's deque-based approach.
  2. Practice mode for course-schedule-ii: change deque to heapq.heappush / heappop, collect the order into a list, print. Target: under 10 minutes.
  3. AI training: Explain why a min-heap gives lex-smallest order. The proof is short ("greedy on the in-degree-0 set is locally and globally optimal") and worth internalising.
  4. Exam mode under five minutes. The integrity score will reflect whether the heap substitution is in your fingers.

The lex-smallest variant is the lesson that "the queue's discipline determines the order". With this in your toolbox, you can compute lex-LARGEST (max-heap), random-but-reproducible (PRNG with a fixed seed at each tie), or anti-priority orders (custom comparator) with zero algorithm changes. The flexibility is the take-away.

In the AI-integrated workspace

When you direct an agent to write a deterministic topological sort, the failure modes are predictable:

  1. The agent uses a FIFO queue and claims it returns "the order": it returns a topological order, not the lex-smallest. The public tests with no ties pass; private tests with multiple in-degree-0 nodes diverging fail.
  2. The agent uses a sorted list: correct but slow. Demand heapq for the O(log n) insert/pop.
  3. The agent emits a non-canonical cycle signal: 'no order', [], null. The grader expects an empty line. Read the spec.
  4. The agent uses recursive DFS-based topological sort: produces a valid order but with the reverse-DFS-finish-time discipline, not lex-smallest. Reach for Kahn here; reach for three-colour DFS when you also need to detect the cycle node itself.

A reviewer who can articulate "Kahn with heapq for lex-smallest deterministic topological order, empty line on cycle, O((n+m) log n)" in one breath is the reviewer who ships reproducible builds, deploys, and migrations. parikshan's exam mode on this problem is the smoke test for that ability. If you score above 90 on this, every dependency-resolution problem you will ever review becomes a 30-second audit.

course-schedule-ii