Graphs

DFS

Connected components, cycle detection, path existence

BFS

Shortest path (unweighted), level order, min steps

Union-Find

Dynamic connectivity, number of components

Topological Sort

Task ordering with prerequisites (DAG)

Medium Number of Islands

INSIGHT: DFS from each unvisited '1'. "Sink" the island (mark as '0') during DFS to avoid revisiting. Count DFS calls = islands.

def numIslands(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
        grid[r][c] = '0'   # sink
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1; dfs(r, c)
    return count

Medium Course Schedule I & II (Topological Sort)

INSIGHT: DFS with 3 states: 0=unvisited, 1=visiting (in current path), 2=done. If we visit a node with state=1 → cycle. Add to result AFTER all children processed (postorder).

def findOrder(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        graph[b].append(a)
    state = [0] * numCourses
    result = []

    def dfs(node):
        if state[node] == 1: return False   # cycle
        if state[node] == 2: return True    # already done
        state[node] = 1
        for nb in graph[node]:
            if not dfs(nb): return False
        state[node] = 2
        result.append(node)   # add after all deps
        return True

    if not all(dfs(i) for i in range(numCourses)):
        return []
    return result[::-1]   # reverse postorder = topological order

Medium Rotting Oranges (Multi-source BFS)

INSIGHT: Multi-source BFS: start with ALL rotten oranges in queue simultaneously. BFS naturally gives shortest time (all spread at same rate).

from collections import deque

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    fresh = 0; queue = deque()
    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
    max_time = 0
    while queue:
        r, c, t = queue.popleft()
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            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
                max_time = max(max_time, t+1)
                queue.append((nr, nc, t+1))
    return max_time if fresh == 0 else -1

Hard Word Ladder

INSIGHT: BFS for shortest path. Pre-build pattern→words map ("h*t" → ["hot","hat"]). O(1) neighbor lookup instead of O(n·L) brute force.

from collections import deque, defaultdict

def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set: return 0
    patterns = defaultdict(list)
    for w in wordList:
        for i in range(len(w)):
            patterns[w[:i] + '*' + w[i+1:]].append(w)
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    while queue:
        word, steps = queue.popleft()
        if word == endWord: return steps
        for i in range(len(word)):
            for nb in patterns[word[:i] + '*' + word[i+1:]]:
                if nb not in visited:
                    visited.add(nb)
                    queue.append((nb, steps+1))
    return 0

← Dynamic Programming Greedy & Intervals →