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.

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

Core idea (near-solution)

This is topological sorting of a directed graph. If every node can be removed by repeatedly taking nodes with indegree 0, the graph is acyclic and a valid order exists.

Invariant: the queue contains exactly the courses whose prerequisites have all been satisfied so far.

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

• Invariant: the queue contains exactly the courses whose prerequisites have all been satisfied so far.
• Nodes with indegree 0 have no unmet prerequisites and can be taken safely.
• Removing them and updating indegrees preserves correctness of remaining prerequisites.
• If all nodes are removed, the order is valid; otherwise a cycle exists.

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).

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.