Concepts146
Category
0-1 BFS
0-1 BFS is a shortest path algorithm specialized for graphs whose edge weights are only 0 or 1.
Depth-First Search (DFS)
Depth-First Search (DFS) explores a graph by going as deep as possible along each path before backtracking.
2D Prefix Sum
A 2D prefix sum (also called an integral image) lets you compute the sum of any axis-aligned sub-rectangle in constant time after O(nm) preprocessing.
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.