Course Schedule I and II
Model course prerequisites as a directed graph and use topological sort to determine if all courses can be completed and in which order.
Course Schedule I and II is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Problem Overview
Course Schedule I (LeetCode 207): given n courses and a list of prerequisites pairs [a, b] meaning 'b must be taken before a', determine if you can finish all courses. Course Schedule II (LeetCode 210): return the actual order to take courses, or an empty array if impossible. Both reduce to topological sort on a directed graph where prerequisites are edges.
Graph Modelling
Build a directed graph: for each prerequisite pair [a, b], add edge b → a ('b must come before a' means b leads to a). Compute in-degrees for each course. A course with in-degree 0 has no prerequisites and can be taken immediately. The problem is solvable if and only if no cycle exists in this graph (no circular dependency).
from collections import defaultdict
def build_graph(n, prerequisites):
graph = defaultdict(list)
in_degree = [0] * n
for a, b in prerequisites: # b must come before a
graph[b].append(a)
in_degree[a] += 1
return graph, in_degree
graph, ind = build_graph(4, [[1,0],[2,0],[3,1],[3,2]])
print('In-degrees:', ind) # [0, 1, 1, 2]
print('Graph edges:', dict(graph))Course Schedule I: Kahn's Solution
Use Kahn's algorithm. If the number of processed courses equals n, all courses can be finished. Otherwise, a circular dependency prevents completion.
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
course = queue.popleft()
count += 1
for nxt in graph[course]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == numCourses
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # FalseCourse Schedule II: Return Order
Same as Course Schedule I, but collect the order of courses as we process them. Return the order if all courses are included, otherwise return an empty list.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
course = queue.popleft()
order.append(course)
for nxt in graph[course]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))Course Schedule with DFS
An alternative using DFS cycle detection. Courses have three states: unvisited (0), in-progress (1), done (2). If we reach an in-progress course during DFS, a cycle exists. This approach is functionally equivalent to Kahn's but uses recursive DFS.
from collections import defaultdict
def canFinish_dfs(numCourses, prerequisites):
graph = defaultdict(list)
for a, b in prerequisites:
graph[b].append(a)
# 0=unvisited, 1=in-progress, 2=done
state = [0] * numCourses
def has_cycle(course):
if state[course] == 1: return True # back edge
if state[course] == 2: return False # already cleared
state[course] = 1
for nxt in graph[course]:
if has_cycle(nxt):
return True
state[course] = 2
return False
return not any(has_cycle(i) for i in range(numCourses))
print(canFinish_dfs(2, [[1,0]])) # True
print(canFinish_dfs(2, [[1,0],[0,1]])) # FalseWhy Direction of Edges Matters
A common mistake is reversing edge direction: if prerequisite is [a, b] meaning 'b before a', add edge b → a not a → b. The edge direction must reflect dependency flow: an arrow points from what must be done first to what depends on it. With wrong direction, the cycle detection and ordering will be backwards, giving incorrect results on problems with multiple dependencies.
Course Schedule III: Greedy Variant
Course Schedule III (LeetCode 630) is a different problem: courses have durations and deadlines, and you want to maximise the number of courses taken. This is solved greedily with a max-heap: always take the course with the latest deadline first; if adding a course exceeds its deadline, replace it with the longest course taken so far (if that course is longer). This is a greedy, not topological sort problem — showing the importance of reading problem statements carefully.
Handling Isolated Nodes
Courses with no prerequisites and no dependents are isolated nodes — they have in-degree 0 and no outgoing edges. Kahn's algorithm correctly handles them: they are immediately enqueued and processed. Make sure to initialise in-degrees for ALL nodes 0 to n-1, even those not appearing in the prerequisites list, or they'll be missed.
# Example: 4 courses, but only courses 0 and 1 have a prerequisite relationship
# Courses 2 and 3 are isolated - they should appear in the output
from collections import deque, defaultdict
def findOrder_isolated(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses # initialise ALL nodes
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
c = queue.popleft(); order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder_isolated(4, [[1,0]])) # [0,1,2,3] or [2,3,0,1] etc.Parallel Course Completion Time
Parallel Courses II: find the minimum number of semesters to take all courses when at most k courses per semester are allowed and prerequisites must be respected. This requires Kahn's level-by-level processing with bitmask DP for the k-selection constraint — a significantly harder problem that combines topological sort with bitmask DP.
Interview Communication Strategy
When facing a Course Schedule-type problem in an interview: (1) Identify it as a topological sort / cycle detection problem immediately. (2) Model the graph by clarifying which direction the edges point. (3) Choose Kahn's (BFS) for simplicity or DFS for familiarity. (4) Handle the cycle case explicitly. (5) Mention time complexity O(V+E). This structured approach demonstrates systematic problem-solving skills.
Comprehensive Test
Testing both solutions on a range of inputs to verify correctness. The Kahn's approach handles multiple valid orderings gracefully — any valid topological order is acceptable as an answer for Course Schedule II.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
c = queue.popleft(); order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(1, [])) # [0]
print(findOrder(2, [[0,1]])) # [1, 0]
print(findOrder(3, [[1,0],[2,1]])) # [0, 1, 2]
print(findOrder(3, [[1,0],[0,1]])) # [] cycleQuick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Course Schedule I and II both use topological sort with edge b → a for prerequisite [a, b], Course Schedule I just checks len(order) == n while Course Schedule II returns the order itself, and DFS-based cycle detection with three states is a valid alternative to Kahn's BFS approach. Next up we explore Kosaraju's algorithm for Strongly Connected Components.
Frequently asked questions
Is the “Course Schedule I and II” lesson free?
Yes — the full text of “Course Schedule I and II” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Course Schedule I and II”?
Model course prerequisites as a directed graph and use topological sort to determine if all courses can be completed and in which order. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Course Schedule I and II” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.