Course Schedule II

You are given numCourses labeled 0..numCourses-1 and a list of prerequisites [a, b] meaning you must take b before a. Return any valid order to finish all courses, or an empty list if impossible.

Why this is worth learning

The output is a certificate, not a unique sequence. Validate a topological order by checking it contains every course once and places each prerequisite before its dependent.

Before coding: one-minute experiment

For courses 0,1,2 with only edge 0->2, are [0,1,2] and [1,0,2] both valid? What must a test check instead of one fixed order?

Function signature

func FindOrder(numCourses int, prerequisites [][]int) []int

Inputs / outputs

• numCourses: total number of courses.
• prerequisites: pairs [a, b] indicating directed edges b -> a.
• Return: a valid topological order or [] if there is a cycle.

Example

numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] (or [0,2,1,3])

Constraints

• 1 <= numCourses <= 200_000
• Every prerequisite has exactly two labels in 0..numCourses-1. Duplicate pairs, if supplied, must be counted consistently in adjacency and indegree.

Core idea (near-solution)

Enumerating course permutations and checking their edges is correct but wastes work on orders already known to break prerequisites. Construct only valid prefixes: retain a count of unmet prerequisites per course and a queue of ready courses. Appending any ready course is legal, and removing its outgoing obligations may expose more choices. Several courses can be ready at once, so the output need not be unique. A nonempty valid prefix is not enough: if fewer than all courses are emitted, the remaining directed cycle means no complete answer exists.

Invariant: At loop boundaries, the queue contains exactly the ready, not-yet-emitted courses, and each residual indegree counts incoming edges from not-yet-emitted courses.

Algorithm (step-by-step)

1. Build an adjacency list and indegree counts.
2. Initialize a queue with all nodes of indegree 0.
3. Pop from the queue, append to the order, and decrement indegrees of neighbors.
4. If a neighbor reaches indegree 0, enqueue it.
5. If the final order length equals numCourses, return it; otherwise return an empty slice.

Correctness sketch

The queue contains exactly currently available unprocessed courses. By the residual-indegree invariant, each appended course has no unmet dependency, so every prefix respects all prerequisite edges whose targets have been emitted. When all vertices are appended, the order is a complete valid certificate. If fewer than numCourses are appended, a residual directed cycle prevents a complete certificate, so returning a partial prefix would be misleading and the function returns an empty result. Ties between available vertices may be resolved in any order without affecting correctness.

Trace (hand walkthrough)

Example input:
numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] (or [0,2,1,3])

Walk:
- indegree: 0:0,1:1,2:1,3:2; queue [0]
- pop 0 -> indegree1=0 indegree2=0; queue [1,2]
- pop 1 -> indegree3=1; pop 2 -> indegree3=0; pop 3 -> order [0,1,2,3]

Pitfalls to avoid

• Forgetting to include courses with no edges.
• Returning a partial order when a cycle exists.
• Mixing edge directions ([a,b] means b -> a).

Debugging lens

Keep cycle detection separate from tie ordering. A nonempty prefix from a cyclic graph is not a valid answer. Validate the returned certificate against every original edge.

Complexity

• Time: O(V + E).
• Extra space: O(V + E).

Implementation notes (Go)

• Use a slice as a queue with head index.
• Pre-allocate adjacency lists if you want to reduce allocations.

Reconstruction checkpoint

For four courses with only edge 0→2, a proposed result is [0,1,1,2]. All listed prerequisites appear in order. Is that enough? Specify a validator that accepts every legitimate ordering.

Return to Graph General · Module quiz