Graph BFS

1. 1.Shortest Path in Binary Matrix
   8-directional BFS in binary grid from (0,0) to (n-1, n-1) with distance ring incrementmedium
2. 2.Rotting Oranges
   Multi-Source BFS: enqueue all initial rotten oranges at minute 0 and spread rot in parallel wavesmedium
3. 3.Word Ladder
   Implicit Graph BFS: transform 1 character at a time checking dictionary set; Bidirectional BFS optimizes search spacehard
4. 4.Open the Lock
   Implicit State BFS: 8 wheel-turn neighbor combinations starting from "0000" avoiding deadendsmedium
5. 5.Number of Islands
   Grid BFS: start BFS on unvisited "1"s and mark connected land mass to "0"medium
6. 6.Number of Provinces
   Adjacency Matrix BFS: loop over all nodes; if unvisited, run BFS to mark componentmedium
7. 7.Clone Graph
   Queue BFS + HashMap mapping original node -> copied node to prevent cycle duplicatesmedium
8. 8.Flood Fill
   4-directional Grid BFS changing matching initial color cells to new coloreasy
9. 9.01 Matrix
   Multi-Source BFS: enqueue all zero cells at distance 0 and expand outward to calculate distance to nearest 0medium
10. 10.Walls and Gates
    Multi-Source BFS: enqueue all gates (0) at once and update room distances in expanding ringsmedium
11. 11.Minimum Genetic Mutation
    BFS gene string mutation in bank set with 1-character difference edgesmedium
12. 12.Keys and Rooms
    BFS reachability starting from room 0 enqueuing newly unlocked room keysmedium
13. 13.Snakes and Ladders
    Board BFS converting 1D board index to 2D matrix coordinates + dice roll moves (1..6)medium
14. 14.As Far from Land as Possible
    Multi-Source BFS starting from all land cells (1) outward into water cells (0)medium
15. 15.Shortest Bridge
    1. DFS to find & mark first island -> 2. Multi-Source BFS from first island cells to reach second islandmedium
16. 16.Minimum Knight Moves
    8-directional knight move offsets BFS from (0,0) to target (x,y) with quadrant symmetrymedium
17. 17.Bus Routes
    Bipartite Route/Stop Graph BFS: queue bus routes and track visited routes & stopshard
18. 18.Jump Game III
    BFS from start index moving to i + arr[i] and i - arr[i] checking for value 0medium
19. 19.Nearest Exit from Entrance in Maze
    Grid BFS level rings starting from entrance to reach boundary empty cellmedium
20. 20.Detonate the Maximum Bombs
    Run BFS from each bomb as source; directed edge exists if dist(u,v) <= radius(u)medium

1. 21.Perfect Squares
   State BFS: starting at n, subtract perfect squares (1, 4, 9...) level-by-level until 0medium
2. 22.Word Ladder II
   BFS to build parent predecessor DAG + DFS Backtracking to construct all shortest pathshard
3. 23.All Nodes Distance K in Binary Tree
   Convert Binary Tree to Undirected Graph (adding parent pointers) + BFS distance Kmedium
4. 24.Shortest Path Visiting All Nodes
   Bitmask BFS: queue tuple (currNode, visitedBitmask) with 2^N state spacehard
5. 25.Minimum Operations to Convert Number
   Implicit State BFS: apply +, -, ^ operations on current x to reach goalmedium
6. 26.Shortest Path with Alternating Colors
   BFS with tuple state (node, edgeColor) expanding via red/blue alternating edgesmedium
7. 27.Minimum Jumps to Reach Home
   BFS with state (position, jumpedBackwardsBool) obeying backward jump constraintsmedium
8. 28.Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
   Bitmask State BFS flipping 3x3 binary matrix cells to zero statehard

How to Think

1. Need shortest path with equal-cost edges?BFS (Level-by-level distance rings)
2. Need minimum number of moves / steps?BFS
3. Many starting points spread together?Multi-Source BFS
4. Need nearest node/state?BFS
5. Graph has cycles?BFS + Visited Set (Mark when ENQUEUED!)

// 1. Level-by-Level Distance BFS (Equal-Cost Shortest Path)
func shortestPathBFS(n int, graph [][]int, start, target int) int {
    queue := []int{start}
    head := 0 // Head pointer avoids O(N) slice reallocation!

    visited := make([]bool, n)
    visited[start] = true // Mark WHEN ENQUEUED!

    distance := 0

    for head < len(queue) {
        levelSize := len(queue) - head
        for i := 0; i < levelSize; i++ {
            curr := queue[head]
            head++

            if curr == target {
                return distance
            }

            for _, next := range graph[curr] {
                if !visited[next] {
                    visited[next] = true // Mark WHEN ENQUEUED!
                    queue = append(queue, next)
                }
            }
        }
        distance++
    }
    return -1
}

// 2. Multi-Source BFS (Rotting Oranges)
func orangesRotting(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])
    queue := [][2]int{}
    freshCount := 0

    // Enqueue ALL initial sources at minute 0!
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == 2 {
                queue = append(queue, [2]int{r, c})
            } else if grid[r][c] == 1 {
                freshCount++
            }
        }
    }

    if freshCount == 0 { return 0 }

    minutes := 0
    dirs := [][2]int{{-1,0}, {1,0}, {0,-1}, {0,1}}

    for len(queue) > 0 {
        size := len(queue)
        spread := false
        for i := 0; i < size; i++ {
            curr := queue[0]
            queue = queue[1:]
            r, c := curr[0], curr[1]

            for _, d := range dirs {
                nr, nc := r+d[0], c+d[1]
                if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 {
                    grid[nr][nc] = 2 // Mark rotten WHEN ENQUEUED!
                    freshCount--
                    spread = true
                    queue = append(queue, [2]int{nr, nc})
                }
            }
        }
        if spread { minutes++ }
    }

    if freshCount > 0 { return -1 }
    return minutes
}

Mandatory BFS Rule: Mark Visited When ENQUEUED

Multi-Source BFS & Path Reconstruction

Graph BFS        → Queue FIFO level-by-level ring expansion (Equal-Cost Shortest Path)
Enqueue Rule     → Mark visited[neighbor] = true WHEN ENQUEUED (Not when popped!)
Multi-Source BFS → Push ALL initial sources into queue at minute 0 simultaneously
Parent Map       → Store parent[next] = curr to trace back actual shortest path sequence
Equal-Cost Only  → BFS requires equal edge costs! If weighted, use Dijkstra's algorithm.

Common Interview Mistakes

Interview Rules

1. 1. Minimum moves / equal-cost shortest path? → Graph BFS
2. 2. Queue data structure? → Queue FIFO (using head index in Go)
3. 3. When to mark visited? → Mark visited[neighbor] = true WHEN ENQUEUED
4. 4. Multiple starting points? → Multi-Source BFS (enqueue all initial sources at minute 0)
5. 5. Actual path sequence required? → Store parent[next] = curr and trace back from target
6. 6. Large state space + known target? → Bidirectional BFS (meeting in the middle)
7. 7. Non-equal weighted edges?→ Dijkstra's Priority Queue algorithm
8. 8. Overall Complexity → Time: O(V + E) | Space: O(V)

Graph BFS        → Queue
Visited          → Mark when discovered
BFS Wave         → Distance 0, 1, 2, 3...
Equal-cost path  → BFS
Minimum moves    → BFS
Multi-Source     → All starts in queue at minute 0
Actual path      → Parent map
Weighted edges   → Dijkstra
Time             → O(V + E)

💡 Golden Rule: "If every move costs the same, BFS explores states in exactly the order of their shortest distance from the start."