# Course Schedule II > Order courses so every prerequisite comes first, or report that no order exists. Why a course with zero unmet prerequisites is always safe to take next, and how a leftover course reveals a cycle. - Track: DSA (Graphs & Union-Find) - Level: Medium - Format: Step-through player - Author: Aayush Ostwal - Published: 25 October 2026 - Topics: Topological sort, BFS, Kahn's algorithm, Graph, Cycle detection - LeetCode: https://leetcode.com/problems/course-schedule-ii/ - Canonical URL: https://compoundengineer.com/library/dsa/course-schedule-ii Graph traversal · Topological sort (Kahn's algorithm) Medium · O(V + E) time · O(V + E) space ## Problem There are numCourses courses, labelled 0 to numCourses − 1 . You are given prerequisites , where prerequisites[i] = [a, b] means you must take course b before course a . Return any order in which you can take all the courses. If it is impossible, return an empty array. Example 1 Input: numCourses = 6, prerequisites = [[1,0],[2,0],[3,1],[3,2],[4,3],[5,3]] Output: [0, 1, 2, 3, 4, 5] (course 3 needs both 1 and 2; 4 and 5 need 3) Example 2 Input: numCourses = 4, prerequisites = [[1,0],[2,1],[3,2],[1,3]] Output: [] (1 needs 0, 2 needs 1, 3 needs 2, and 1 needs 3: a cycle) Constraints 1 ≤ numCourses ≤ 2000 0 ≤ prerequisites.length ≤ numCourses · (numCourses − 1) All pairs are distinct and a ≠ b. Several valid orders may exist. Any one is accepted. ## Brute force You are choosing university courses. Some courses have a prerequisite : you must finish course b before you start course a . In what order can you take all the courses? - Every course appears exactly once in your list. - For each rule "b before a", course b comes earlier in the list. - If the rules contradict each other, return an empty list. Draw each rule as an arrow from the prerequisite to the course it unlocks: b → a . Now a valid order is simply a list in which every arrow points forward . The first course in the list must be one with no arrow pointing into it. The direct idea: try every possible order of the courses, and return the first one that obeys every rule. ### The problem with it There are n! orders (n × (n − 1) × … × 1), and checking each one takes a pass over all the rules. With only twelve courses that is already 479 million orders. It is far too slow. But look at what a valid order is: a list where all arrows point forward. We do not need to search for it. We can build it from the left, one course at a time . ## How to think your way to the optimal solution At each step, which course is safe to put next? A course is safe when it is not waiting for anything: all its prerequisites are already in the list. Count, for every course, how many prerequisites it still waits for. This count is called its in-degree (how many arrows point into it). A course with in-degree 0 is safe, because nothing it needs is missing. So: take any safe course and put it in the list. Then cross it off. Every course it unlocked now waits for one fewer prerequisite. Any course whose count drops to 0 has just become safe, so it joins the line of safe courses. Repeat until nobody is left. Why is it safe? A course with in-degree 0 has no prerequisite left outside the list, so placing it next can never break a rule. And if we get stuck with courses left but none safe, every remaining course is waiting on another remaining course. That means there is a loop of prerequisites, and no valid order exists. ## The optimal solution - Build the arrows, and count the in-degree of every course. - Put every course with in-degree 0 in a queue. A queue hands out items in the order they arrived. - Take a course out of the queue and add it to the answer. - For each course it unlocks: subtract 1 from its in-degree. it reaches 0⟶add it to the queue - Repeat from step 3 until the queue is empty. the answer has all the courses⟶return it fewer⟶there is a loop: return an empty list By hand , with 6 courses and the rules [1,0] [2,0] [3,1] [3,2] [4,3] [5,3] . The in-degrees are: course 0 has 0, courses 1 and 2 have 1, course 3 has 2, courses 4 and 5 have 1. - Only course 0 has in-degree 0. The queue is [0]. - Take 0. Answer [0]. It unlocks 1 and 2: both drop to 0, so both join the queue: [1, 2]. - Take 1. Answer [0, 1]. It unlocks 3, which drops from 2 to 1. Not safe yet. - Take 2. Answer [0, 1, 2]. It unlocks 3, which drops to 0. The queue is [3]. - Take 3. Answer [0, 1, 2, 3]. It unlocks 4 and 5, both drop to 0: queue [4, 5]. - Take 4, then 5. Answer [0, 1, 2, 3, 4, 5]. That has all 6 courses, so we return it. With the loop [1,0] [2,1] [3,2] [1,3] , only course 0 starts safe. Taking it only lowers course 1 from 2 to 1, so nothing new joins the queue. We stop with 1 course in the answer, not 4, so we return [] . Press Play to watch the queue and the in-degree numbers change. ## Complexity analysis O(V + E) Time. Here's why: V is the number of courses and E the number of rules. Building the arrows and counting in-degrees takes one pass over the E rules. Each course enters the queue once and is taken out once, which is V steps. When a course is taken out, we look at each arrow leaving it once, so over the whole run we look at each of the E arrows once. O(V + E) Space. The arrows take V lists holding E entries in total. The in-degree list, the queue and the answer each hold at most V courses. ## Interviewer follow-ups These are the questions that usually come next. Open one to see an answer you could say out loud. "You can take as many courses at once as you like. What is the fewest number of semesters?" What they are checking Whether you see that the queue already holds every course that is safe to take at the same time. A strong answer I process the queue in rounds. In each round I take out everything that is in the queue right now , and that is one semester. The courses they unlock go into the queue for the next round. The number of rounds is the number of semesters. If there is a loop, I never finish all the courses, and I return -1 (or whatever the problem asks for). "There is a loop. Tell me which courses are the problem." What they are checking Whether you can read useful information out of the failure case instead of only reporting it. A strong answer When the queue empties early, the courses that never reached in-degree 0 are the ones that are in a loop or wait on one. They are exactly the courses missing from the answer. To report one actual loop, I would start from one of them and keep following a prerequisite that is also in that leftover group until a course repeats. That repeated course is on a loop. "Several courses are safe at once. Always take the one with the smallest number." What they are checking Whether you know why the queue gives "any valid order", and what to use when the order matters. A strong answer A plain queue returns whichever safe course arrived first, which is a valid order but not a chosen one. To always take the smallest, I swap the queue for a min-heap. The heap hands out the smallest safe course, and unlocked courses are added to it. The rest of the algorithm stays the same. The cost goes from O(V + E) to O(V log V + E), because each heap step takes about log V. ## Spot this pattern - Items have "must come before" rules, and you need an order, or you need to know that none exists. - You can count how many things an item still waits for. - Something that waits for nothing can go first, and finishing it frees the items that waited on it. ## Solution code ### Python ```python from collections import deque class Solution: def findOrder(self, num_courses, prerequisites): graph = [[] for _ in range(num_courses)] in_degree = [0] * num_courses for course, pre in prerequisites: graph[pre].append(course) # edge: pre -> course in_degree[course] += 1 # course waits on one more prerequisite queue = deque(i for i in range(num_courses) if in_degree[i] == 0) order = [] while queue: node = queue.popleft() order.append(node) for nxt in graph[node]: in_degree[nxt] -= 1 # one prerequisite of nxt is now done if in_degree[nxt] == 0: # nothing left to wait for queue.append(nxt) return order if len(order) == num_courses else [] ``` ### Java ```java class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { List[] graph = new List[numCourses]; Arrays.setAll(graph, i -> new ArrayList<>()); int[] inDegree = new int[numCourses]; for (int[] p : prerequisites) { // p = [course, pre] graph[p[1]].add(p[0]); // edge: pre -> course inDegree[p[0]]++; // course waits on one more prerequisite } Queue queue = new ArrayDeque<>(); for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) queue.add(i); List order = new ArrayList<>(); while (!queue.isEmpty()) { int node = queue.poll(); order.add(node); for (int nxt : graph[node]) { inDegree[nxt]--; // one prerequisite of nxt is now done if (inDegree[nxt] == 0) // nothing left to wait for queue.add(nxt); } } if (order.size() != numCourses) return new int[0]; return order.stream().mapToInt(Integer::intValue).toArray(); } } `.replace(/^\n/, ''); const MAP_JAVA = { 5: [3, 4], 6: 5, 7: 6, 8: 7, 9: 8, 10: [10, 11], 11: 12, 12: 13, 13: 14, 14: 15, 15: 16, 16: 17, 17: 18, 18: 19, 19: [22, 23] }; const CODE_CPP = ` class Solution { public: vector findOrder(int numCourses, vector>& prerequisites) { vector> graph(numCourses); vector inDegree(numCourses, 0); for (auto& p : prerequisites) { // p = [course, pre] graph[p[1]].push_back(p[0]); // edge: pre -> course inDegree[p[0]]++; // course waits on one more prerequisite } queue q; for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) q.push(i); vector order; while (!q.empty()) { int node = q.front(); q.pop(); order.push_back(node); for (int nxt : graph[node]) { inDegree[nxt]--; // one prerequisite of nxt is now done if (inDegree[nxt] == 0) // nothing left to wait for q.push(nxt); } } return order.size() == numCourses ? order : vector(); } }; `.replace(/^\n/, ''); const MAP_CPP = { 5: 4, 6: 5, 7: 6, 8: 7, 9: 8, 10: [10, 11], 11: 12, 12: 13, 13: 14, 14: 15, 15: 16, 16: 17, 17: 18, 18: 19, 19: 22 }; const LANGS = [ { lang: 'python', label: 'Python', code: CODE }, { lang: 'java', label: 'Java', code: CODE_JAVA, map: MAP_JAVA }, { lang: 'cpp', label: 'C++', code: CODE_CPP, map: MAP_CPP }, ]; document.getElementById('brute-code').innerHTML = DSA.highlight(` from itertools import permutations class Solution: def findOrderBrute(self, num_courses, prerequisites): for perm in permutations(range(num_courses)): pos = {course: i for i, course in enumerate(perm)} if all(pos[pre] < pos[course] for course, pre in prerequisites): return list(perm) return [] `); const N = 6, PRE = [[1,0],[2,0],[3,1],[3,2],[4,3],[5,3]]; const POS = [[0,1],[1,0],[1,2],[2,1],[3,0],[3,2]]; const nodesOf = (n) => Array.from({ length: n }, (_, i) => n === 6 ? { id: i, x: POS[i][0], y: POS[i][1] } : { id: i }); const edgesOf = (pre) => pre.map(([c, p]) => ({ u: p, v: c })); const gr = (states, o = {}) => DSA.graph('graph', { nodes: nodesOf(N), edges: edgesOf(PRE), directed: true }, Object.assign({ states, width: 420, height: 200 }, o)); DSA.still('#fig-1', [ { panels: [gr({ 0: 'ok' }, { notes: { 0: 'in 0', 1: 'in 1', 2: 'in 1', 3: 'in 2', 4: 'in 1', 5: 'in 1' } })], cond: 'in-degree of 0 is 0', act: 'course 0 can go first', note: 'Course 0 has no arrow into it. Every other course waits on at least one prerequisite.' }, ], { caption: '**Figure 1** — Example 1 as a graph. An arrow goes from a prerequisite to the course it unlocks. The small number is the in-degree.' }); DSA.still('#fig-2', [ { panels: [gr({ 0: 'active', 1: 'frontier', 2: 'frontier' }, { notes: { 0: 'in 0', 1: 'in 0', 2: 'in 0', 3: 'in 2', 4: 'in 1', 5: 'in 1' }, edgeStates: { '0-1': 'done', '0-2': 'done' } })], cond: 'take 0; in_degree[1] 1→0, in_degree[2] 1→0', act: 'queue 1 and 2', note: 'Taking course 0 frees courses 1 and 2.' }, { panels: [gr({ 0: 'done', 1: 'active', 2: 'frontier', 3: 'compare' }, { notes: { 0: 'in 0', 1: 'in 0', 2: 'in 0', 3: 'in 1', 4: 'in 1', 5: 'in 1' }, edgeStates: { '0-1': 'done', '0-2': 'done', '1-3': 'done' } })], cond: 'take 1; in_degree[3] 2→1', act: '1 ≠ 0, so 3 must wait', note: 'Course 3 still needs course 2, so it is not queued yet.' }, { panels: [gr({ 0: 'done', 1: 'done', 2: 'active', 3: 'ok' }, { notes: { 0: 'in 0', 1: 'in 0', 2: 'in 0', 3: 'in 0', 4: 'in 1', 5: 'in 1' }, edgeStates: { '0-1': 'done', '0-2': 'done', '1-3': 'done', '2-3': 'done' } })], cond: 'take 2; in_degree[3] 1→0', act: 'queue 3', note: 'Now both prerequisites of course 3 are done.' }, ], { caption: '**Figure 2** — Taking a course removes its arrows. A course joins the queue only when its in-degree hits 0.' }); function solve(n, pre) { const g = Array.from({ length: n }, () => []), d = Array(n).fill(0); for (const [c, p] of pre) { g[p].push(c); d[c]++; } const q = []; for (let i = 0; i < n; i++) if (!d[i]) q.push(i); const o = []; while (q.length) { const x = q.shift(); o.push(x); for (const y of g[x]) if (--d[y] === 0) q.push(y); } return o.length === n ? o : []; } DSA.player('#player', { title: 'Solution().findOrder(num_courses, prerequisites)', code: CODE, langs: LANGS, lang: 'python', solve, inputs: [ { label: '6 courses, diamond', args: [6, PRE], expect: [0, 1, 2, 3, 4, 5] }, { label: '4 courses, cycle', args: [4, [[1,0],[2,1],[3,2],[1,3]]], expect: [] }, { label: '2 courses, 2-cycle', args: [2, [[1,0],[0,1]]], expect: [] }, { label: '1 course', args: [1, []], expect: [0] }, ], legend: { frontier: 'ready, in the queue', active: 'being taken', compare: 'in-degree just lowered', ok: 'became ready', done: 'taken (in the order)', bad: 'stuck (never ready)' }, trace(T, n, pre) { const graph = Array.from({ length: n }, () => []), ind = Array(n).fill(0); const edges = [], doneE = new Set(), order = [], q = []; let cur = null, look = null, lookE = null, built = false, stuck = false; let course = '–', p = '–', node = '–', nxt = '–'; const show = (line, note, extra = {}) => { const states = {}; order.forEach(x => states[x] = 'done'); q.forEach(x => states[x] = 'frontier'); if (stuck) for (let i = 0; i < n; i++) if (!order.includes(i)) states[i] = 'bad'; if (cur !== null) states[cur] = 'active'; if (look) states[look[0]] = look[1]; const es = {}; doneE.forEach(e => es[e] = 'done'); if (lookE) es[lookE] = 'compare'; const notes = {}; if (built || edges.length) for (let i = 0; i < n; i++) notes[i] = 'in ' + ind[i]; T.frame(line, Object.assign({ note, vars: { course, pre: p, node, nxt }, panels: [ DSA.graph('graph', { nodes: nodesOf(n), edges, directed: true }, { states, edgeStates: es, notes, width: 420, height: 200 }), DSA.array('in_degree', ind, { states: Object.fromEntries([...(look ? [[look[0], look[1]]] : [])]) }), DSA.queue('queue', [...q], { states: Object.fromEntries(q.map((_, i) => [i, 'frontier'])) }), DSA.array('order', order), ], }, extra)); }; show(5, `One empty list of "courses unlocked" per course, ${n} in all.`); show(6, 'Every course starts with zero known prerequisites.'); for (const [c, pr] of pre) { course = c; p = pr; graph[pr].push(c); ind[c]++; edges.push({ u: pr, v: c }); lookE = `${pr}-${c} ``` ### C++ ```cpp class Solution { public: vector findOrder(int numCourses, vector>& prerequisites) { vector> graph(numCourses); vector inDegree(numCourses, 0); for (auto& p : prerequisites) { // p = [course, pre] graph[p[1]].push_back(p[0]); // edge: pre -> course inDegree[p[0]]++; // course waits on one more prerequisite } queue q; for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) q.push(i); vector order; while (!q.empty()) { int node = q.front(); q.pop(); order.push_back(node); for (int nxt : graph[node]) { inDegree[nxt]--; // one prerequisite of nxt is now done if (inDegree[nxt] == 0) // nothing left to wait for q.push(nxt); } } return order.size() == numCourses ? order : vector(); } }; `.replace(/^\n/, ''); const MAP_CPP = { 5: 4, 6: 5, 7: 6, 8: 7, 9: 8, 10: [10, 11], 11: 12, 12: 13, 13: 14, 14: 15, 15: 16, 16: 17, 17: 18, 18: 19, 19: 22 }; const LANGS = [ { lang: 'python', label: 'Python', code: CODE }, { lang: 'java', label: 'Java', code: CODE_JAVA, map: MAP_JAVA }, { lang: 'cpp', label: 'C++', code: CODE_CPP, map: MAP_CPP }, ]; document.getElementById('brute-code').innerHTML = DSA.highlight(` from itertools import permutations class Solution: def findOrderBrute(self, num_courses, prerequisites): for perm in permutations(range(num_courses)): pos = {course: i for i, course in enumerate(perm)} if all(pos[pre] < pos[course] for course, pre in prerequisites): return list(perm) return [] `); const N = 6, PRE = [[1,0],[2,0],[3,1],[3,2],[4,3],[5,3]]; const POS = [[0,1],[1,0],[1,2],[2,1],[3,0],[3,2]]; const nodesOf = (n) => Array.from({ length: n }, (_, i) => n === 6 ? { id: i, x: POS[i][0], y: POS[i][1] } : { id: i }); const edgesOf = (pre) => pre.map(([c, p]) => ({ u: p, v: c })); const gr = (states, o = {}) => DSA.graph('graph', { nodes: nodesOf(N), edges: edgesOf(PRE), directed: true }, Object.assign({ states, width: 420, height: 200 }, o)); DSA.still('#fig-1', [ { panels: [gr({ 0: 'ok' }, { notes: { 0: 'in 0', 1: 'in 1', 2: 'in 1', 3: 'in 2', 4: 'in 1', 5: 'in 1' } })], cond: 'in-degree of 0 is 0', act: 'course 0 can go first', note: 'Course 0 has no arrow into it. Every other course waits on at least one prerequisite.' }, ], { caption: '**Figure 1** — Example 1 as a graph. An arrow goes from a prerequisite to the course it unlocks. The small number is the in-degree.' }); DSA.still('#fig-2', [ { panels: [gr({ 0: 'active', 1: 'frontier', 2: 'frontier' }, { notes: { 0: 'in 0', 1: 'in 0', 2: 'in 0', 3: 'in 2', 4: 'in 1', 5: 'in 1' }, edgeStates: { '0-1': 'done', '0-2': 'done' } })], cond: 'take 0; in_degree[1] 1→0, in_degree[2] 1→0', act: 'queue 1 and 2', note: 'Taking course 0 frees courses 1 and 2.' }, { panels: [gr({ 0: 'done', 1: 'active', 2: 'frontier', 3: 'compare' }, { notes: { 0: 'in 0', 1: 'in 0', 2: 'in 0', 3: 'in 1', 4: 'in 1', 5: 'in 1' }, edgeStates: { '0-1': 'done', '0-2': 'done', '1-3': 'done' } })], cond: 'take 1; in_degree[3] 2→1', act: '1 ≠ 0, so 3 must wait', note: 'Course 3 still needs course 2, so it is not queued yet.' }, { panels: [gr({ 0: 'done', 1: 'done', 2: 'active', 3: 'ok' }, { notes: { 0: 'in 0', 1: 'in 0', 2: 'in 0', 3: 'in 0', 4: 'in 1', 5: 'in 1' }, edgeStates: { '0-1': 'done', '0-2': 'done', '1-3': 'done', '2-3': 'done' } })], cond: 'take 2; in_degree[3] 1→0', act: 'queue 3', note: 'Now both prerequisites of course 3 are done.' }, ], { caption: '**Figure 2** — Taking a course removes its arrows. A course joins the queue only when its in-degree hits 0.' }); function solve(n, pre) { const g = Array.from({ length: n }, () => []), d = Array(n).fill(0); for (const [c, p] of pre) { g[p].push(c); d[c]++; } const q = []; for (let i = 0; i < n; i++) if (!d[i]) q.push(i); const o = []; while (q.length) { const x = q.shift(); o.push(x); for (const y of g[x]) if (--d[y] === 0) q.push(y); } return o.length === n ? o : []; } DSA.player('#player', { title: 'Solution().findOrder(num_courses, prerequisites)', code: CODE, langs: LANGS, lang: 'python', solve, inputs: [ { label: '6 courses, diamond', args: [6, PRE], expect: [0, 1, 2, 3, 4, 5] }, { label: '4 courses, cycle', args: [4, [[1,0],[2,1],[3,2],[1,3]]], expect: [] }, { label: '2 courses, 2-cycle', args: [2, [[1,0],[0,1]]], expect: [] }, { label: '1 course', args: [1, []], expect: [0] }, ], legend: { frontier: 'ready, in the queue', active: 'being taken', compare: 'in-degree just lowered', ok: 'became ready', done: 'taken (in the order)', bad: 'stuck (never ready)' }, trace(T, n, pre) { const graph = Array.from({ length: n }, () => []), ind = Array(n).fill(0); const edges = [], doneE = new Set(), order = [], q = []; let cur = null, look = null, lookE = null, built = false, stuck = false; let course = '–', p = '–', node = '–', nxt = '–'; const show = (line, note, extra = {}) => { const states = {}; order.forEach(x => states[x] = 'done'); q.forEach(x => states[x] = 'frontier'); if (stuck) for (let i = 0; i < n; i++) if (!order.includes(i)) states[i] = 'bad'; if (cur !== null) states[cur] = 'active'; if (look) states[look[0]] = look[1]; const es = {}; doneE.forEach(e => es[e] = 'done'); if (lookE) es[lookE] = 'compare'; const notes = {}; if (built || edges.length) for (let i = 0; i < n; i++) notes[i] = 'in ' + ind[i]; T.frame(line, Object.assign({ note, vars: { course, pre: p, node, nxt }, panels: [ DSA.graph('graph', { nodes: nodesOf(n), edges, directed: true }, { states, edgeStates: es, notes, width: 420, height: 200 }), DSA.array('in_degree', ind, { states: Object.fromEntries([...(look ? [[look[0], look[1]]] : [])]) }), DSA.queue('queue', [...q], { states: Object.fromEntries(q.map((_, i) => [i, 'frontier'])) }), DSA.array('order', order), ], }, extra)); }; show(5, `One empty list of "courses unlocked" per course, ${n} in all.`); show(6, 'Every course starts with zero known prerequisites.'); for (const [c, pr] of pre) { course = c; p = pr; graph[pr].push(c); ind[c]++; edges.push({ u: pr, v: c }); lookE = `${pr}-${c} ``` --- From Compound Engineer (https://compoundengineer.com), visual lessons for engineers. The page above is the full interactive version.