Algorithm & Data Structure Cheatsheet

Big O complexity plus, for each data structure and pattern, how to recognise it, a template in Go, Python and TypeScript, common variants and classic problems.

Updated: 2026-10-06

25 entries

Big O complexity

Growth rates from fastest to slowest, with typical complexities for common algorithms and data structures.

Big O growth ratesLine chart of operations against input size n from 1 to 10 for O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) and O(n!). Factorial and exponential growth leave the chart first.02550751001246810n (input size)operationsO(1)O(log n)O(n)O(n log n)O(n²)O(2ⁿ)O(n!)
Big O classes with growth name, operations at n = 1,000, and typical examples
NotationGrowthOps at n = 1,000Typical examples
O(1)Constant1Hash map lookup, array index
O(log n)Logarithmic10Binary search, heap push/pop
O(n)Linear1,000Single pass, sliding window
O(n log n)Linearithmic10,000Merge sort, heap sort, sort + scan
O(n²)Quadratic1,000,000Nested loops, 2D DP table
O(2ⁿ)Exponential—Subsets, naive recursion
O(n!)Factorial—Permutations, brute-force TSP

Common algorithms and data structures

Sorting

  • Quick sort
    Best
    O(n log n)
    Average
    O(n log n)
    Worst
    O(n²)
    Space
    O(log n)

    Not stable; random pivot avoids the worst case.

  • Merge sort
    Best
    O(n log n)
    Average
    O(n log n)
    Worst
    O(n log n)
    Space
    O(n)

    Stable; good for linked lists.

  • Heap sort
    Best
    O(n log n)
    Average
    O(n log n)
    Worst
    O(n log n)
    Space
    O(1)

    In place, not stable.

  • Insertion sort
    Best
    O(n)
    Average
    O(n²)
    Worst
    O(n²)
    Space
    O(1)

    Fast on nearly sorted or tiny inputs.

  • Counting sort
    Best
    O(n + k)
    Average
    O(n + k)
    Worst
    O(n + k)
    Space
    O(k)

    k is the value range.

Searching

  • Linear search
    Best
    O(1)
    Average
    O(n)
    Worst
    O(n)
    Space
    O(1)
  • Binary search
    Best
    O(1)
    Average
    O(log n)
    Worst
    O(log n)
    Space
    O(1)

    Requires sorted or monotonic input.

Data structures

  • Array / slice
    Best
    O(1) access
    Average
    O(n) search/insert
    Worst
    O(n) search/insert
    Space
    O(n)

    Append is amortised O(1).

  • Linked list
    Best
    O(1) insert at known node
    Average
    O(n) search
    Worst
    O(n) search
    Space
    O(n)
  • Hash map
    Best
    O(1)
    Average
    O(1)
    Worst
    O(n)
    Space
    O(n)

    Worst case needs heavy collisions.

  • BST (balanced)
    Best
    O(log n)
    Average
    O(log n)
    Worst
    O(n) unbalanced
    Space
    O(n)
  • Binary heap
    Best
    O(1) peek
    Average
    O(log n) push/pop
    Worst
    O(log n) push/pop
    Space
    O(n)

    Building from an array is O(n).

  • Trie
    Best
    O(L)
    Average
    O(L)
    Worst
    O(L)
    Space
    O(N·L)

    L is the key length.

  • Union find
    Best
    O(α(n))
    Average
    O(α(n))
    Worst
    O(α(n))
    Space
    O(n)

    With path compression and union by size; α is the inverse Ackermann function.

  • Stack / queue
    Best
    O(1)
    Average
    O(1)
    Worst
    O(1)
    Space
    O(n)

    Push/pop/enqueue/dequeue.

Graph algorithms

  • BFS / DFS
    Best
    O(V + E)
    Average
    O(V + E)
    Worst
    O(V + E)
    Space
    O(V)
  • Dijkstra (heap)
    Best
    O((V + E) log V)
    Average
    O((V + E) log V)
    Worst
    O((V + E) log V)
    Space
    O(V)

    Non-negative weights only.

  • Bellman-Ford
    Best
    O(E)
    Average
    O(V·E)
    Worst
    O(V·E)
    Space
    O(V)

    Handles negative edges, detects negative cycles.

  • Topological sort
    Best
    O(V + E)
    Average
    O(V + E)
    Worst
    O(V + E)
    Space
    O(V)
  • Kruskal (MST)
    Best
    O(E log E)
    Average
    O(E log E)
    Worst
    O(E log E)
    Space
    O(V)

Data structures

Array / Slice

O(1) access / O(n) insert / O(n)

Contiguous storage with O(1) index access; prefix sums turn range queries into subtraction.

How to recognise it

  • Repeated range-sum or range-count queries → prefix sum
  • In-place rewrite of an array → read/write indices
  • Matrix traversal → direction arrays or layer-by-layer bounds
Go
// Prefix sum: sum of a[l..r] inclusive
func buildPrefix(a []int) []int {
    pre := make([]int, len(a)+1)
    for i, v := range a {
        pre[i+1] = pre[i] + v
    }
    return pre
}

func rangeSum(pre []int, l, r int) int {
    return pre[r+1] - pre[l]
}

// Subarray sum equals k: prefix sum + hash map (LC 560)
func subarraySum(nums []int, k int) int {
    count, sum := 0, 0
    seen := map[int]int{0: 1}
    for _, v := range nums {
        sum += v
        count += seen[sum-k]
        seen[sum]++
    }
    return count
}

// Difference array: add delta to every a[l..r]
func applyRangeAdds(n int, ops [][3]int) []int { // ops: {l, r, delta}
    diff := make([]int, n+1)
    for _, op := range ops {
        diff[op[0]] += op[2]
        diff[op[1]+1] -= op[2]
    }
    res := make([]int, n)
    run := 0
    for i := 0; i < n; i++ {
        run += diff[i]
        res[i] = run
    }
    return res
}

Common variants

  • Prefix sum → pre[i+1] = pre[i] + a[i]; sum(l..r) = pre[r+1] - pre[l]
  • Prefix sum + hash map → Count subarrays with sum k: look up pre - k seen so far
  • Difference array → Many range increments → +1 at l, -1 at r+1, then prefix-sum once
  • Go slice aliasing → append may share the backing array; copy before mutating

Classic problems

Linked List

O(n) / O(1)

Nodes joined by pointers; reverse, merge and cycle problems rely on dummy heads and fast/slow pointers.

How to recognise it

  • Head may change → dummy node
  • Cycle, middle or k-th from end → fast/slow pointers
  • Reorder without extra space → reverse in place
Go
type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for cur := head; cur != nil; {
        next := cur.Next
        cur.Next = prev
        prev, cur = cur, next
    }
    return prev
}

