Concepts318
Category
Topological Sort
Topological sort orders the nodes of a directed acyclic graph (DAG) so every edge points from left to right in the order.
Multi-Source BFS
Multi-source BFS explores an unweighted graph starting from several sources at once to compute the minimum distance to any source for every vertex.
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.
Kinetic Tournament Tree
A kinetic tournament tree maintains the minimum (or maximum) of moving values whose pairwise order can change over time.
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.