This problem follows the Topological Sort / Cycle Detection pattern, commonly found in the Graphs category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Build adjacency list. DFS with 3 states (unvisited, visiting, visited). Detect cycles.
Three states (not just visited/unvisited) are needed to detect back edges in directed graphs — 'visiting' means the node is in the current DFS path.
graph = defaultdict(list)
for a, b in prerequisites:
graph[a].append(b)
state = [0] * numCourses # 0=unvisited, 1=visiting, 2=visited
def dfs(course):
if state[course] == 1: return false # cycle
if state[course] == 2: return true # done
state[course] = 1
for prereq in graph[course]:
if not dfs(prereq): return false
state[course] = 2
return true
return all(dfs(i) for i in range(numCourses))Practice Course Schedule and similar Graphs problems with flashcards. Build pattern recognition through active recall.
Practice this problem