Concepts11
Think Backwards (Reverse Thinking)
Think Backwards is a problem‑solving pattern where you reverse time or direction so hard deletions become easy insertions and the final state becomes the starting point.
Stars and Bars
Stars and Bars counts the ways to distribute n identical items into k distinct bins using combinations.
Sieve of Eratosthenes
The Sieve of Eratosthenes marks multiples of each prime to find all primes up to n in O(n log log n) time.
GCD and Euclidean Algorithm
The greatest common divisor (gcd) of two integers is the largest integer that divides both without a remainder.
Z-Function
The Z-function of a string S computes for each position i the length of the longest substring starting at i that matches the prefix of S.
Exchange Arguments in DP
An exchange argument proves that any optimal solution can be reordered to satisfy a simple sorting rule by showing that swapping adjacent out-of-order elements never helps.
Digit DP
Digit DP is a dynamic programming technique for counting or aggregating values over all integers in a range that satisfy a digit-based property.
Lowest Common Ancestor (LCA)
The Lowest Common Ancestor (LCA) of two nodes in a rooted tree is the deepest node that is an ancestor of both.
Minimum Spanning Tree - Prim
Prim's algorithm builds a Minimum Spanning Tree (MST) by growing a tree from an arbitrary start vertex, always adding the lightest edge that connects the tree to a new vertex.
Iterative Segment Tree
An iterative segment tree stores all leaves in tree[n..2n-1] and internal nodes in tree[1..n-1], enabling O(\log n) point updates and range queries without recursion.
Trie (Prefix Tree)
A trie (prefix tree) stores strings or bit-sequences so that common prefixes share nodes, making operations depend on the key length L rather than the set size.