Course Schedule II

Problem

There are n courses (0..n−1) and prerequisites[i] = [a, b] means you must take b before a. Return any valid order to finish every course, or an empty array if it is impossible.

Constraints

• 1 ≤ n ≤ 2000
• 0 ≤ prereq.length ≤ 5000

Approach — Graphs

This is a Graphs problem. The idea: explore the graph with BFS or DFS, marking nodes visited so you never process one twice. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(V + E) time.

Solution code

Python

class Solution:
    def findOrder(self, numCourses, prerequisites):
        from collections import deque
        adj = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses
        for a, b in prerequisites:
            adj[b].append(a); indeg[a] += 1
        q = deque(i for i in range(numCourses) if indeg[i] == 0)
        order = []
        while q:
            u = q.popleft(); order.append(u)
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        return order if len(order) == numCourses else []

Java

import java.util.*;

class Solution {
    public int[] findOrder(int n, int[][] prereq) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] p : prereq) { adj.get(p[1]).add(p[0]); indeg[p[0]]++; }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
        int[] out = new int[n];
        int k = 0;
        while (!q.isEmpty()) {
            int c = q.poll();
            out[k++] = c;
            for (int next : adj.get(c)) {
                if (--indeg[next] == 0) q.offer(next);
            }
        }
        return k == n ? out : new int[0];
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.