Course Schedule II

mediumGraphs: Topological Sort & Union-Find62 stepsJava · Python · C++

Return an order to take all courses, or an empty array if impossible. Run Kahn's algorithm and record each course as it leaves the queue. If fewer than n courses were recorded, there's a cycle.

▶ Watch the animated trace

Traced input: numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]] → [0, 1, 2, 3]. Original problem: neetcode.io/problems/course-schedule-ii

Complexity

BestO(V + E)

AverageO(V + E)

WorstO(V + E)

SpaceO(V + E)

Same as Course Schedule, plus the output array.

Key idea

The order courses leave the queue is a valid topological order.
Many valid orders can exist; any one is accepted.
An incomplete order means some courses are stuck in a cycle.

Common mistakes

Returning a partial order when there's a cycle.
Reversing the edge direction.

Solution

Java

int[] findOrder(int n, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indegree = new int[n];
    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]);
        indegree[p[0]]++;
    }
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.offer(i);
    int[] order = new int[n];
    int k = 0;
    while (!queue.isEmpty()) {
        int c = queue.poll();
        order[k++] = c;
        for (int next : adj.get(c)) {
            if (--indegree[next] == 0) queue.offer(next);
        }
    }
    return k == n ? order : new int[0];
}

Python

def findOrder(n: int, prerequisites: List[List[int]]) -> List[int]:
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for a, b in prerequisites:
        adj[b].append(a)
        indegree[a] += 1
    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        c = queue.popleft()
        order.append(c)
        for nxt in adj[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0: queue.append(nxt)
    return order if len(order) == n else []

C++

vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(n);
    vector<int> indegree(n);
    for (auto& p : prerequisites) {
        adj[p[1]].push_back(p[0]);
        indegree[p[0]]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int c = q.front(); q.pop();
        order.push_back(c);
        for (int next : adj[c]) {
            if (--indegree[next] == 0) q.push(next);
        }
    }
    return (int)order.size() == n ? order : vector<int>{};
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Cycle Neither course can start.	`numCourses = 2, prerequisites = [[0, 1], [1, 0]]`	`[]`
Single course Take it.	`numCourses = 1, prerequisites = []`	`[0]`
Chain Only one valid order.	`numCourses = 3, prerequisites = [[1, 0], [2, 1]]`	`[0, 1, 2]`