// Dummy head: the result head may change
func mergeTwoLists(a, b *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for a != nil && b != nil {
        if a.Val <= b.Val {
            tail.Next, a = a, a.Next
        } else {
            tail.Next, b = b, b.Next
        }
        tail = tail.Next
    }
    if a != nil {
        tail.Next = a
    } else {
        tail.Next = b
    }
    return dummy.Next
}

// Fast/slow pointers: entry node of the cycle, or nil
func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
        if slow == fast {
            for p := head; p != slow; p, slow = p.Next, slow.Next {
            }
            return slow
        }
    }
    return nil
}

// Remove the n-th node from the end: gap of n between two pointers
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    fast, slow := dummy, dummy
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    for fast.Next != nil {
        fast, slow = fast.Next, slow.Next
    }
    slow.Next = slow.Next.Next
    return dummy.Next
}

Common variants

  • Reverse a list → prev / cur / next three-pointer loop
  • Merge two sorted lists → Dummy head, append the smaller node
  • Cycle entry → After fast meets slow, restart one at head; they meet at the entry
  • LRU cache → Hash map + doubly linked list for O(1) get/put

Classic problems

Stack / Queue

O(1) per op / O(n)

LIFO and FIFO containers; stacks match nested structure, queues drive level-order traversal.

How to recognise it

  • Matching brackets or nested structure → stack
  • Undo / most recent first → stack
  • Level by level or shortest steps → queue
Go
// Valid parentheses (LC 20)
func isValid(s string) bool {
    pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}
    stack := []byte{}
    for i := 0; i < len(s); i++ {
        c := s[i]
        if open, ok := pairs[c]; ok {
            if len(stack) == 0 || stack[len(stack)-1] != open {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, c)
        }
    }
    return len(stack) == 0
}

// Min stack (LC 155): a parallel stack of running minimums
type MinStack struct{ st, mins []int }

func (m *MinStack) Push(x int) {
    m.st = append(m.st, x)
    if len(m.mins) == 0 || x <= m.mins[len(m.mins)-1] {
        m.mins = append(m.mins, x)
    }
}

func (m *MinStack) Pop() {
    if m.st[len(m.st)-1] == m.mins[len(m.mins)-1] {
        m.mins = m.mins[:len(m.mins)-1]
    }
    m.st = m.st[:len(m.st)-1]
}

func (m *MinStack) Min() int { return m.mins[len(m.mins)-1] }

// Queue skeleton: slice as FIFO (add a visited set for graphs)
func bfsOrder(start int, neighbors func(int) []int) []int {
    queue := []int{start}
    order := []int{}
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        order = append(order, cur)
        queue = append(queue, neighbors(cur)...)
    }
    return order
}

Common variants

  • Valid parentheses → Push openers, pop and compare on closers
  • Min stack → Keep a parallel stack of running minimums
  • Queue with two stacks → Move in → out only when out is empty (amortised O(1))
  • Deque → Both ends O(1): sliding-window maximum, 0-1 BFS

Classic problems

Hash Map

O(1) avg / O(n)

Key to value lookup in O(1) average; use it to trade space for time, count, group and deduplicate.

How to recognise it

  • "Have I seen this before?" → set / map
  • Pair, complement or count problems → map of value → index/count
  • Group by a canonical key → map of key → list
Go
// Two sum (LC 1): value → index
func twoSum(nums []int, target int) []int {
    seen := map[int]int{}
    for i, x := range nums {
        if j, ok := seen[target-x]; ok {
            return []int{j, i}
        }
        seen[x] = i
    }
    return nil
}

// Group anagrams (LC 49): [26]int counts are comparable, so usable as a key
func groupAnagrams(strs []string) [][]string {
    groups := map[[26]int][]string{}
    for _, s := range strs {
        var key [26]int
        for _, c := range s {
            key[c-'a']++
        }
        groups[key] = append(groups[key], s)
    }
    out := make([][]string, 0, len(groups))
    for _, g := range groups {
        out = append(out, g)
    }
    return out
}

// Longest consecutive sequence (LC 128): only start from sequence heads
func longestConsecutive(nums []int) int {
    set := make(map[int]struct{}, len(nums))
    for _, x := range nums {
        set[x] = struct{}{}
    }
    best := 0
    for x := range set {
        if _, ok := set[x-1]; ok {
            continue
        }
        length := 1
        for {
            if _, ok := set[x+length]; !ok {
                break
            }
            length++
        }
        best = max(best, length)
    }
    return best
}

Common variants

  • Two sum → Store value → index; check target - x before inserting x
  • Frequency count → Counter map; compare counts for anagrams
  • Group by key → Sorted string or 26-count tuple as the key
  • Set for O(1) membership → Longest consecutive sequence: only start from numbers with no predecessor

Classic problems

Binary Tree / BST

O(n) / O(h) / O(h)

Recursive structure; traversals are DFS/BFS, and a BST's in-order traversal is sorted.

How to recognise it

  • Answer depends on children's answers → post-order recursion
  • BST + order/rank → in-order traversal is sorted
  • Level by level → BFS with a queue
Go
type TreeNode struct {
    Val         int
    Left, Right *TreeNode
}

// Post-order: combine the children's answers (LC 104)
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}

// In-order: sorted output for a BST
func inorder(root *TreeNode) []int {
    var out []int
    var walk func(*TreeNode)
    walk = func(n *TreeNode) {
        if n == nil {
            return
        }
        walk(n.Left)
        out = append(out, n.Val)
        walk(n.Right)
    }
    walk(root)
    return out
}

// Level order (LC 102): process len(queue) nodes per round
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    var res [][]int
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        level := make([]int, 0, len(queue))
        for n := len(queue); n > 0; n-- {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        res = append(res, level)
    }
    return res
}

// Validate BST (LC 98): pass bounds down, nil means unbounded
func isValidBST(root *TreeNode) bool {
    var check func(n *TreeNode, lo, hi *int) bool
    check = func(n *TreeNode, lo, hi *int) bool {
        if n == nil {
            return true
        }
        if (lo != nil && n.Val <= *lo) || (hi != nil && n.Val >= *hi) {
            return false
        }
        return check(n.Left, lo, &n.Val) && check(n.Right, &n.Val, hi)
    }
    return check(root, nil, nil)
}

// Lowest common ancestor (LC 236)
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    l := lowestCommonAncestor(root.Left, p, q)
    r := lowestCommonAncestor(root.Right, p, q)
    if l != nil && r != nil {
        return root
    }
    if l != nil {
        return l
    }
    return r
}

Common variants

  • Pre / in / post-order → Position of the root visit relative to children
  • Level order → Process len(queue) nodes per round
  • Validate BST → Pass (lo, hi) bounds down, not just parent comparison
  • LCA → Return the node when both sides report a hit

Classic problems

Heap (Priority Queue)

O(log n) push/pop / O(n)

Always gives the min or max in O(log n); the answer to top-k, k-way merge and streaming median.

