Concepts204
Category
Prefix Sum and Difference Array
Prefix sums precompute running totals so any range sum [l, r] can be answered in O(1) time as prefix[r] - prefix[l-1].
Coordinate Compression
Coordinate compression replaces large, sparse, or arbitrary values with small consecutive integers while preserving relative order.
Complete Search and Backtracking
Complete search enumerates every candidate solution, while backtracking prunes branches that cannot possibly lead to a valid or better solution.
Sorting Algorithms
Sorting arranges items into a chosen order so that searching, grouping, and further algorithms become faster and simpler.
Greedy - Exchange Argument
The exchange argument proves a greedy algorithm is optimal by swapping out-of-order choices in any supposed optimal solution until it matches the greedy one without making it worse.
Greedy Algorithms
Greedy algorithms build a solution step by step by always taking the best local choice available.
Sliding Window
Sliding window is a technique that moves a contiguous segment (window) across an array or string while maintaining some running information like sum, count, or max.
Ternary Search
Ternary search finds the maximum or minimum of a unimodal function on a line by probing two interior points and discarding one third of the interval each step.
Binary Search on Answer
Binary Search on Answer turns an optimization problem into a yes/no decision problem over a monotonic answer space.
Two Pointers
Two pointers is a pattern where two indices move through a sequence in a coordinated, usually monotonic way to avoid unnecessary work.
Binary Search
Binary search quickly finds targets or boundaries in sorted or monotonic data by halving the search interval each step.
Merge Sort Tree
A Merge Sort Tree is a segment tree where every node stores the sorted list of values in its segment.