Data Structures & Algorithms

Used for finding subarrays or substrings that satisfy a condition (e.g. "Longest substring without repeating characters").

// Template: Variable Sliding Window
left := 0
for right := 0; right < len(arr); right++ {
    // 1. Add arr[right] to window state
    // 2. While window is invalid:
    //      Remove arr[left] from window state
    //      left++
    // 3. Update max/min result
}

Used for sorted arrays or linked lists. (e.g. "Two Sum II", "Valid Palindrome", "Container With Most Water").

left, right := 0, len(arr)-1
for left < right {
    sum := arr[left] + arr[right]
    if sum == target { return true }
    if sum < target { left++ } else { right-- }
}

Used for cycle detection in Linked Lists or Arrays (Floyd's Tortoise and Hare). Find middle of linked list.

slow, fast := head, head
for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
    if slow == fast { return true } // Cycle detected
}

Not just for sorted arrays! Used anytime the "answer space" is monotonic (e.g. Koko Eating Bananas).

left, right := 0, len(arr)-1
for left <= right {
    mid := left + (right-left)/2
    if arr[mid] == target { return mid }
    if arr[mid] < target { left = mid + 1 } else { right = mid - 1 }
}

Graph traversal on 2D grids (Number of Islands, Rotten Oranges).

// DFS Template for Grid
func dfs(grid [][]byte, r, c int) {
    if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] == '0' { return }
    grid[r][c] = '0' // Mark visited
    dfs(grid, r+1, c); dfs(grid, r-1, c); dfs(grid, r, c+1); dfs(grid, r, c-1)
}

Anytime you see "Top K", "Kth largest", or "K closest", use a Heap (Priority Queue). A Min-Heap of size K keeps the K largest elements (since the smallest of the largest is at the top, ready to be popped).

Optimizing recursion by storing intermediate results. Two approaches:

• Top-Down (Memoization): Recursion + HashMap to cache results. Easiest to write.
• Bottom-Up (Tabulation): Iteration + Array. Better space complexity (can often optimize to O(1) space, e.g. Fibonacci only needs last 2 variables).

Many problems are graphs in disguise (prerequisites, social networks, routes).

// Build adjacency list
graph := make(map[int][]int)
for _, edge := range edges {
    graph[edge[0]] = append(graph[edge[0]], edge[1])
    graph[edge[1]] = append(graph[edge[1]], edge[0]) // undirected
}

// BFS — shortest path in unweighted graph
func bfs(graph map[int][]int, start int) map[int]int {
    dist := map[int]int{start: 0}
    queue := []int{start}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        for _, neighbor := range graph[node] {
            if _, visited := dist[neighbor]; !visited {
                dist[neighbor] = dist[node] + 1
                queue = append(queue, neighbor)
            }
        }
    }
    return dist
}

// Topological Sort (for DAGs — course prerequisites, build order)
// Using Kahn's algorithm (BFS-based)
func topologicalSort(numCourses int, prerequisites [][]int) []int {
    inDegree := make([]int, numCourses)
    graph := make(map[int][]int)
    for _, p := range prerequisites {
        graph[p[1]] = append(graph[p[1]], p[0])
        inDegree[p[0]]++
    }
    
    queue := []int{}
    for i, d := range inDegree {
        if d == 0 { queue = append(queue, i) }
    }
    
    var order []int
    for len(queue) > 0 {
        node := queue[0]; queue = queue[1:]
        order = append(order, node)
        for _, next := range graph[node] {
            inDegree[next]--
            if inDegree[next] == 0 { queue = append(queue, next) }
        }
    }
    if len(order) != numCourses { return nil } // cycle detected
    return order
}

Generate all combinations, permutations, or subsets. Think of it as DFS on a decision tree.

// Template: Generate all subsets
func subsets(nums []int) [][]int {
    var result [][]int
    var current []int
    
    var backtrack func(start int)
    backtrack = func(start int) {
        // Make a copy of current and add to result
        temp := make([]int, len(current))
        copy(temp, current)
        result = append(result, temp)
        
        for i := start; i < len(nums); i++ {
            current = append(current, nums[i])  // choose
            backtrack(i + 1)                     // explore
            current = current[:len(current)-1]   // un-choose (backtrack)
        }
    }
    
    backtrack(0)
    return result
}
// Key insight: "choose, explore, un-choose"

Find the "next greater/smaller element" in O(n). Stack maintains monotonic order.

// Next Greater Element
func nextGreaterElement(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    for i := range result { result[i] = -1 }
    
    stack := []int{} // stores indices
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[idx] = nums[i]
        }
        stack = append(stack, i)
    }
    return result
}
// Also used in: Largest Rectangle in Histogram, Daily Temperatures

Efficient storage and retrieval of strings. Used for autocomplete, spell check, IP routing.

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd    bool
}

type Trie struct {
    root *TrieNode
}

func NewTrie() *Trie {
    return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if _, ok := node.children[ch]; !ok {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.root
    for _, ch := range word {
        if _, ok := node.children[ch]; !ok { return false }
        node = node.children[ch]
    }
    return node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    node := t.root
    for _, ch := range prefix {
        if _, ok := node.children[ch]; !ok { return false }
        node = node.children[ch]
    }
    return true
}

Track connected components. Used for: Number of Islands, Graph connectivity, Kruskal's MST.

type UnionFind struct {
    parent []int
    rank   []int
}

func NewUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    rank := make([]int, n)
    for i := range parent { parent[i] = i }
    return &UnionFind{parent, rank}
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x]) // path compression
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) bool {
    px, py := uf.Find(x), uf.Find(y)
    if px == py { return false } // already connected
    // Union by rank
    if uf.rank[px] < uf.rank[py] { px, py = py, px }
    uf.parent[py] = px
    if uf.rank[px] == uf.rank[py] { uf.rank[px]++ }
    return true
}