Course Schedule II

Difficulty: Medium

Problem

You again have numCourses courses and a list prerequisites where each pair [a, b] says that b must be completed before a. This time, instead of a yes/no answer, return one valid sequence in which all the courses can be taken (any valid sequence is fine). If the prerequisites contain a cycle and no sequence exists, return an empty array. The idea is the same as before, only the output is richer.

Example

Input: numCourses = 5, prerequisites = [[1,0],[2,1],[3,1],[4,2],[4,3]]
Output: [0,1,2,3,4]
Explanation: Course 0 has no prerequisite, so it goes first and unlocks 1. Course 1 then unlocks 2 and 3, and course 4 needs both of those. [0,1,3,2,4] would work too.

Brute-force approach

No brute-force phase: Kahn's algorithm from the previous lesson is the approach; only the output changes.

Optimal approach

Key insight: The valid order was hiding inside Course Schedule I all along. The sequence in which courses left the queue. Write it down instead of counting it.

Run Kahn's algorithm exactly as in Course Schedule, but append each taken course to an order list. Return the list if complete, else [].

Steps

  1. Build adjacency + indegree (arrow b → a per [a, b])
  2. Seed the queue with all indegree-0 courses
  3. Each dequeued course is APPENDED to the order, then its arrows dissolve
  4. Newly-unblocked courses join the queue
  5. Return order if its length is numCourses, else []

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

Pseudocode

function findOrder(numCourses, prerequisites):
    build adj and indegree     // [a, b] draws b -> a
    queue = all courses with indegree ____
    order = []
    
    while queue not empty:
        c = queue.pop_front()
        order.____(c)
        for nxt in adj[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == ____:
                queue.push(nxt)
    
    if length(order) == numCourses:
        return ____
    return []

Hints

  • Only unblocked courses may start, what indegree marks 'ready'?
  • Version I counted here; version II writes the course down instead
  • A course joins the queue at the exact moment its LAST prerequisite dissolves
  • Complete schedule → return it. Incomplete → the cycle rule says return what?

Complexity questions

Recording the order instead of counting changes the complexity how?

Not at all: append is O(1), so it stays O(V + E). One O(1) append replaced one O(1) increment. Each course still queues once, each arrow still dissolves once: O(V + E).

What is the space complexity?

O(V + E): adjacency, indegrees, queue, and the order list. Same structures as version I plus the O(V) order list, still O(V + E) overall.

When is the topological order UNIQUE?

Exactly when the queue never holds more than one course at a time. Every step has a single unblocked choice. Two simultaneously-unblocked courses = two valid orders. Uniqueness requires a forced march: exactly one indegree-0 course at every step (a 'Hamiltonian path' situation).

Topological order can also come from DFS. How?

Run DFS with finish times: a node is appended AFTER all its descendants finish, then the list is REVERSED. Postorder DFS finishes dependents before the things they depend on. Reverse that finishing order and every arrow points forward. Kahn's (BFS) and reversed-postorder (DFS) are the two standard routes to the same answer.

Check your understanding of Course Schedule II

What changes from Course Schedule I to II?

Only the OUTPUT: instead of true/false, we return the actual order the algorithm was already producing. Kahn's algorithm already processes courses in a valid order: Course Schedule I just counted them. Record them in a list instead of counting, and you have Course Schedule II. One changed line.

Why is the order in which Kahn's algorithm takes courses automatically valid?

A course only enters the queue when its indegree hits 0, meaning every one of its prerequisites was already taken. Entering the queue REQUIRES indegree 0, all blockers already processed. So at the moment a course is appended to the order, everything it needed appears earlier in that order. Validity is built into the mechanism.

Can there be more than one valid order?

Yes: whenever two courses are simultaneously unblocked, either may go first ([0,1,2,3] and [0,2,1,3] are both valid in the example). After taking 0, courses 1 and 2 are BOTH in the queue: either order between them respects every arrow. The problem accepts any valid order; the queue's FIFO behavior just picks one deterministically.

What should the function return when the prerequisite graph has a cycle?

An empty array: no complete valid order exists. The problem asks for an ordering of ALL courses. A cycle makes that impossible, so we return []. Careful: the algorithm may have processed SOME courses before stalling. That partial list must be discarded.

How do we DETECT that the order is incomplete?

Compare lengths: if len(order) < numCourses, a cycle trapped the missing courses. Cycle members never reach indegree 0, never enter the queue, never join the order. The same processed-count check from Course Schedule I, now phrased as a length check on the order list.

Related problems

Keep practising