Graphs

1. 1.Number of Islands
   Grid as Graph: Connected Components count using DFS/BFS marking land "0"medium
2. 2.Clone Graph
   DFS/BFS + HashMap mapping original node -> copied node to prevent duplicate cloning in cyclesmedium
3. 3.Number of Provinces
   Connected Components in Adjacency Matrix using visited array + DFSmedium
4. 4.Flood Fill
   Grid DFS changing matching initial color cells to new coloreasy
5. 5.Rotting Oranges
   Multi-Source BFS: enqueue all rotten oranges at minute 0 and spread in parallel wavesmedium
6. 6.Course Schedule
   Directed Cycle Detection (0=unvisited, 1=visiting, 2=finished) or Topological Sortmedium
7. 7.Course Schedule II
   Topological Sort (Kahn's BFS or DFS postorder reversed) returning valid orderingmedium
8. 8.Pacific Atlantic Water Flow
   Reverse Multi-Source BFS/DFS starting from ocean boundaries inwardmedium
9. 9.Surrounded Regions
   Boundary DFS: mark border-connected "O"s as safe, capture remaining "O"s to "X"medium
10. 10.Max Area of Island
    Grid DFS returning 1 + sum(dfs(neighbor)) for each connected land massmedium
11. 11.Graph Valid Tree
    Check edges == n - 1 AND graph is fully connected without cyclesmedium
12. 12.Redundant Connection
    Union Find / Disjoint Set: find first edge where find(u) == find(v)medium
13. 13.Is Graph Bipartite?
    BFS/DFS 2-coloring: if neighbor has same color -> return falsemedium
14. 14.Word Ladder
    Unweighted Shortest Path BFS: transform word 1 char at a time checking dictionary sethard
15. 15.Open the Lock
    BFS level-by-level distance rings starting from "0000" avoiding deadendsmedium
16. 16.Evaluate Division
    Weighted Directed Graph: DFS to find product of path weights A -> Bmedium
17. 17.Reorder Routes to Make All Paths Lead to Zero
    Tree DFS from 0 tracking artificial forward edges vs original reverse edgesmedium
18. 18.Shortest Path in Binary Matrix
    8-directional BFS in binary grid from (0,0) to (n-1, n-1)medium
19. 19.Network Delay Time
    Dijkstra's algorithm with Priority Queue for weighted shortest pathmedium
20. 20.Cheapest Flights Within K Stops
    Bellman-Ford / Modified BFS with stop constraint arraymedium

1. 21.Accounts Merge
   Union Find connecting emails belonging to same personmedium
2. 22.Alien Dictionary
   Construct character dependency graph from adjacent words + Topological Sorthard
3. 23.Minimum Height Trees
   Kahn's leaf-trimming BFS until 1 or 2 center nodes remainmedium
4. 24.Find Eventual Safe States
   Reverse graph + Topological Sort / DFS 3-state cycle detectionmedium
5. 25.Keys and Rooms
   Graph reachability BFS/DFS tracking visited rooms starting from room 0medium
6. 26.Possible Bipartition
   Construct dislike graph + BFS/DFS 2-coloringmedium
7. 27.All Paths From Source to Target
   DAG DFS + Backtracking appending path from 0 to n-1medium
8. 28.Detonate the Maximum Bombs
   Directed graph where edge u -> v exists if dist(u, v) <= radius(u); run DFS from each bombmedium
9. 29.Find Closest Node to Given Two Nodes
   Run 2 BFS passes from node1 and node2 to compute distance arraysmedium
10. 30.Minimum Genetic Mutation
    BFS gene mutation string transformation in bank setmedium

How to Think

1. Things are connected to other things?Graph (Nodes & Edges)
2. Need explore connected area?DFS / BFS + Visited Set
3. Need count groups?Connected Components
4. Need shortest path with every edge same cost?BFS (Level-by-level rings)
5. Need detect cycle?DFS 3-state / Union Find
6. Dependencies / prerequisites?Directed Graph + Topological Sort
7. Weighted shortest path?Dijkstra (non-negative weights)

// 1. Graph DFS (Adjacency List + Visited Set)
func graphDFS(n int, edges [][]int) {
    adj := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        adj[u] = append(adj[u], v)
        adj[v] = append(adj[v], u) // Undirected: Add both!
    }

    visited := make([]bool, n)
    var dfs func(u int)
    dfs = func(u int) {
        visited[u] = true
        for _, neighbor := range adj[u] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            dfs(i) // Discover each connected component
        }
    }
}

// 2. Unweighted Shortest Path BFS (Mark visited WHEN ENQUEUED!)
func shortestPathBFS(n int, edges [][]int, start, target int) int {
    adj := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        adj[u] = append(adj[u], v)
        adj[v] = append(adj[v], u)
    }

    visited := make([]bool, n)
    queue := []int{start}
    visited[start] = true // Mark when enqueued!
    dist := 0

    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            curr := queue[0]
            queue = queue[1:]
            if curr == target {
                return dist
            }
            for _, neighbor := range adj[curr] {
                if !visited[neighbor] {
                    visited[neighbor] = true // Mark when enqueued!
                    queue = append(queue, neighbor)
                }
            }
        }
        dist++
    }
    return -1
}

Visited Set & Mandatory BFS Enqueue Rule

Grid as Graph & Multi-Source BFS

Graph            → Nodes + Edges (May contain cycles & disconnected components)
Visited Set      → MANDATORY to prevent infinite loops (Mark WHEN ENQUEUED in BFS!)
Unweighted Path  → BFS guaranteed shortest distance in level-by-level rings
Multi-Source BFS → Push ALL initial sources into queue at minute 0 simultaneously
Shortest Path    → Unweighted (BFS) | Non-negative (Dijkstra) | Negative (Bellman-Ford)

Common Interview Mistakes

Interview Rules

1. 1. Things connected to other things?→ Graph (Nodes & Edges)
2. 2. Explore connected area? → DFS / BFS + Visited Set
3. 3. Count connected components?→ Loop over all nodes; if unvisited, increment count & run DFS/BFS
4. 4. Unweighted shortest path? → BFS (Level-by-level distance rings)
5. 5. Prerequisites / Dependencies? → Directed Graph + Topological Sort
6. 6. Multi-Source expansion (Rotting Oranges)? → Push ALL initial sources into queue at minute 0
7. 7. Weighted shortest path? → Dijkstra (non-negative weights) | Bellman-Ford (negative weights)
8. 8. Overall Complexity → Time: O(V + E) | Space: O(V + E)

Graph            → Nodes + Edges
DFS              → Go deep
BFS              → Level by level
Visited          → Prevent repeats & cycles
Components       → Count groups
Shortest Path    → BFS (unweighted)
Multi-Source BFS → All starts at once
Dependencies     → Directed Graph
Weighted Path    → Dijkstra
Time             → O(V + E)

💡 Golden Rule: "Turn the problem into ‘What are the nodes, what are the edges, and how should I explore the neighbors?’"