How to recognise it

  • "k-th largest / top k" → size-k heap
  • Merge k sorted sources → heap of heads
  • Running median or repeated min/max extraction → one or two heaps
Go
// container/heap: implement the interface, then use heap.Push / heap.Pop.
// For a max-heap flip Less, or push negated values.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
    old := *h
    x := old[len(old)-1]
    *h = old[:len(old)-1]
    return x
}

// k-th largest (LC 215): min-heap of size k
func findKthLargest(nums []int, k int) int {
    h := &IntHeap{}
    for _, x := range nums {
        heap.Push(h, x)
        if h.Len() > k {
            heap.Pop(h)
        }
    }
    return (*h)[0]
}

// Median of a stream (LC 295): two heaps
type MedianFinder struct {
    lo, hi *IntHeap // lo stores negated values (max-heap), hi is a min-heap
}

func NewMedianFinder() *MedianFinder {
    return &MedianFinder{lo: &IntHeap{}, hi: &IntHeap{}}
}

func (m *MedianFinder) Add(x int) {
    heap.Push(m.lo, -x)
    heap.Push(m.hi, -heap.Pop(m.lo).(int))
    if m.hi.Len() > m.lo.Len() {
        heap.Push(m.lo, -heap.Pop(m.hi).(int))
    }
}

func (m *MedianFinder) Median() float64 {
    if m.lo.Len() > m.hi.Len() {
        return float64(-(*m.lo)[0])
    }
    return float64(-(*m.lo)[0]+(*m.hi)[0]) / 2
}

Common variants

  • Top k largest → Min-heap of size k; pop when it exceeds k
  • Merge k lists → Heap of (value, source); push the successor after each pop
  • Two heaps for median → Max-heap for the lower half, min-heap for the upper half
  • Lazy deletion → Mark removed items and skip them when they surface

Classic problems

Trie

O(L) / O(N·L)

Prefix tree for shared-prefix lookups: autocomplete, word search, prefix counting.

How to recognise it

  • Many strings, queries about prefixes → trie
  • Word search over a grid with a dictionary → DFS pruned by trie
  • Longest common prefix or autocomplete → walk shared path
Go
// Lowercase letters only: a [26] array is the fastest child lookup
type Trie struct {
    next [26]*Trie
    end  bool
}

func (t *Trie) Insert(word string) {
    cur := t
    for i := 0; i < len(word); i++ {
        c := word[i] - 'a'
        if cur.next[c] == nil {
            cur.next[c] = &Trie{}
        }
        cur = cur.next[c]
    }
    cur.end = true
}

func (t *Trie) walk(s string) *Trie {
    cur := t
    for i := 0; i < len(s) && cur != nil; i++ {
        cur = cur.next[s[i]-'a']
    }
    return cur
}

func (t *Trie) Search(word string) bool {
    n := t.walk(word)
    return n != nil && n.end
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.walk(prefix) != nil
}

Common variants

  • Insert / search / startsWith → One node per character, end-of-word flag
  • Wildcard search → On '.', recurse into every child
  • Count with prefix → Store pass-through counts on each node
  • Array vs map children → [26]*Node is fastest for lowercase; map for general alphabets

Classic problems

Union Find (DSU)

O(α(n)) / O(n)

Tracks disjoint sets with near-O(1) find and union via path compression and union by size.

How to recognise it

  • Dynamic connectivity: "are x and y in the same group?"
  • Merge groups over time, count components
  • Undirected graph, edges arrive one by one
Go
type DSU struct {
    parent, size []int
    count        int // number of components
}

func NewDSU(n int) *DSU {
    d := &DSU{parent: make([]int, n), size: make([]int, n), count: n}
    for i := range d.parent {
        d.parent[i], d.size[i] = i, 1
    }
    return d
}

// Path halving: near-flat trees without recursion
func (d *DSU) Find(x int) int {
    for d.parent[x] != x {
        d.parent[x] = d.parent[d.parent[x]]
        x = d.parent[x]
    }
    return x
}

// Union by size; reports whether a merge happened
func (d *DSU) Union(a, b int) bool {
    ra, rb := d.Find(a), d.Find(b)
    if ra == rb {
        return false
    }
    if d.size[ra] < d.size[rb] {
        ra, rb = rb, ra
    }
    d.parent[rb] = ra
    d.size[ra] += d.size[rb]
    d.count--
    return true
}

Common variants

  • Path compression → Point every visited node straight at the root
  • Union by size / rank → Attach the smaller tree under the larger
  • Component count → Start at n, decrement on every successful union
  • Weighted DSU → Store the offset to the root for ratio or parity constraints

Classic problems

Algorithm paradigms

Two Pointers

O(n) / O(1)

Two indices sweep a sorted or symmetric sequence, replacing an O(n²) pair search with O(n).

How to recognise it

  • Sorted array + pair/triple with a target sum
  • Palindrome or symmetric checks
  • In-place dedupe / partition (slow-fast pointers)
Go
// Opposite ends on a sorted array (LC 167)
func twoSumSorted(a []int, target int) []int {
    l, r := 0, len(a)-1
    for l < r {
        switch sum := a[l] + a[r]; {
        case sum == target:
            return []int{l, r}
        case sum < target:
            l++
        default:
            r--
        }
    }
    return nil
}

// Move the shorter side: only that can improve the area (LC 11)
func maxArea(h []int) int {
    l, r, best := 0, len(h)-1, 0
    for l < r {
        best = max(best, min(h[l], h[r])*(r-l))
        if h[l] < h[r] {
            l++
        } else {
            r--
        }
    }
    return best
}

// 3Sum (LC 15): sort, fix one, two-pointer the rest, skip duplicates
func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var res [][]int
    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        l, r := i+1, len(nums)-1
        for l < r {
            switch sum := nums[i] + nums[l] + nums[r]; {
            case sum < 0:
                l++
            case sum > 0:
                r--
            default:
                res = append(res, []int{nums[i], nums[l], nums[r]})
                for l < r && nums[l] == nums[l+1] {
                    l++
                }
                for l < r && nums[r] == nums[r-1] {
                    r--
                }
                l++
                r--
            }
        }
    }
    return res
}

// Same direction: slow writes, fast reads (LC 283)
func moveZeroes(a []int) {
    slow := 0
    for fast := range a {
        if a[fast] != 0 {
            a[slow], a[fast] = a[fast], a[slow]
            slow++
        }
    }
}

Common variants

  • Opposite ends → Move the pointer that can improve the answer (container, two-sum II)
  • Same direction (slow/fast) → Slow writes, fast reads: remove duplicates, move zeroes
  • k-sum → Sort, fix one element, two-pointer the rest, skip duplicates
  • Merge two sorted arrays → Advance the pointer with the smaller value

Classic problems

Sliding Window

O(n) / O(1)

Contiguous subarray or substring with a max/min/exact constraint: grow right, shrink left.

