Course Schedule II
Asked at Apple, Netflix, Salesforce, Uber, Walmart
Problem
There are a total of n courses you can take, with some courses having prerequisites. Return the ordering of courses you should take to finish all courses. If impossible, return an empty array. This problem tests topological sorting.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| Netflix | Medium | View all Netflix questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Uber | Medium | View all Uber questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Model this as a directed graph: each course is a node, each prerequisite [dest, src] is an edge from src to dest (you must take src before dest).
Topological sort = ordering nodes so all edges go forward. Use Kahn's algorithm (BFS): start with nodes that have no prerequisites (in-degree 0), process them, then process their neighbors.
Why Kahn's works: nodes with in-degree 0 have all prerequisites satisfied. Process them, remove their edges, and new nodes may become in-degree 0. Repeat until done.
Cycle detection: if the result has fewer than n nodes, a cycle exists. You can't finish all courses.
Visual walkthrough for n=4, prereqs=[[1,0],[2,0],[3,1],[3,2]]:
Graph: 0→1, 0→2, 1→3, 2→3
In-degrees: [0, 1, 1, 2]
Queue: [0] (in-degree 0)
Process 0: result=[0]. Decrement 1→0, 2→0. Queue: [1,2].
Process 1: result=[0,1]. Decrement 3→1. Queue: [2].
Process 2: result=[0,1,2]. Decrement 3→0. Queue: [3].
Process 3: result=[0,1,2,3]. Queue empty.
Result: [0,1,2,3] (valid order)
Optimal Approach
Step 1: Build adjacency list and compute in-degrees.
Step 2: Add all nodes with in-degree 0 to a queue.
Step 3: Process queue (BFS):
Dequeue a node, add to result- For each neighbor, decrement in-degree
- If in-degree becomes 0, enqueue
Step 4: If result length < n, cycle exists → return [].
Kahn's algorithm naturally detects cycles: if you can't process all nodes, there's a cycle.
Time: O(V + E). Space: O(V + E).
What Trips People Up in Real Interviews
Confusing this with Course Schedule I. This problem asks for the order, not just whether it's possible. You need topological sort, not just cycle detection.
Not handling the case where no valid order exists (cycle). Return an empty array, not null or an error.
Forgetting to include courses with no prerequisites. They should appear in the order (their in-degree is 0).
Not handling the case where the result array is shorter than the number of courses. This means a cycle exists — return empty.
Reversing the edge direction. If course A requires course B, the edge is B → A (B must come before A). Getting this wrong reverses the topological order entirely.
Solution Code
from collections import deque
def findOrder(numCourses, prerequisites):
adj = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses
for dest, src in prerequisites:
adj[src].append(dest)
in_degree[dest] += 1
q = deque([i for i in range(numCourses) if in_degree[i] == 0])
order = []
while q:
node = q.popleft()
order.append(node)
for neighbor in adj[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
q.append(neighbor)
return order if len(order) == numCourses else []Frequently Asked Questions
What is the Course Schedule II problem?
There are a total of n courses you can take, with some courses having prerequisites. Return the ordering of courses you should take to finish all courses. If impossible, return an empty array. This problem tests topological sorting.
How do you solve Course Schedule II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Course Schedule II?
Course Schedule II is asked at Apple, Netflix, Salesforce, Uber, Walmart. It is a medium difficulty problem.
What are common mistakes on Course Schedule II?
- Confusing this with Course Schedule I. This problem asks for the order, not just whether it's possible. You need topological sort, not just cycle detection.
- Not handling the case where no valid order exists (cycle). Return an empty array, not `null` or an error.
- Forgetting to include courses with no prerequisites. They should appear in the order (their in-degree is 0).
- Not handling the case where the result array is shorter than the number of courses. This means a cycle exists — return empty.
- Reversing the edge direction. If course A requires course B, the edge is B → A (B must come before A). Getting this wrong reverses the topological order entirely.