Graphs Cheat Sheet

What is Graphs?

Model relationships and connections between entities.

Template Code

def numIslands(grid: List[List[str]]) -> int:
    if not grid:
        return 0
    
    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:
            return
        if grid[r][c] != &#039;1':
            return
        
        grid[r][c] = &#039;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] == &#039;1':
                count += 1
                dfs(r, c)
    
    return count

Complexity

Common Variations

• Basic Graphs
• Graphs with constraints
• Optimized Graphs

Practice Problems