DSA problem
Course Schedule II
There are a total of numCourses courses labeled 0 to numCourses - 1. You are given a list prerequisites where prerequisites[i] = [a, b] says you must take course b before course a. Return any valid ordering of all the courses; if no such ordering exists (because the prerequisites contain a cycle) return an empty array.
This is the constructive sibling of the classic Course Schedule cycle-detection problem. Modelling each prerequisite [a, b] as a directed edge b → a, we want a linear ordering of the vertices such that every edge points from an earlier vertex to a later one. That is exactly the definition of a topological ordering of a directed acyclic graph.
Kahn's algorithm is the natural BFS-style solution. Compute the in-degree of every node, push the zero-in-degree nodes into a queue, then repeatedly pop a node, append it to the answer, and decrement the in-degree of each of its successors, pushing any successor whose in-degree drops to zero. The order in which nodes are popped from the queue is a valid topological order.
If, after the loop, the produced order has fewer than numCourses entries, some node was permanently trapped inside a cycle and we return an empty array. Otherwise the recorded order is a feasible course schedule. The algorithm runs in O(V + E) time and O(V + E) space, which is optimal because we must inspect every node and every edge at least once.
Examples
numCourses = 2, prerequisites = [[1,0]][0,1]numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]][0,1,2,3]numCourses = 1, prerequisites = [][0]Constraints
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= numCourses * (numCourses - 1)
- prerequisites[i].length == 2
- 0 <= a, b < numCourses
- a != b and all the pairs prerequisites[i] are distinct.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.