Graph day. Three problems that look very different — prerequisite ordering, copying a graph, and a word game. But each one reuses either the snapshot-queue BFS engine from grid BFS, or the "loop over everything, skip what's already visited" pattern from Number of Islands.
207. Course Schedule
Given a list of prerequisite pairs, can you finish every course? This is really just: does this directed graph have a cycle?
Way 1 — BFS (Kahn's Algorithm)
Build an adjacency list plus an inDegree array (how many prerequisites each course still needs). Start with every course that has zero prerequisites left. Every time a course finishes, every course it unlocks gets one step closer to zero prerequisites.
from collections import deque, defaultdict
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
inDegree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course) # prereq unlocks course
inDegree[course] += 1
queue = deque([c for c in range(numCourses) if inDegree[c] == 0])
finished = 0
while queue:
prereqCourse = queue.popleft()
finished += 1
for nextCourse in graph[prereqCourse]:
inDegree[nextCourse] -= 1 # nextCourse, never prereqCourse - its own inDegree is already 0
if inDegree[nextCourse] == 0:
queue.append(nextCourse)
return finished == numCoursesTime: O(V+E) / Space: O(V+E)
There's no explicit "cycle found" check inside the loop — cycle detection is inferred afterward. A course trapped in a cycle can never reach inDegree == 0, because whichever course would unlock it is itself trapped in the same cycle. So if finished ends up short of numCourses, some courses got permanently stuck — that's the cycle.
Follow-up: Course Schedule II — return the order (LC 210)
Same BFS engine. Swap the finished counter for an order list that records the actual sequence, and return it (or [] if it's short).
def findOrder(self, numCourses, prerequisites):
graph = defaultdict(list)
inDegree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
inDegree[course] += 1
queue = deque([c for c in range(numCourses) if inDegree[c] == 0])
order = []
while queue:
prereqCourse = queue.popleft()
order.append(prereqCourse)
for nextCourse in graph[prereqCourse]:
inDegree[nextCourse] -= 1
if inDegree[nextCourse] == 0:
queue.append(nextCourse)
return order if len(order) == numCourses else []A DFS alternative exists too: do post-order DFS, append a course the moment it's fully explored, then reverse the whole list at the end — dependents always finish before their prerequisites in that traversal, so the list comes out backwards.
Follow-up: DFS cycle detection
The BFS version answers "can I finish," but an interviewer will often ask you to solve the same problem with DFS instead. The trap: a single visited set is not enough. In a directed graph, a node can be legitimately reached twice through two different paths without any cycle existing at all — picture 0→1→3 and 0→2→3, a perfectly valid DAG where 3 gets visited twice.
So you need to track two things separately: path (nodes currently on this recursive descent — an actual ancestor) and visited (nodes already fully explored elsewhere and proven safe).
def canFinish(self, numCourses, prerequisites):
graph = defaultdict(list)
for course, prereq in prerequisites:
graph[prereq].append(course)
path = set()
visited = set()
def hasCycle(course):
if course in path:
return True # revisiting a node still on my own call stack = real cycle
if course in visited:
return False # already proven safe elsewhere, just a different route
path.add(course)
for nextCourse in graph[course]:
if hasCycle(nextCourse):
return True
path.remove(course)
visited.add(course)
return False
for course in range(numCourses):
if course not in visited:
if hasCycle(course):
return False
return TrueThe if hasCycle(nextCourse): return True check is not optional — it's the exact mechanism that sends the "cycle found" signal back up through the recursion. Drop it (call the recursive function but discard the result) and the function will silently report every graph as safe, cycle or not.
Verbal follow-ups
| Question | Answer |
|---|---|
Why decrement inDegree[nextCourse], not inDegree[course]? | course's own inDegree is already 0 by the time it's popped — it's the next course that just lost a prerequisite |
| Why not a single visited set for the DFS version? | Diamond-shaped DAGs (0→1→3, 0→2→3) revisit a node through two valid paths with zero cycles — you need path vs visited to tell "still-on-my-stack" apart from "cleared elsewhere" |
| BFS or DFS as the default recommendation? | BFS with a dict/set-based adjacency list generalizes to any node type (not just contiguous integer IDs), so it's the safer default; an array-indexed version is a valid but narrower optimization for exactly this integer-ID shape |
133. Clone Graph
Make a deep copy of an undirected graph that might have cycles (node A knows B, and B knows A back). If you copy it the simple way, you keep going back and forth between A and B forever. So you need a way to check: have I already cloned this node?
Way 1 — DFS with a dictionary
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return None
oldToNew = {} # maps each original node to its copy
def dfs(node):
if node in oldToNew:
return oldToNew[node] # already cloned this one - reuse it
copy = Node(node.val)
oldToNew[node] = copy # register BEFORE touching neighbors
for neighbor in node.neighbors:
copy.neighbors.append(dfs(neighbor))
return copy
return dfs(node)Time: O(V+E) / Space: O(V)
The order here matters. Since this is undirected, a neighbor can point straight back to a node that isn't finished being cloned yet. Register the copy before going into its neighbors, or that cycle keeps calling itself with no way to stop.
A dictionary is the right choice here, not a set. A set can only answer "have I seen this?" — it can't give back the actual copy object you need to add to copy.neighbors. The dictionary does both jobs (visited-check and lookup) at the same time.
Follow-up: BFS instead of DFS
from collections import deque
def cloneGraph(self, node):
if not node:
return None
oldToNew = {node: Node(node.val)}
queue = deque([node])
while queue:
curr = queue.popleft()
for neighbor in curr.neighbors:
if neighbor not in oldToNew:
oldToNew[neighbor] = Node(neighbor.val)
queue.append(neighbor)
oldToNew[curr].neighbors.append(oldToNew[neighbor]) # wire up the edge every time, new or not
return oldToNew[node]The neighbor-wiring line runs on every neighbor, new or already-seen — it only adds one direction per run. Both directions get filled in because the input graph's adjacency lists are already symmetric, so each edge gets visited once from each endpoint at a different point in the traversal.
Follow-up: disconnected graph
If the graph isn't guaranteed connected, you're handed a list of nodes spanning multiple components. Reuse the same BFS as a helper, wrapped in an outer loop — same "loop over everything, skip what's already visited" shape as Number of Islands.
def cloneAllNodes(self, nodes):
oldToNew = {}
result = [] # one entry point per component, not one per input node
def bfs(start):
oldToNew[start] = Node(start.val)
queue = deque([start])
while queue:
curr = queue.popleft()
for neighbor in curr.neighbors:
if neighbor not in oldToNew:
oldToNew[neighbor] = Node(neighbor.val)
queue.append(neighbor)
oldToNew[curr].neighbors.append(oldToNew[neighbor])
for node in nodes:
if node not in oldToNew:
bfs(node)
result.append(oldToNew[node]) # this node just became a brand-new component's entry point
return resultThe return list is sized by component count, not by input node count — every node inside one component is reachable from any single node in it via .neighbors, so recording one entry point per component is enough.
Follow-up: iterative DFS
Swap queue.popleft() for stack.pop() — that's the entire change, since this problem has no notion of "levels" the way tree traversal does.
127. Word Ladder
Find the shortest transformation sequence from beginWord to endWord, changing one letter at a time, where every intermediate word must be in wordList. This is really just unweighted shortest-path BFS, using a word game as the setting. Words are nodes, words that differ by one letter are neighbors, and neighbors are built on the fly (try all 26 letters at every position) instead of read from a fixed adjacency list.
from collections import deque
class Solution:
def ladderLength(self, beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return 0
queue = deque([beginWord])
steps = 1
while queue:
levelSize = len(queue) # same snapshot trick as grid BFS / level order traversal
for _ in range(levelSize):
word = queue.popleft()
if word == endWord:
return steps
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
if c == word[i]:
continue
candidate = word[:i] + c + word[i+1:]
if candidate in wordSet:
wordSet.remove(candidate) # mark visited - never generate it again
queue.append(candidate)
steps += 1
return 0Time: O(N · L² · 26) / Space: O(N · L)
Follow-up: return the actual transformation sequence
Same BFS, plus a parent dictionary recording where each word came from, then walk it backward from endWord once found and reverse.
def findLadder(beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return []
queue = deque([beginWord])
parent = {beginWord: None}
while queue:
word = queue.popleft()
if word == endWord:
path = []
while word is not None:
path.append(word)
word = parent[word]
path.reverse()
return path
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
if c == word[i]:
continue
candidate = word[:i] + c + word[i+1:]
if candidate in wordSet:
wordSet.remove(candidate)
parent[candidate] = word
queue.append(candidate)
return []Follow-up: bidirectional BFS
The search space grows exponentially with depth on one side. Expand from beginWord and endWord at the same time, and stop the moment the two groups touch.
def ladderLengthBidirectional(beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return 0
frontGroup = {beginWord}
backGroup = {endWord}
visited = {beginWord, endWord}
steps = 1
while frontGroup and backGroup:
if len(frontGroup) > len(backGroup):
frontGroup, backGroup = backGroup, frontGroup # always expand the smaller side
nextGroup = set()
for word in frontGroup:
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
if c == word[i]:
continue
candidate = word[:i] + c + word[i+1:]
if candidate in backGroup:
return steps + 1 # the two groups just met
if candidate in wordSet and candidate not in visited:
visited.add(candidate)
nextGroup.add(candidate)
frontGroup = nextGroup
steps += 1
return 0visited has to be tracked separately from wordSet here (rather than just deleting from wordSet the way the single-direction version does), because beginWord isn't guaranteed to be a member of wordSet at all — the problem allows that — so there needs to be a place to mark it "already accounted for" regardless.
Follow-up: Word Ladder II — every shortest path (LC 126)
Two phases: build a level-by-level BFS where parents[word] is a set (multiple words at the same level can reach the same next word), then backtrack from endWord, checking every possible parent.
from collections import defaultdict
def findLadders(beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return []
parents = defaultdict(set)
currentLevel = {beginWord}
found = False
while currentLevel and not found:
wordSet -= currentLevel # remove this whole level at once, not word by word
nextLevel = set()
for word in currentLevel:
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
if c == word[i]:
continue
candidate = word[:i] + c + word[i+1:]
if candidate in wordSet:
nextLevel.add(candidate)
parents[candidate].add(word)
if candidate == endWord:
found = True
currentLevel = nextLevel
if not found:
return []
def backtrack(word):
if word == beginWord:
return [[beginWord]]
paths = []
for p in parents[word]:
for path in backtrack(p):
paths.append(path + [word])
return paths
return backtrack(endWord)The whole-level removal is the detail that makes this correct: if you deleted each candidate from wordSet the moment it was found (like the single-path version does), the second word in the same level that could also reach it would see it as already gone and silently lose that parent. Waiting until the level is fully processed keeps every valid parent visible.
The recursive backtrack doesn't need a final .reverse() the way the iterative parent-pointer version does — it resolves the base case (beginWord) first and appends outward as the recursion unwinds, so the path comes out in the correct order by construction.
Summary
| Problem | The trick |
|---|---|
| 207 Course Schedule | Kahn's BFS: inDegree hits zero only when every prerequisite is done |
| — cycle detection (DFS) | path vs visited — a single visited set can't tell "still on my current path" from "cleared already" |
| 210 Course Schedule II | Same BFS, just replace the counter with an order list |
| 133 Clone Graph | A dictionary that works as both the visited-check and the lookup table |
| — disconnected graph | One entry point per component, not per input node |
| 127 Word Ladder | Grid BFS's snapshot-queue engine, but neighbors are built on the fly |
| — path reconstruction | Parent pointers + reverse (or let recursion build the path outward, and skip the reverse) |
| — bidirectional BFS | Always expand the smaller group; stop the moment the two sides meet |
| 126 Word Ladder II | Parents become a set; remove a whole BFS level at once, not one word at a time |
Main point from today: almost none of this was a new engine. Course Schedule's BFS is grid BFS with a different stopping condition. Clone Graph's dictionary is Number of Islands' visited-set with a value attached to it. And Word Ladder's neighbors are grid BFS's directions, just built instead of given directly.