Cheatsheet

// ===== Data structures =====
// Array          O(1) index; O(n) insert middle
// Linked list    O(1) insert/delete given node; O(n) lookup
// Stack          LIFO; O(1) push/pop
// Queue          FIFO; O(1) enqueue/dequeue
// Deque          double-ended; O(1) both ends
// Hash map       O(1) avg insert/lookup; O(n) worst
// Hash set       same; unique items
// Tree (BST)     O(log n) ops on balanced; O(n) on degenerate
// Trie           O(m) ops where m = key length; prefix search
// Heap           O(log n) push/pop; min/max
// Graph          O(V+E) BFS/DFS
// Disjoint set   O(α(n)) union/find with path compression
// Bloom filter   O(k) lookup; approximate membership

// ===== Big O classes =====
// O(1)         constant
// O(log n)     binary search, balanced tree
// O(n)         linear scan
// O(n log n)   sort, heap-based n-passes
// O(n^2)       pairwise checks
// O(n^3)       triple loop
// O(2^n)       subset enumeration
// O(n!)        permutations

// ===== Algorithm patterns =====
// Two pointers       sorted arrays, palindromes
// Sliding window     contiguous subarray problems
// Hash + lookup      'have I seen this?'
// Sort + sweep       O(n log n) over O(n^2)
// Binary search      sorted arrays + monotonic functions
// BFS                shortest path in unweighted graphs
// DFS                connectivity, topological sort, cycle detection
// Dynamic programming overlapping subproblems
// Greedy             local-best -> global-best (prove it)
// Backtracking       combinatorial search with pruning
// Divide + conquer   sort, search, matrix algorithms
// Prefix sums        O(1) range queries
// Heap               top-k, k-way merge

// ===== Sort algorithms =====
// Bubble        O(n^2) — teaching
// Selection     O(n^2) — unstable
// Insertion     O(n^2) worst, O(n) best — small lists
// Merge         O(n log n) — stable, extra space
// Quick         O(n log n) avg, O(n^2) worst — in place, unstable
// Heap          O(n log n) — in place, unstable
// Tim sort      O(n log n) — stable, real-world default (Python, Java, JS)
// Radix sort    O(d*n) — non-comparison; bounded keys
// Counting sort O(n + k) — bounded range

// ===== Search algorithms =====
// Linear            O(n)
// Binary            O(log n) — sorted required
// Interpolation     O(log log n) — uniform distribution
// BFS / DFS         O(V+E)
// Dijkstra          O((V+E) log V) — weighted, non-negative
// A*                heuristic-guided

// ===== Patterns =====
// - Pick structure based on hot operation
// - Hash for lookup; sort + sweep beats pairwise
// - Sliding window / two pointers on contiguous problems
// - BFS for shortest unweighted; Dijkstra for weighted
// - DP for overlapping subproblems
// - Heap for top-k, merge-k-sorted, scheduling

// ===== Pitfalls =====
// - Hash maps degrade under adversarial inputs (DoS)
// - O(n log n) sort assumes comparison sort
// - Recursion depth on n=1e5 -> stack overflow; iterate
// - Counting amortised vs worst case

// Two pointers | Sliding window | BFS / DFS | DP | Backtracking | Greedy | Sort + binary search