How to recognise it

  • "Contiguous subarray / substring" + "longest / shortest / exactly" + a numeric or distinctness constraint
  • Validity is monotonic: shrinking the window can only help
  • Elements are non-negative (for sum windows)
Go
// Longest substring without repeating characters (LC 3)
func lengthOfLongestSubstring(s string) int {
    charSet := make(map[byte]int)
    left, maxLen := 0, 0
    for right := 0; right < len(s); right++ {
        for charSet[s[right]] > 0 { // window invalid → shrink from the left
            charSet[s[left]]--
            left++
        }
        charSet[s[right]]++
        maxLen = max(maxLen, right-left+1)
    }
    return maxLen
}

// Shortest subarray with sum >= target, non-negative numbers (LC 209)
func minSubArrayLen(target int, nums []int) int {
    left, sum, best := 0, 0, len(nums)+1
    for right, x := range nums {
        sum += x
        for sum >= target { // window valid → try to shrink
            best = min(best, right-left+1)
            sum -= nums[left]
            left++
        }
    }
    if best > len(nums) {
        return 0
    }
    return best
}

// At most k distinct characters
func longestAtMostKDistinct(s string, k int) int {
    count := map[byte]int{}
    left, best := 0, 0
    for right := 0; right < len(s); right++ {
        count[s[right]]++
        for len(count) > k {
            count[s[left]]--
            if count[s[left]] == 0 {
                delete(count, s[left])
            }
            left++
        }
        best = max(best, right-left+1)
    }
    return best
}

// Fixed window of size k: add the new element, drop the old one
func maxSumK(nums []int, k int) int {
    sum, best := 0, math.MinInt
    for i, x := range nums {
        sum += x
        if i >= k {
            sum -= nums[i-k]
        }
        if i >= k-1 {
            best = max(best, sum)
        }
    }
    return best
}

Common variants

  • Fixed window size → for loop: add a[i], remove a[i-k]
  • At most k distinct characters → Relax the condition: shrink while distinct > k
  • Product less than k → Multiply instead of add; each right adds (right-left+1) subarrays
  • Exactly k → atMost(k) - atMost(k-1)
  • Window max → Monotonic deque instead of a plain counter

Classic problems

DFS / BFS

O(V + E) / O(V)

Graph and grid traversal; DFS for exhaustive paths and components, BFS for shortest steps.

How to recognise it

  • Grid / graph connectivity, islands, flood fill → DFS or BFS
  • Minimum number of steps in an unweighted graph → BFS
  • Enumerate all paths or components → DFS
Go
// Grid DFS: number of islands (LC 200). Marks visited in place.
func numIslands(grid [][]byte) int {
    count := 0
    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] != '1' {
            return
        }
        grid[r][c] = '0'
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    }
    for r := range grid {
        for c := range grid[r] {
            if grid[r][c] == '1' {
                count++
                dfs(r, c)
            }
        }
    }
    return count
}

// BFS shortest number of edges in an unweighted graph
func shortestSteps(adj [][]int, src, dst int) int {
    dist := make([]int, len(adj))
    for i := range dist {
        dist[i] = -1
    }
    dist[src] = 0
    queue := []int{src}
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        if u == dst {
            return dist[u]
        }
        for _, v := range adj[u] {
            if dist[v] == -1 { // mark on enqueue, not on dequeue
                dist[v] = dist[u] + 1
                queue = append(queue, v)
            }
        }
    }
    return -1
}

// Multi-source BFS: rotting oranges (LC 994)
func orangesRotting(grid [][]int) int {
    type cell struct{ r, c int }
    var queue []cell
    fresh := 0
    for r := range grid {
        for c := range grid[r] {
            switch grid[r][c] {
            case 2:
                queue = append(queue, cell{r, c})
            case 1:
                fresh++
            }
        }
    }
    dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    minutes := 0
    for len(queue) > 0 && fresh > 0 {
        minutes++
        for n := len(queue); n > 0; n-- {
            cur := queue[0]
            queue = queue[1:]
            for _, d := range dirs {
                nr, nc := cur.r+d[0], cur.c+d[1]
                if nr >= 0 && nc >= 0 && nr < len(grid) && nc < len(grid[0]) && grid[nr][nc] == 1 {
                    grid[nr][nc] = 2
                    fresh--
                    queue = append(queue, cell{nr, nc})
                }
            }
        }
    }
    if fresh > 0 {
        return -1
    }
    return minutes
}

Common variants

  • Grid DFS → Mark visited in place, four-direction array
  • BFS shortest steps → Process the queue level by level, count levels
  • Multi-source BFS → Seed the queue with every source (rotting oranges)
  • Graph with visited set → Mark when enqueued, not when dequeued, to avoid duplicates

Classic problems

Dynamic Programming

O(states × transitions) / O(states)

Overlapping subproblems with optimal substructure: define state, transition and base case.

How to recognise it

  • "Count the ways", "min/max cost", "is it possible" over choices
  • Brute force recursion repeats the same arguments
  • Decisions at step i only depend on a small summary of earlier steps
Go
// 1-D with rolling variables: house robber (LC 198)
func rob(nums []int) int {
    prev, cur := 0, 0
    for _, x := range nums {
        prev, cur = cur, max(cur, prev+x)
    }
    return cur
}

// Unbounded knapsack: fewest coins (LC 322)
func coinChange(coins []int, amount int) int {
    const inf = 1 << 30
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        dp[i] = inf
        for _, c := range coins {
            if c <= i {
                dp[i] = min(dp[i], dp[i-c]+1)
            }
        }
    }
    if dp[amount] >= inf {
        return -1
    }
    return dp[amount]
}

// 0/1 knapsack: subset sum (LC 416). Capacity goes downwards → each item once.
func canPartition(nums []int) bool {
    total := 0
    for _, x := range nums {
        total += x
    }
    if total%2 != 0 {
        return false
    }
    target := total / 2
    dp := make([]bool, target+1)
    dp[0] = true
    for _, x := range nums {
        for j := target; j >= x; j-- {
            dp[j] = dp[j] || dp[j-x]
        }
    }
    return dp[target]
}

