Graph

Breadth-First Traversal (BFS)

• BFS naturally finds the shortest path to a node

from collections import deque

def bfs(graph, root):
    visited = set([root])
    queue = deque([root])
    result = []

    while queue:
        curr = popleft()
        result.append(curr)

        for neighbor in graph[curr]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return result

Depth-First Search (DFS)

def dfsRecursive(graph, root, visited):
    visited.add(root)
    print(root.val)

    for neighbor in graph[root]:
        if root not in visited:
            dfsRecursive(graph, neighbor, visited)

def dfsIterative(graph, root):
    visited = set()
    stack = [root]

    while stack:
        curr = stack.pop()
        print(curr.val)
        visited.add(curr)

        for neighbor in graph[curr]:
            if neighbor not in visited:
                stack.append(neighbor)

Topological Sort (Kahn's Algorithm)

from collections import deque, defaultdict

def topologicalSort(nodes, edges):
    # Which nodes have current node as a prerequisite?
    # { prereqNode: [nodes] }
    neighbors = defaultdict(list)
    # How many prerequisites does the current node have?
    # { node: prereqCount }
    indegree = {}

    # Add all nodes. Edges may not include all nodes
    for node in nodes:
        indegree[node] = 0

    for prereq, node in edges:
        neighbors[prereq].append(node)
        indegree[node] += 1

    # breadth first traversal
    queue = deque([node for node in nodes if indegree[node] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in neighbors[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    # Cycle exists if unequal lengths
    return result if len(result) == len(nodes) else []

def numIslands(grid: List[List[str]]) -> int:
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    m, n, count = len(grid), len(grid[0]), 0

    for row in range(m):
        for col in range(n):
            if grid[row][col] == "1":
                count += 1
                stack = [(row, col)]
                # Iterative depth-first traversal, mark entire island as visited
                while stack:
                    r, c = stack.pop()
                    for d in directions:
                        newR, newC = r + d[0], c + d[1]
                        if 0 <= newR < m and 0 <= newC < n and grid[newR][newC] == "1":
                            grid[newR][newC] = "2"
                            stack.append((newR, newC))

    return count

Time: O(m * n)

Space: O(m * n)

Alternative solution:

def numIslands(grid: List[List[str]]) -> int:
    def dfs(row, col):
        if not 0 <= row < len(grid) or not 0 <= col < len(grid[0]) or grid[row][col] != "1":
            return

        grid[row][col] = "2"
        dfs(row, col - 1)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row + 1, col)

    count = 0

    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if grid[row][col] == "1":
                count += 1
                dfs(row, col)

    return count

Time: O(m * n)

Space: O(m * n)

def solve(board: List[List[str]]) -> None:
    def dfs(row, col):
        if not 0 <= row < len(board) or not 0 <= col < len(board[0]) or board[row][col] != "O":
            return

        board[row][col] = "L"
        dfs(row, col - 1)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row + 1, col)

    # Regions on the border will not be surrounded. Mark them as safe
    for row in (0, len(board) - 1):
        for col in range(len(board[0])):
            if board[row][col] == "O":
                dfs(row, col)
    for col in (0, len(board[0]) - 1):
        for row in range(len(board)):
            if board[row][col] == "O":
                dfs(row, col)

    # Revert marked regions and capture everything else
    for row in range(len(board)):
        for col in range(len(board[0])):
            if board[row][col] == "O":
                board[row][col] = "X"
            elif board[row][col] == "L":
                board[row][col] = "O"

Time: O(m * n)

Space: O(m * n)

from collections import deque

def cloneGraph(node: Optional['Node']) -> Optional['Node']:
    if not node: return None

    # Key: old node; Value: new node
    visited, d = { node: Node(node.val)}, deque([node])

    # Iterative breadth first traversal
    while d:
        curr = d.popleft()
        for neighbor in curr.neighbors:
            if neighbor not in visited:
                d.append(neighbor)
                visited[neighbor] = Node(neighbor.val)
            visited[curr].neighbors.append(visited[neighbor])

    return visited[node]

Time: O(V + E), V = vertices, E = edges

Space: O(V) excluding output

Alternative solution:

def cloneGraph(node: Optional['Node']) -> Optional['Node']:
    if not node: return None

    # Key: old node; Value: new node
    visited = {}

    # Recursive depth first traversal
    def dfs(node):
        if node not in visited:
            visited[node] = Node(node.val)
            for neighbor in node.neighbors:
                visited[node].neighbors.append(dfs(neighbor))
        return visited[node]

    return dfs(node)

Time: O(V + E), V = vertices, E = edges

Space: O(V) excluding output

def calcEquation(equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
    # Build weighted graph using nested map
    # { val: { neighbor: weight } }
    m = {}
    for i in range(len(equations)):
        x, y = equations[i]
        if x not in m:
            m[x] = { y: values[i] }
        else:
            m[x][y] = values[i]
        # Include reciprocal as weight in opposite direction
        if y not in m:
            m[y] = { x: 1 / values[i] }
        else:
            m[y][x] = 1 / values[i]

    # Iterative depth first search
    def findPath(start, end):
        if start not in m or end not in m:
            return -1

        # Stack stores (value, product of current path)
        # If (a / b = x) and (b / c = y) then (a / c = x * y)
        visited, stack = set(), [(start, 1)]

        while stack:
            curr, product = stack.pop()
            if curr == end:
                return product

            visited.add(curr)
            for neighbor, weight in m[curr].items():
                if neighbor not in visited:
                    stack.append((neighbor, weight * product))

        return -1

    return [findPath(x, y) for x, y in queries]

Time: O(Q * (V + E)), Q = queries, V = vertices, E = edges

Space: O(V + E)

from collections import deque

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    # { prereq: [courses with prereq] }
    neighbors = defaultdict(list)
    # Track how many prereqs a course has
    indegree = {i: 0 for i in range(numCourses)}

    for node, prereq in prerequisites:
        indegree[node] += 1
        neighbors[prereq].append(node)

    # Breadth first topological sort
    queue = deque([c for c in range(numCourses) if indegree[c] == 0])
    completed = 0

    while queue:
        course = queue.popleft()
        completed += 1

        for neighbor in neighbors[course]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return completed == numCourses

Time: O(V + E), V = nodes, E = edges

Space: O(V + E)

def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    # Breadth first topological sort
    neighbors = defaultdict(list)
    indegree = {i: 0 for i in range(numCourses)}

    for course, prereq in prerequisites:
        indegree[course] += 1
        neighbors[prereq].append(course)

    queue = deque([c for c in range(numCourses) if indegree[c] == 0])
    result = []

    while queue:
        prereq = queue.popleft()
        result.append(prereq)

        for course in neighbors[prereq]:
            indegree[course] -= 1
            if indegree[course] == 0:
                queue.append(course)

    return result if len(result) == numCourses else []

Time: O(V + E), V = nodes, E = edges

Space: O(V + E)

from collections import deque

def snakesAndLadders(board: List[List[int]]) -> int:
    end = len(board) ** 2

    # Calculate coordinates now to avoid repeated work later
    coords = [None] * (end + 1)
    for square in range(1, end + 1):
        i = square - 1
        row = len(board) - (i // len(board)) - 1
        col = i % len(board)
        if (len(board) - row - 1) % 2 != 0:
            col = len(board) - col - 1
        coords[square] = (row, col)

    visited = [False] * (end + 1)
    visited[1] = True

    queue = deque([1])
    # Track number of rolls i.e. BFS level
    moves = 0

    while queue:
        for _ in range(len(queue)):
            curr = queue.popleft()
            for i in range(1, 7):
                if curr + i > end: continue

                row, col = coords[curr + i]
                newPos = board[row][col] if board[row][col] != -1 else curr + i

                # First time reaching square is guaranteed minimum moves
                if newPos == end:
                    return moves + 1

                if not visited[newPos]:
                    queue.append(newPos)
                    visited[newPos] = True

        # Increment after looping because value applies to
        #   nodes in queue before popping
        moves += 1

    return -1

Time: O(n²)

Space: O(n²)

from collections import deque

def minMutation(startGene: str, endGene: str, bank: List[str]) -> int:
    bank, visited, choices = set(bank), set(), ["A", "C", "G", "T"]
    queue = deque([startGene])
    mutations = 0

    # Breadth first search
    while queue:
        for _ in range(len(queue)):
            curr = queue.popleft()

            for i in range(8):
                for choice in choices:
                    newGene = curr[:i] + choice + curr[i + 1:]

                    if newGene not in bank:
                        continue
                    if newGene == endGene:
                        return mutations + 1

                    if newGene not in visited:
                        queue.append(newGene)
                        visited.add(newGene)
        mutations += 1

    return -1

Time: O(N * L²) or O(N), N = bank size, L = string length = 8

Space: O(NL) or O(N)

class Trie:
    def __init__(self):
        # Simulate graph nodes with nested maps. Use "#" to end word
        # "apple" -> {a: {p: {p: {l: {e: {"#": True}}}}}}
        self.head = {}

    def insert(self, word: str) -> None:
        node = self.head
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node["#"] = True

    def search(self, word: str) -> bool:
        node = self.head
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return "#" in node

    def startsWith(self, prefix: str) -> bool:
        node = self.head
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True

class WordDictionary:
    def __init__(self):
        # Simulate graph nodes with nested maps. Use "#" to end word
        # "apple" -> {a: {p: {p: {l: {e: {"#": True}}}}}}
        self.head = {}

    def addWord(self, word: str) -> None:
        node = self.head
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node["#"] = {}

    def search(self, word: str) -> bool:
        def dfs(i, charMap):
            if i >= len(word):
                return "#" in charMap

            char = word[i]

            if char != ".":
                if char not in charMap:
                    return False
                return dfs(i + 1, charMap[char])
            else:
                for key in charMap:
                    if dfs(i + 1, charMap[key]):
                        return True
                return False

        return dfs(0, self.head)