DFS, BFS, topological sort, and Union-Find. Graphs appear in island problems, dependency ordering, and connected component questions.
Problems: 13
Easy: 0
Medium: 12
Hard: 1
Learning approach: Read the problem. Try the test cases yourself first.
Click Hint if stuck — it guides without spoiling.
Use Show Solution only after a genuine attempt.
Then hit Let's Code to run your solution live.
For each unvisited '1', run DFS to mark all connected land cells as visited ('0'). Count how many times you start a DFS.
Python Solution
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited
dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count
Key idea: DFS flood fill. When we find a '1', increment the count and flood-fill it (marking all connected '1's as '0') so we don't count them again.
Given a reference to a node in a connected undirected graph, return a deep copy of the graph.
Test Cases
# Node has .val and .neighbors list
# Input: node representing graph [[2,4],[1,3],[2,4],[1,3]]
# Output: deep copy with same adjacency
BFSold→new mapO(V+E)
Use a hash map from old node to new node. BFS/DFS to traverse; create new nodes on first visit, link neighbors using the map.
Python Solution
from collections import deque
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors or []
def cloneGraph(node):
if not node:
return None
clone_map = {node: Node(node.val)}
queue = deque([node])
while queue:
curr = queue.popleft()
for neighbor in curr.neighbors:
if neighbor not in clone_map:
clone_map[neighbor] = Node(neighbor.val)
queue.append(neighbor)
clone_map[curr].neighbors.append(clone_map[neighbor])
return clone_map[node]
Key idea: BFS traversal. First visit: create a new node and store in the map. Every visit: link the cloned current node to the cloned neighbor using the map.
DFS from each unvisited '1'. Count cells visited in this DFS (the island area). Return the maximum area found.
Python Solution
def maxAreaOfIsland(grid):
rows, cols = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
return 0
grid[r][c] = 0 # mark visited
return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1)
return max((dfs(r,c) for r in range(rows) for c in range(cols)), default=0)
Key idea: DFS returns the count of cells in the island. Mark cells as 0 to avoid revisiting. Take the max across all islands.
Reverse the problem: BFS from Pacific borders uphill — cells reachable going uphill from Pacific. Same for Atlantic. Answer = intersection.
Python Solution
from collections import deque
def pacificAtlantic(heights):
rows, cols = len(heights), len(heights[0])
def bfs(starts):
visited = set(starts)
queue = deque(starts)
while queue:
r, c = queue.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if (0 <= nr < rows and 0 <= nc < cols
and (nr,nc) not in visited
and heights[nr][nc] >= heights[r][c]):
visited.add((nr,nc))
queue.append((nr,nc))
return visited
pacific_starts = [(r,0) for r in range(rows)] + [(0,c) for c in range(cols)]
atlantic_starts = [(r,cols-1) for r in range(rows)] + [(rows-1,c) for c in range(cols)]
return sorted(bfs(pacific_starts) & bfs(atlantic_starts))
Key idea: Instead of simulating flow downhill, BFS uphill from each ocean's borders. A cell is in the answer if water from it can reach both oceans — i.e., it's reachable (going uphill) from both borders.
Given m×n board of 'X' and 'O', capture all regions of 'O' fully surrounded by 'X' (replace with 'X'). 'O' on borders or connected to border 'O' are NOT captured.
Mark all 'O's connected to the border as safe ('S'). Then flip remaining 'O' to 'X', and 'S' back to 'O'.
Python Solution
def solve(board):
rows, cols = len(board), len(board[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
return
board[r][c] = 'S' # safe — connected to border
dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
# Mark border-connected O's
for r in range(rows): dfs(r, 0); dfs(r, cols-1)
for c in range(cols): dfs(0, c); dfs(rows-1, c)
# Flip: O→X (captured), S→O (safe)
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O': board[r][c] = 'X'
elif board[r][c] == 'S': board[r][c] = 'O'
Key idea: Two-phase approach. First, mark all 'O's reachable from borders as 'S' (safe). Then, convert remaining 'O's to 'X' and restore 'S' to 'O'.
Grid has 0 (empty), 1 (fresh), 2 (rotten). Each minute, rotten oranges make adjacent fresh ones rotten. Return minutes until no fresh oranges remain, or -1.
Start BFS from ALL rotten oranges simultaneously. Track fresh count — decrement as oranges rot. Answer is the time when fresh reaches 0.
Python Solution
from collections import deque
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2: queue.append((r, c, 0))
elif grid[r][c] == 1: fresh += 1
minutes = 0
while queue:
r, c, t = queue.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
minutes = max(minutes, t + 1)
queue.append((nr, nc, t + 1))
return minutes if fresh == 0 else -1
Key idea: Multi-source BFS seeded with all initial rotten oranges. As we spread, we track elapsed time per cell and count fresh oranges. If fresh reaches 0, return the max time seen.
multi-source BFS from gatesdistance propagationO(m·n)
Start BFS from all gates simultaneously. For each reachable empty room, set distance = parent's distance + 1.
Python Solution
from collections import deque
def wallsAndGates(rooms):
rows, cols = len(rooms), len(rooms[0])
INF = 2147483647
queue = deque()
for r in range(rows):
for c in range(cols):
if rooms[r][c] == 0:
queue.append((r, c))
while queue:
r, c = queue.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:
rooms[nr][nc] = rooms[r][c] + 1
queue.append((nr, nc))
Key idea: Multi-source BFS from all gates at once. Each BFS level represents one unit of distance. Fill rooms as we expand — this guarantees shortest distance from a gate.
Build a directed graph. If a topological ordering exists (no cycles), return True. Use Kahn's algorithm: repeatedly process nodes with in-degree 0.
Python Solution
from collections import defaultdict, deque
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, pre in prerequisites:
graph[pre].append(course)
in_degree[course] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
node = queue.popleft()
count += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return count == numCourses
Key idea: Kahn's topological sort. Nodes with in-degree 0 have no prerequisites. Process them and reduce neighbors' in-degrees. If we process all nodes, there's no cycle.
Return the order in which to finish all numCourses given prerequisites. Return empty array if impossible.
Test Cases
findOrder(2, [[1,0]]) → [0,1]
findOrder(4, [[1,0],[2,0],[3,1],[3,2]]) → [0,2,1,3] or [0,1,2,3]
Kahn's with order listO(V+E)
Same as Course Schedule but also track the order nodes are processed. Return order if it equals numCourses.
Python Solution
from collections import defaultdict, deque
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, pre in prerequisites:
graph[pre].append(course)
in_degree[course] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == numCourses else []
Key idea: Kahn's algorithm, same as Course Schedule, but also collect nodes in the order they're processed. That order is a valid topological sort.
Use Union-Find. For each edge, try to union the two nodes. If they're already in the same component, this edge is the redundant one.
Python Solution
def findRedundantConnection(edges):
parent = list(range(len(edges) + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # already connected — redundant edge
parent[py] = px
return True
for u, v in edges:
if not union(u, v):
return [u, v]
Key idea: Union-Find with path compression. Process edges one by one. If both endpoints are already in the same component, the edge creates a cycle — it's the redundant one.
Use Union-Find. Start with n components. For each edge, if union succeeds (nodes were in different components), decrement component count.
Python Solution
def countComponents(n, edges):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return 0
parent[py] = px
return 1
components = n
for u, v in edges:
components -= union(u, v)
return components
Key idea: Start with n components (each node isolated). For each edge, union the endpoints. If they were in different components, decrement the count. The final count is the answer.
A valid tree has exactly n-1 edges and no cycles. Check edge count first. Then use Union-Find to detect cycles.
Python Solution
def validTree(n, edges):
if len(edges) != n - 1:
return False # trees have exactly n-1 edges
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
pu, pv = find(u), find(v)
if pu == pv:
return False # cycle detected
parent[pv] = pu
return True
Key idea: Two conditions for a valid tree: (1) exactly n-1 edges, (2) no cycles. Check condition 1 upfront. Use Union-Find for condition 2.
Given beginWord, endWord, and word list, find shortest transformation sequence length. Each step changes exactly one letter; each intermediate word must be in the list.
BFS where each node is a word. From each word, generate all one-letter variations; if in the word set and unvisited, add to queue.
Python Solution
from collections import deque
def ladderLength(beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + ch + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in wordSet and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
Key idea: BFS on the implicit graph of words. Generate all one-letter mutations. If a mutation is in the word set and unvisited, add to queue. BFS guarantees the shortest path.