#210 Course Schedule II
frequently reported atNetflixByteDance / TikTokAppleAmazonUberSalesforce
the problem
In plain words
Same input as Course Schedule. Return any order in which you can take all courses, or an empty array if it's impossible.
in numCourses = 2, prerequisites = [[1,0]]
out [0,1]
in numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
out [0,2,1,3]
[0,1,2,3] is also accepted.
in numCourses = 1, prerequisites = []
out [0]
- 1 ≤ numCourses ≤ 2000
- 0 ≤ prerequisites.length ≤ numCourses · (numCourses − 1)
- All pairs are distinct
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTopological sort & cycle detection
The textbook topological sort. Kahn's poll order is already the answer; DFS needs the finish order reversed.
solutions
From brute force to optimal
Push each course when it finishes (after all courses that depend on it); pop the stack for the order.
- Colour DFS from every white course.
- Back edge to gray → return [].
- On finish push to a stack; pop all to build the answer.
Standard DFS: each vertex and edge once.
Adjacency, colours, finished stack and recursion depth up to V.
class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>()); for (int[] p : prerequisites) adj.get(p[1]).add(p[0]); int[] color = new int[numCourses]; // 0 white, 1 gray, 2 black Deque<Integer> finished = new ArrayDeque<>(); for (int c = 0; c < numCourses; c++) { if (color[c] == 0 && !dfs(c, adj, color, finished)) return new int[0]; } int[] order = new int[numCourses]; for (int i = 0; i < numCourses; i++) order[i] = finished.pop(); return order; } private boolean dfs(int u, List<List<Integer>> adj, int[] color, Deque<Integer> finished) { color[u] = 1; for (int v : adj.get(u)) { if (color[v] == 1) return false; if (color[v] == 0 && !dfs(v, adj, color, finished)) return false; } color[u] = 2; finished.push(u); return true; }}DFS dry run (edges shown as [from, to] = [pre, course])
Output courses in the order they become free (in-degree 0).
- Build pre → course adjacency and in-degrees.
- Queue the zeros.
- Poll → append → decrement neighbours → enqueue zeros.
- If fewer than n were appended, return [].
Each vertex polled once, each edge processed once.
Adjacency list + in-degree array + queue.
class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>()); int[] indegree = new int[numCourses]; for (int[] p : prerequisites) { // p = {course, pre}: edge pre → course adj.get(p[1]).add(p[0]); indegree[p[0]]++; } Deque<Integer> queue = new ArrayDeque<>(); for (int c = 0; c < numCourses; c++) { if (indegree[c] == 0) queue.offer(c); } int[] order = new int[numCourses]; int idx = 0; while (!queue.isEmpty()) { int u = queue.poll(); order[idx++] = u; for (int v : adj.get(u)) { indegree[v]--; if (indegree[v] == 0) queue.offer(v); } } return idx == numCourses ? order : new int[0]; }}Kahn dry run (edges shown as [from, to] = [pre, course])
in the room
How to say it in the interview
talk track
- Say: "This is topological sort; I'll use Kahn because the cycle check is just comparing the count with n."
- Clarify that any valid order is accepted.
- Walk through the diamond example: 0 first, then 1 and 2 in either order, then 3.
traps
- Returning the partially filled array when there's a cycle — return
new int[0]. - Reversing Kahn's output (only the DFS finish order needs reversing).
what they ask next
Follow-ups
Is the order unique? (LC 444 Sequence Reconstruction, Premium)
Unique iff Kahn's queue has exactly one vertex at every step.
Courses in semesters, at most k per semester (LC 1494)?
No longer plain topo sort — it's bitmask DP over subsets (n ≤ 15).
before you submit
Edge cases to test
- A cycle →
new int[0], never a half-filled array. - Courses with no prerequisites and no dependants still appear in the order.
- Several orders are valid — any one is accepted.
practise next
Similar problems
- #207Course ScheduleMediumin Topo Sort
- #269Alien DictionaryHardin Topo SortLeetCode Premium
- #2392Build a Matrix With ConditionsHardin Topo Sort