Pattern Catalogue

# ===== 1) Two pointers =====
# - Removing duplicates from a sorted array
# - Reverse a string in place
# - Three-sum (sort, fix one, two-pointer the rest)
# - Merge two sorted arrays
# Time: O(n). Recognise by 'sorted input, find a pair'.

# ===== 2) Sliding window =====
# - Longest substring without repeating chars
# - Max sum subarray of fixed size k
# - Min window substring covering a pattern
# Time: O(n). Recognise by 'subarray with constraint, maximise/minimise'.

# ===== 3) Fast / slow pointers =====
# - Detect cycle in a linked list (Floyd)
# - Find middle of a linked list
# - Happy number
# Recognise by 'cycle detection' OR 'find midpoint without size'.

# ===== 4) Binary search =====
# - Sorted array search
# - First/last occurrence (lower/upper bound)
# - 'Find smallest k such that predicate(k) is true'
# Time: O(log n). Recognise by 'monotonic predicate'.

# ===== 5) BFS / DFS on a graph =====
# - Shortest path on unweighted graph (BFS)
# - All paths between A and B (DFS with backtrack)
# - Connected components
# - Topological sort (BFS = Kahn, DFS = postorder)
# Recognise by 'reachability, layers, ordering'.

# ===== 6) Dijkstra / A* =====
# - Shortest path with non-negative weights
# Time: O((V+E) log V). Recognise by 'weighted shortest path'.

# ===== 7) Union-Find (Disjoint Set Union) =====
# - Connected components after edges added
# - Kruskal MST
# - Cycle detection in an undirected graph
# Recognise by 'merge groups, ask if same group'.

# ===== 8) Heap / Priority queue =====
# - Kth largest
# - Merge K sorted lists
# - Median of stream (two heaps)
# - Dijkstra inner loop
# Recognise by 'top-K' or 'min/max as you go'.

# ===== 9) Backtracking =====
# - Permutations / combinations / subsets
# - N-Queens, Sudoku
# - Word search on grid
# Recognise by 'enumerate solutions, prune with constraints'.

# ===== 10) Dynamic programming =====
# - Climbing stairs / Fibonacci
# - 0/1 knapsack
# - Edit distance
# - Longest common subsequence
# - Coin change
# Recognise by 'optimal substructure + overlapping subproblems'.

# ===== 11) Greedy =====
# - Interval scheduling (sort by finish time)
# - Coin change for canonical currencies
# - Huffman coding
# Recognise by 'local optimum proven optimal globally' (exchange argument).

# ===== 12) Bit manipulation =====
# - Single number among pairs (XOR)
# - Subset enumeration via bitmask
# - Bitmask DP (TSP with N <= 18)
# Recognise by 'small N, all subsets' or 'XOR-able state'.

# ===== 13) Divide and conquer =====
# - Mergesort / quicksort / quickselect
# - Closest pair of points
# - Karatsuba multiplication
# Recognise by 'split, recurse, combine'.

# ===== 14) Topological sort =====
# - Build order, course schedule, dependency resolution
# Recognise by 'directed acyclic graph + ordering'.

# ===== 15) Trie =====
# - Autocomplete
# - Word search II
# - Replace words
# Recognise by 'prefix queries over many strings'.

# ===== 16) Segment tree / Fenwick tree (BIT) =====
# - Range sum + point update
# - Range min + point update
# Recognise by 'range query + point update on a fixed array'.

# ===== 17) Floyd-Warshall =====
# - All-pairs shortest paths on small (<= 500) graphs
# Time: O(V^3). Recognise by 'small graph, all pairs'.

# ===== 18) Sweep line =====
# - Skyline problem, interval merging, max events at once
# Recognise by 'intervals + events + sorted scan'.

# ===== 19) Randomised =====
# - Reservoir sampling, quickselect, BloomFilter
# Recognise by 'limited memory + approximate answer ok'.

# ===== 20) String matching =====
# - KMP, Rabin-Karp, Aho-Corasick
# Recognise by 'find pattern(s) in long text'.

# ===== Recognition matters more than implementation =====
# Most interview / production puzzles are 'spot the pattern'. Once named,
# the implementation is a 30-line standard recipe. Build a mental map of
# 'shape -> pattern' and the work becomes fast and confident.

// Patterns to recognise:
// Two pointers, sliding window, binary search on answer, BFS/DFS,
// DP (subset, knapsack, intervals, strings), greedy, monotonic stack/queue,
// union-find, tries, Dijkstra, topological sort.