// Two sequences: LCS (LC 1143)
func longestCommonSubsequence(a, b string) int {
    dp := make([][]int, len(a)+1)
    for i := range dp {
        dp[i] = make([]int, len(b)+1)
    }
    for i := 1; i <= len(a); i++ {
        for j := 1; j <= len(b); j++ {
            if a[i-1] == b[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[len(a)][len(b)]
}

// LIS in O(n log n) (LC 300): tails[i] = smallest tail of an increasing run of length i+1
func lengthOfLIS(nums []int) int {
    var tails []int
    for _, x := range nums {
        i := sort.SearchInts(tails, x)
        if i == len(tails) {
            tails = append(tails, x)
        } else {
            tails[i] = x
        }
    }
    return len(tails)
}

Common variants

  • 1-D linear (climb, house robber) → dp[i] from dp[i-1], dp[i-2]; roll to O(1) space
  • 0/1 knapsack → Iterate capacity downwards so each item is used once
  • Unbounded knapsack / coin change → Iterate capacity upwards so items repeat
  • Two-sequence (LCS, edit distance) → dp[i][j] over prefixes of both strings
  • LIS → O(n²) dp, or O(n log n) with a tails array + binary search

Classic problems

Backtracking

O(2ⁿ) / O(n!) / O(n)

Build a candidate step by step, undo on dead ends: permutations, subsets, combinations, N-Queens.

How to recognise it

  • "Generate all" permutations / subsets / combinations / valid placements
  • Choose → explore → un-choose structure
  • Constraints let you prune partial candidates early
Go
// Subsets (LC 78): record the path at every node
func subsets(nums []int) [][]int {
    res := [][]int{}
    path := []int{}
    var dfs func(start int)
    dfs = func(start int) {
        res = append(res, append([]int(nil), path...)) // copy the path!
        for i := start; i < len(nums); i++ {
            path = append(path, nums[i])
            dfs(i + 1)
            path = path[:len(path)-1] // undo
        }
    }
    dfs(0)
    return res
}

// Permutations (LC 46): used[] marks what is already in the path
func permute(nums []int) [][]int {
    var res [][]int
    path := []int{}
    used := make([]bool, len(nums))
    var dfs func()
    dfs = func() {
        if len(path) == len(nums) {
            res = append(res, append([]int(nil), path...))
            return
        }
        for i, x := range nums {
            if used[i] {
                continue
            }
            used[i] = true
            path = append(path, x)
            dfs()
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    dfs()
    return res
}

// Combination sum (LC 39): reuse allowed → recurse with i, not i+1
func combinationSum(candidates []int, target int) [][]int {
    var res [][]int
    path := []int{}
    var dfs func(start, remain int)
    dfs = func(start, remain int) {
        if remain == 0 {
            res = append(res, append([]int(nil), path...))
            return
        }
        for i := start; i < len(candidates); i++ {
            if candidates[i] > remain {
                continue
            }
            path = append(path, candidates[i])
            dfs(i, remain-candidates[i])
            path = path[:len(path)-1]
        }
    }
    dfs(0, target)
    return res
}

// N-Queens (LC 51): count solutions with O(1) conflict checks
func totalNQueens(n int) int {
    cols := make([]bool, n)
    diag1 := make([]bool, 2*n) // row + col
    diag2 := make([]bool, 2*n) // row - col + n
    count := 0
    var dfs func(row int)
    dfs = func(row int) {
        if row == n {
            count++
            return
        }
        for c := 0; c < n; c++ {
            if cols[c] || diag1[row+c] || diag2[row-c+n] {
                continue
            }
            cols[c], diag1[row+c], diag2[row-c+n] = true, true, true
            dfs(row + 1)
            cols[c], diag1[row+c], diag2[row-c+n] = false, false, false
        }
    }
    dfs(0)
    return count
}

Common variants

  • Subsets → Record the path at every node; recurse from start index
  • Permutations → used[] array, or swap in place
  • Combination sum → Pass start index; reuse allowed → recurse with i, otherwise i + 1
  • Dedupe equal elements → Sort, then skip a[i] == a[i-1] when i > start
  • N-Queens → Column and two diagonal sets for O(1) conflict checks

Classic problems

Greedy

O(n log n) / O(1)

Take the locally best choice each step; sort first, then prove the exchange argument.

How to recognise it

  • Sort by one key, then a single pass makes irrevocable choices
  • Interval scheduling, jump reach, assignment by size
  • A local-best choice never hurts the remaining problem (exchange argument)
Go
// Jump game (LC 55): track the farthest reachable index
func canJump(nums []int) bool {
    far := 0
    for i, x := range nums {
        if i > far {
            return false
        }
        far = max(far, i+x)
    }
    return true
}

// Jump game II (LC 45): fewest jumps, extend the window when the current one ends
func jump(nums []int) int {
    steps, curEnd, far := 0, 0, 0
    for i := 0; i < len(nums)-1; i++ {
        far = max(far, i+nums[i])
        if i == curEnd {
            steps++
            curEnd = far
        }
    }
    return steps
}

// Stock with unlimited trades (LC 122): collect every upward step
func maxProfit(prices []int) int {
    profit := 0
    for i := 1; i < len(prices); i++ {
        profit += max(0, prices[i]-prices[i-1])
    }
    return profit
}

// Partition labels (LC 763): cut when we reach the last occurrence of everything seen
func partitionLabels(s string) []int {
    var last [26]int
    for i := range s {
        last[s[i]-'a'] = i
    }
    var res []int
    start, end := 0, 0
    for i := range s {
        end = max(end, last[s[i]-'a'])
        if i == end {
            res = append(res, end-start+1)
            start = i + 1
        }
    }
    return res
}

Common variants

  • Reachability → Track the farthest reachable index (jump game)
  • Interval scheduling → Sort by end; keep the interval that ends earliest
  • Stock with unlimited trades → Sum every positive day-to-day difference
  • Partition by last occurrence → Extend the current end to the farthest last index seen

Classic problems

Divide & Conquer

O(n log n) / O(log n)

Split into independent subproblems, solve recursively, merge: merge sort, quickselect, closest pair.

How to recognise it

  • Problem splits into independent halves that combine cheaply
  • Recurrence looks like T(n) = 2T(n/2) + O(n)
  • Need the k-th element without fully sorting
Go
// Merge sort (LC 912): T(n) = 2T(n/2) + O(n)
func mergeSort(a []int) []int {
    if len(a) <= 1 {
        return a
    }
    mid := len(a) / 2
    l, r := mergeSort(a[:mid]), mergeSort(a[mid:])
    out := make([]int, 0, len(a))
    i, j := 0, 0
    for i < len(l) && j < len(r) {
        if l[i] <= r[j] {
            out = append(out, l[i])
            i++
        } else {
            out = append(out, r[j])
            j++
        }
    }
    out = append(out, l[i:]...)
    return append(out, r[j:]...)
}

// Quickselect (LC 215): k-th largest, 1-based, average O(n)
func findKthLargest(nums []int, k int) int {
    target := len(nums) - k // index in ascending order
    lo, hi := 0, len(nums)-1
    for lo < hi {
        p := partition(nums, lo, hi)
        switch {
        case p == target:
            return nums[p]
        case p < target:
            lo = p + 1
        default:
            hi = p - 1
        }
    }
    return nums[lo]
}

func partition(a []int, lo, hi int) int {
    r := lo + rand.Intn(hi-lo+1) // random pivot avoids the O(n²) case
    a[r], a[hi] = a[hi], a[r]
    pivot, i := a[hi], lo
    for j := lo; j < hi; j++ {
        if a[j] < pivot {
            a[i], a[j] = a[j], a[i]
            i++
        }
    }
    a[i], a[hi] = a[hi], a[i]
    return i
}

// Maximum subarray by divide and conquer (LC 53)
func maxSubArray(a []int) int {
    var solve func(lo, hi int) int
    solve = func(lo, hi int) int {
        if lo == hi {
            return a[lo]
        }
        mid := (lo + hi) / 2
        leftBest, rightBest, sum := math.MinInt, math.MinInt, 0
        for i := mid; i >= lo; i-- {
            sum += a[i]
            leftBest = max(leftBest, sum)
        }
        sum = 0
        for i := mid + 1; i <= hi; i++ {
            sum += a[i]
            rightBest = max(rightBest, sum)
        }
        return max(solve(lo, mid), solve(mid+1, hi), leftBest+rightBest)
    }
    return solve(0, len(a)-1)
}

Common variants

  • Merge sort → Sort halves, merge; count inversions during the merge
  • Quickselect → Partition around a pivot, recurse into one side: O(n) average
  • Merge k lists → Pair lists up and merge, O(N log k)
  • Maximum subarray → Best of left, right, or crossing the middle

Classic problems

High-frequency patterns

Intervals

O(n log n) / O(n)

Sort by start (or end), then sweep: merge, insert, count overlaps, pick the max non-overlapping set.

How to recognise it

  • Input is a list of [start, end] pairs
  • "Merge", "insert", "overlap", "minimum rooms/arrows/removals"
  • Sort first; the answer follows from one sweep
Go
// Merge overlapping intervals (LC 56): sort by start, extend the last end
func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return nil
    }
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
    res := [][]int{intervals[0]}
    for _, iv := range intervals[1:] {
        last := res[len(res)-1]
        if iv[0] <= last[1] {
            last[1] = max(last[1], iv[1])
        } else {
            res = append(res, iv)
        }
    }
    return res
}

// Minimum removals so the rest don't overlap (LC 435): sort by END
func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })
    removed, end := 0, math.MinInt
    for _, iv := range intervals {
        if iv[0] >= end {
            end = iv[1]
        } else {
            removed++
        }
    }
    return removed
}

// Minimum meeting rooms: sorted starts vs sorted ends
func minMeetingRooms(intervals [][]int) int {
    n := len(intervals)
    starts, ends := make([]int, n), make([]int, n)
    for i, iv := range intervals {
        starts[i], ends[i] = iv[0], iv[1]
    }
    sort.Ints(starts)
    sort.Ints(ends)
    rooms, e := 0, 0
    for _, s := range starts {
        if s < ends[e] {
            rooms++ // nobody has left yet → new room
        } else {
            e++ // reuse a room that just freed up
        }
    }
    return rooms
}

// Insert a new interval into a sorted, non-overlapping list (LC 57)
func insert(intervals [][]int, newI []int) [][]int {
    var res [][]int
    i := 0
    for ; i < len(intervals) && intervals[i][1] < newI[0]; i++ {
        res = append(res, intervals[i])
    }
    for ; i < len(intervals) && intervals[i][0] <= newI[1]; i++ {
        newI = []int{min(newI[0], intervals[i][0]), max(newI[1], intervals[i][1])}
    }
    res = append(res, newI)
    return append(res, intervals[i:]...)
}

Common variants

  • Merge overlapping → Sort by start; extend the last merged end when start <= end
  • Max non-overlapping / min removals → Sort by end; keep an interval only if start >= last end
  • Meeting rooms (max overlap) → Sweep line over +1 starts and -1 ends, or a min-heap of end times
  • Insert interval → Copy left of the new one, merge the overlapping, copy the right

Classic problems

Keep a stack or deque ordered to answer next-greater, histogram and sliding-window-max queries in O(n).

How to recognise it

  • "Next greater / smaller element" for every position
  • Largest rectangle, trapping water, stock span
  • Window maximum/minimum over a sliding range
Go
// Next greater element: distance to the next warmer day (LC 739)
func dailyTemperatures(t []int) []int {
    ans := make([]int, len(t))
    stack := []int{} // indices, values decreasing
    for i, x := range t {
        for len(stack) > 0 && t[stack[len(stack)-1]] < x {
            j := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            ans[j] = i - j
        }
        stack = append(stack, i)
    }
    return ans
}

// Largest rectangle in a histogram (LC 84): increasing stack with a -1 sentinel
func largestRectangleArea(h []int) int {
    stack := []int{-1}
    best := 0
    for i := 0; i <= len(h); i++ {
        cur := 0 // a virtual 0-height bar flushes the stack at the end
        if i < len(h) {
            cur = h[i]
        }
        for len(stack) > 1 && h[stack[len(stack)-1]] >= cur {
            height := h[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            best = max(best, height*(i-stack[len(stack)-1]-1))
        }
        stack = append(stack, i)
    }
    return best
}

// Sliding window maximum (LC 239): deque of indices, values decreasing
func maxSlidingWindow(nums []int, k int) []int {
    var res, dq []int
    for i, x := range nums {
        for len(dq) > 0 && nums[dq[len(dq)-1]] <= x {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, i)
        if dq[0] <= i-k { // front left the window
            dq = dq[1:]
        }
        if i >= k-1 {
            res = append(res, nums[dq[0]])
        }
    }
    return res
}

Common variants

  • Next greater element → Decreasing stack of indices; pop while the new value is greater
  • Circular array → Iterate 2n and index with i % n
  • Largest rectangle in histogram → Increasing stack; a pop fixes the rectangle's height and width
  • Sliding window maximum → Decreasing deque of indices; drop indices that left the window

Classic problems

Topological Sort

O(V + E) / O(V + E)

Order a DAG by dependencies with Kahn's algorithm; leftover nodes mean a cycle.

How to recognise it

  • Tasks with prerequisites; "can all be finished?"
  • Output a valid order of a directed acyclic graph
  • Detect a cycle in a directed graph
Go
// Kahn's algorithm. Edge {a, b} means a must come before b.
// Returns nil if the graph has a cycle.
func topoSort(n int, edges [][]int) []int {
    adj := make([][]int, n)
    indeg := make([]int, n)
    for _, e := range edges {
        adj[e[0]] = append(adj[e[0]], e[1])
        indeg[e[1]]++
    }
    queue := []int{}
    for i, d := range indeg {
        if d == 0 {
            queue = append(queue, i)
        }
    }
    order := make([]int, 0, n)
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        order = append(order, u)
        for _, v := range adj[u] {
            if indeg[v]--; indeg[v] == 0 {
                queue = append(queue, v)
            }
        }
    }
    if len(order) != n {
        return nil // leftover nodes sit on a cycle
    }
    return order
}

// Course schedule (LC 207): prerequisites[i] = {course, prerequisite}
func canFinish(numCourses int, prerequisites [][]int) bool {
    edges := make([][]int, len(prerequisites))
    for i, p := range prerequisites {
        edges[i] = []int{p[1], p[0]}
    }
    return topoSort(numCourses, edges) != nil
}

Common variants

  • Kahn's algorithm (BFS) → Queue nodes with in-degree 0; the order is complete only if all nodes are visited
  • DFS with colors → white / gray / black; an edge into gray is a cycle; reverse post-order
  • Lexicographically smallest order → Replace the queue with a min-heap
  • Safe states → Run Kahn on the reversed graph

Classic problems

Dijkstra with a heap for non-negative weights; Bellman-Ford for negative edges or at most k hops.

How to recognise it

  • Weighted graph, minimum cost between nodes
  • All weights ≥ 0 → Dijkstra; negative weights or "at most k edges" → Bellman-Ford
  • Unweighted graph → plain BFS is enough
Go
type item struct{ node, dist int }
type minHeap []item

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() any {
    old := *h
    x := old[len(old)-1]
    *h = old[:len(old)-1]
    return x
}

// Dijkstra (non-negative weights, LC 743). graph[u] = list of {v, w}.
// dist is math.MaxInt for unreachable nodes.
func dijkstra(graph [][][2]int, src int) []int {
    dist := make([]int, len(graph))
    for i := range dist {
        dist[i] = math.MaxInt
    }
    dist[src] = 0
    h := &minHeap{{src, 0}}
    for h.Len() > 0 {
        cur := heap.Pop(h).(item)
        if cur.dist > dist[cur.node] {
            continue // stale entry
        }
        for _, e := range graph[cur.node] {
            v, w := e[0], e[1]
            if nd := cur.dist + w; nd < dist[v] {
                dist[v] = nd
                heap.Push(h, item{v, nd})
            }
        }
    }
    return dist
}

// Bellman-Ford limited to k edges (LC 787): relax against last round's copy
func findCheapestPrice(n int, flights [][]int, src, dst, k int) int {
    const inf = math.MaxInt / 2
    dist := make([]int, n)
    for i := range dist {
        dist[i] = inf
    }
    dist[src] = 0
    for round := 0; round <= k; round++ {
        next := append([]int(nil), dist...)
        for _, f := range flights {
            u, v, w := f[0], f[1], f[2]
            if dist[u] < inf && dist[u]+w < next[v] {
                next[v] = dist[u] + w
            }
        }
        dist = next
    }
    if dist[dst] >= inf {
        return -1
    }
    return dist[dst]
}

Common variants

  • Dijkstra with a heap → Pop (dist, node), skip stale entries, relax neighbours
  • Bellman-Ford with k rounds → Relax all edges k times against a copy of the previous round
  • Grid Dijkstra → Cost is the max (or sum) along the path; neighbours are 4 directions
  • 0-1 BFS → Deque: push 0-weight edges front, 1-weight edges back

Classic problems

Union Find Applications

O(n α(n)) / O(n)

Cycle detection in undirected graphs, grouping accounts, equation constraints and minimum spanning trees.

How to recognise it

  • Add edges one by one and ask which edge closes a cycle
  • Merge items that share an attribute (email, equality)
  • Spanning tree / connect all nodes at minimum cost
Go
// Reuses the DSU from the Union Find entry (parent slice + path halving)
type DSU struct{ parent []int }

func NewDSU(n int) *DSU {
    d := &DSU{parent: make([]int, n)}
    for i := range d.parent {
        d.parent[i] = i
    }
    return d
}

func (d *DSU) Find(x int) int {
    for d.parent[x] != x {
        d.parent[x] = d.parent[d.parent[x]]
        x = d.parent[x]
    }
    return x
}

func (d *DSU) Union(a, b int) bool {
    ra, rb := d.Find(a), d.Find(b)
    if ra == rb {
        return false
    }
    d.parent[rb] = ra
    return true
}

// Redundant connection (LC 684): the edge whose endpoints are already connected
func findRedundantConnection(edges [][]int) []int {
    d := NewDSU(len(edges) + 1)
    for _, e := range edges {
        if !d.Union(e[0], e[1]) {
            return e
        }
    }
    return nil
}

// Equality equations (LC 990): union all '=' first, then check every '!='
func equationsPossible(equations []string) bool {
    d := NewDSU(26)
    for _, eq := range equations {
        if eq[1] == '=' {
            d.Union(int(eq[0]-'a'), int(eq[3]-'a'))
        }
    }
    for _, eq := range equations {
        if eq[1] == '!' && d.Find(int(eq[0]-'a')) == d.Find(int(eq[3]-'a')) {
            return false
        }
    }
    return true
}

// Kruskal MST: total weight, or -1 when the graph is disconnected. Edge = {u, v, w}.
func kruskal(n int, edges [][3]int) int {
    sort.Slice(edges, func(i, j int) bool { return edges[i][2] < edges[j][2] })
    d := NewDSU(n)
    total, used := 0, 0
    for _, e := range edges {
        if d.Union(e[0], e[1]) {
            total += e[2]
            used++
        }
    }
    if used != n-1 {
        return -1
    }
    return total
}

Common variants

  • Cycle detection → If find(a) == find(b) before union, that edge closes a cycle
  • Grouping by shared key → Union each account with the first owner of its email
  • Equality / inequality constraints → Union all '=' first, then verify every '!='
  • Kruskal MST → Sort edges by weight; take an edge when it joins two components

Classic problems

String Processing

O(n) – O(n²) / O(1) – O(n)

Palindromes, anagrams, parsing and pattern matching: expand from centers, count characters, or build a prefix table.

How to recognise it

  • Palindrome substring → expand around each center
  • Anagram or permutation check → character count array
  • Find a pattern inside text in linear time → KMP prefix table
Go
// Longest palindromic substring (LC 5): expand around every center
func longestPalindrome(s string) string {
    start, best := 0, 0
    expand := func(l, r int) {
        for l >= 0 && r < len(s) && s[l] == s[r] {
            l--
            r++
        }
        if r-l-1 > best {
            start, best = l+1, r-l-1
        }
    }
    for i := range s {
        expand(i, i)   // odd length
        expand(i, i+1) // even length
    }
    return s[start : start+best]
}

// Anagram check (LC 242): count lowercase letters
func isAnagram(s, t string) bool {
    if len(s) != len(t) {
        return false
    }
    var cnt [26]int
    for i := range s {
        cnt[s[i]-'a']++
        cnt[t[i]-'a']--
    }
    return cnt == [26]int{}
}

// KMP (LC 28): index of needle in haystack, or -1
func strStr(haystack, needle string) int {
    if needle == "" {
        return 0
    }
    next := make([]int, len(needle)) // longest proper prefix that is also a suffix
    for i, k := 1, 0; i < len(needle); i++ {
        for k > 0 && needle[i] != needle[k] {
            k = next[k-1]
        }
        if needle[i] == needle[k] {
            k++
        }
        next[i] = k
    }
    for i, k := 0, 0; i < len(haystack); i++ {
        for k > 0 && haystack[i] != needle[k] {
            k = next[k-1]
        }
        if haystack[i] == needle[k] {
            k++
        }
        if k == len(needle) {
            return i - k + 1
        }
    }
    return -1
}

Common variants

  • Expand around center → Try odd and even centers; O(n²) time, O(1) space
  • Character count → Compare 26-slot arrays instead of sorting strings
  • KMP / Z-function → Reuse the longest proper prefix-suffix to avoid re-scanning

Classic problems

Bit Manipulation

O(1) – O(n) / O(1)

XOR cancels pairs, n & (n-1) drops the lowest set bit, and a bitmask encodes a subset in one integer.

How to recognise it

  • Every element appears twice except one → XOR everything
  • Count set bits or test a power of two → n & (n-1)
  • Subsets of up to ~20 items → bitmask enumeration
Go
// Single number (LC 136): pairs cancel under XOR
func singleNumber(nums []int) int {
    res := 0
    for _, x := range nums {
        res ^= x
    }
    return res
}

// Number of 1 bits (LC 191): n & (n-1) drops the lowest set bit
func hammingWeight(n uint32) int {
    cnt := 0
    for ; n != 0; n &= n - 1 {
        cnt++
    }
    return cnt
}

// Power of two (LC 231)
func isPowerOfTwo(n int) bool {
    return n > 0 && n&(n-1) == 0
}

// Subsets via bitmask (LC 78): bit i of mask means nums[i] is chosen
func subsets(nums []int) [][]int {
    n := len(nums)
    res := make([][]int, 0, 1<<n)
    for mask := 0; mask < 1<<n; mask++ {
        cur := []int{}
        for i := 0; i < n; i++ {
            if mask>>i&1 == 1 {
                cur = append(cur, nums[i])
            }
        }
        res = append(res, cur)
    }
    return res
}

Common variants

  • XOR cancel → a ^ a = 0 and a ^ 0 = a, so pairs vanish
  • Brian Kernighan → n &= n - 1 removes the lowest set bit; loop count = popcount
  • Subset bitmask → for mask in 0..2^n: bit i set means item i is chosen

Classic problems

Math & Number Theory

O(log n) – O(n log log n) / O(1) – O(n)

GCD, fast exponentiation, sieve of primes and modular arithmetic keep big-number problems inside int range.

How to recognise it

  • Gcd, lcm or simplifying a fraction → Euclid's algorithm
  • x^n with huge n or a modulus → fast exponentiation
  • Count or list primes up to n → sieve of Eratosthenes
Go
// GCD / LCM: Euclid's algorithm
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func lcm(a, b int) int {
    return a / gcd(a, b) * b // divide first to avoid overflow
}

// Fast exponentiation (LC 50): halve the exponent each step
func myPow(x float64, n int) float64 {
    if n < 0 {
        x, n = 1/x, -n
    }
    res := 1.0
    for ; n > 0; n >>= 1 {
        if n&1 == 1 {
            res *= x
        }
        x *= x
    }
    return res
}

// Modular exponentiation: x^n mod m
func powMod(x, n, m int) int {
    res := 1
    x %= m
    for ; n > 0; n >>= 1 {
        if n&1 == 1 {
            res = res * x % m
        }
        x = x * x % m
    }
    return res
}

// Sieve of Eratosthenes (LC 204): count primes below n
func countPrimes(n int) int {
    if n < 3 {
        return 0
    }
    composite := make([]bool, n)
    cnt := 0
    for i := 2; i < n; i++ {
        if composite[i] {
            continue
        }
        cnt++
        for j := i * i; j < n; j += i {
            composite[j] = true
        }
    }
    return cnt
}

Common variants

  • Euclid → gcd(a, b) = gcd(b, a % b); lcm = a / gcd * b
  • Fast power → Halve the exponent each step; take % m after every multiply
  • Sieve → Cross out multiples starting at p*p; O(n log log n)

Classic problems

Combine a hash map with a linked list or heap so every operation is O(1) or O(log n): LRU cache, min stack, iterators.

How to recognise it

  • Evict the least recently used item in O(1) → hash map + doubly linked list
  • Stack that also returns its minimum → keep a parallel min stack
  • Iterate lazily over a nested or tree structure → explicit stack
Go
// LRU cache (LC 146): hash map + doubly linked list with sentinels
type lruNode struct {
    key, val   int
    prev, next *lruNode
}

type LRUCache struct {
    cap        int
    nodes      map[int]*lruNode
    head, tail *lruNode // head.next = most recent, tail.prev = least recent
}

func NewLRUCache(capacity int) *LRUCache {
    head, tail := &lruNode{}, &lruNode{}
    head.next, tail.prev = tail, head
    return &LRUCache{cap: capacity, nodes: map[int]*lruNode{}, head: head, tail: tail}
}

func (c *LRUCache) unlink(n *lruNode) {
    n.prev.next, n.next.prev = n.next, n.prev
}

func (c *LRUCache) pushFront(n *lruNode) {
    n.prev, n.next = c.head, c.head.next
    c.head.next.prev = n
    c.head.next = n
}

func (c *LRUCache) Get(key int) int {
    n, ok := c.nodes[key]
    if !ok {
        return -1
    }
    c.unlink(n)
    c.pushFront(n)
    return n.val
}

func (c *LRUCache) Put(key, val int) {
    if n, ok := c.nodes[key]; ok {
        n.val = val
        c.unlink(n)
        c.pushFront(n)
        return
    }
    if len(c.nodes) == c.cap {
        last := c.tail.prev
        c.unlink(last)
        delete(c.nodes, last.key)
    }
    n := &lruNode{key: key, val: val}
    c.nodes[key] = n
    c.pushFront(n)
}

// Min stack (LC 155): store the running minimum next to every value
type MinStack struct {
    vals, mins []int
}

func (s *MinStack) Push(x int) {
    m := x
    if len(s.mins) > 0 {
        m = min(m, s.mins[len(s.mins)-1])
    }
    s.vals = append(s.vals, x)
    s.mins = append(s.mins, m)
}

func (s *MinStack) Pop() {
    s.vals = s.vals[:len(s.vals)-1]
    s.mins = s.mins[:len(s.mins)-1]
}

func (s *MinStack) Top() int    { return s.vals[len(s.vals)-1] }
func (s *MinStack) GetMin() int { return s.mins[len(s.mins)-1] }

Common variants

  • LRU cache → Map key → node; move a node to the head on every get/put
  • Min stack → Push (value, minSoFar) pairs so pop restores the minimum
  • LFU cache → Frequency buckets, each an ordered list; track the min frequency

Classic problems