- Multi-pattern String Matching – Efficiently finds all occurrences of multiple patterns in a single pass over the text.
- Based on Trie and Failure Links – Constructs a finite automaton using a trie with failure links, similar to KMP.
- Linear Time Complexity – Performs search in O(n + m + z) time, where
n is the text size, m total pattern size, and z number of matches.
- Used in Spam Filtering, Bioinformatics – Ideal for dictionary matching and genome string searches.
- Important for Contest Problems – Frequently used in problems involving large dictionary searches or forbidden substrings.
Learn More...
- Time and Space Trade-offs – Uses memoization, dynamic programming, and precomputation to reduce runtime.
- Bit Tricks and Lookups – Bitwise operations often help reduce time in combinatorial or set-based problems.
- Pruning in Search Algorithms – Techniques like branch and bound or early exit reduce unnecessary computation.
- Data Structure Choice Matters – Optimizing with segment trees, heaps, or hash maps is crucial for performance.
- Asymptotic Analysis Awareness – Understanding complexity helps avoid TLE in tight time limits.
Learn More...
- Used for NP-Hard Problems – Provides near-optimal solutions when exact solutions are computationally expensive.
- Greedy and Heuristic Based – Relies on greedy strategies (e.g., for vertex cover, TSP) with known bounds.
- Polynomial Time Guarantees – Balances feasibility and efficiency, ensuring solutions in polynomial time.
- Performance Ratio Bound – Evaluated based on how close the result is to the optimal one.
- Notable in Advanced Contests – Useful in approximation-based problems or when dealing with very large inputs.
Learn More...
- Key in Geometry Problems – Required for polygon area, circle segments, and other shape computations.
- Shoelace Formula for Polygons – A common and efficient technique to calculate area of a non-intersecting polygon.
- Floating-Point Precision Caution – Always consider errors due to float operations in area calculations.
- Grid-Based and Integral Areas – Often used with prefix sums in matrix/grid problems.
- Common in 2D Geometry Challenges – Area computation plays a role in convex hulls and point-in-polygon tests.
Learn More...
- Fundamental Data Structure – Basis for countless problems involving iteration, prefix sums, and sorting.
- Optimized Traversals Matter – Efficient scanning, two-pointer, and sliding window approaches are common.
- Supports Fast Queries via Preprocessing – Prefix sums, difference arrays, and RMQ enable quick computations.
- Subarray and Subsequence Problems – Core to problems in dynamic programming and optimization.
- Works with Binary Search & Divide-Conquer – Especially in sorted arrays or for finding peaks, bounds, etc.
Learn More...
- Recursive Problem Solving Approach – Explores all possible solutions by building them incrementally.
- Used in Combinatorial Problems – Essential for solving N-Queens, Sudoku, subset generation, permutations.
- Incorporates Pruning for Efficiency – Cuts off branches early when a partial solution is invalid.
- Often Combined with Bitmasking – Bitwise tricks can represent state and speed up recursive solutions.
- Key to Constraint Satisfaction – Widely used in problems with multiple constraints and limited choices.
Learn More...
- Foundation for Geometry Problems – Essential for solving distance, angle, perimeter, and area problems.
- Includes Points, Lines, Circles, and Polygons – Understanding their relationships is key in spatial problems.
- Applications in Vector Geometry – Used to calculate dot products, cross products, and projections.
- Important in Convex Hull & Closest Pair – Underpins algorithms in computational geometry.
- Knowledge of Properties Speeds Up Solutions – Recognizing symmetry and constraints can simplify problems.
Learn More...
- Two-Partite Vertex Set – Graph is bipartite if it can be colored with two colors without adjacent nodes sharing one.
- Key in Matching Problems – Used in maximum bipartite matching with DFS/BFS or Hopcroft-Karp algorithm.
- Cycle Check for Even Length – Bipartite graphs cannot have odd-length cycles.
- Used in 2-SAT and Scheduling – Helps model pairing and group-based decision problems.
- Fast Bipartite Check with BFS/DFS – A frequent question in graph theory sections of contests.
Learn More...
- Efficient Space and Time Optimization – Allows fast computation with minimal memory.
- Used in Subset Generation and DP – Bitmasking is essential in problems involving choices/combinations.
- Common in XOR-Based Problems – Tricks like finding unique elements, parity, and toggling are bit-based.
- Speeds Up Logical Checks – Replaces loops with O(1) operations using bit operators.
- Key for Competitive Edge – Often hidden in editorial solutions for advanced problems.
Learn More...
- Classic DP Problem – Solves the number of ways to make change for a given amount using given coins.
- Variants: Min Coins, Combinations, Permutations – Different problems test different dimensions of the same logic.
- Can Be Solved Using 1D or 2D DP – Space can often be optimized with a rolling array or greedy approach.
- Important for Understanding Unbounded Knapsack – The coin change is a classic example of unbounded DP.
- Taught in All Competitive Courses – Serves as an introduction to dynamic programming and recursion memoization.
Learn More...
- Core to Counting Problems: Helps in solving problems involving permutations, combinations, and selections.
- Factorials & Modulo Arithmetic: Efficient computation using precomputed factorials and modular inverses is common.
- Dynamic Programming Integration: Often used in problems requiring combinatorial DP (e.g., Pascal's Triangle).
- Application Areas: Used in probability, graph theory, game theory, and recurrence relations.
- Frequent in Contests: Shows up in contests like Codeforces, AtCoder, and ICPC regionals regularly.
Learn More...
- 2D/3D Geometric Algorithms: Deals with points, lines, polygons, and circles — core to visual and spatial problems.
- Precision Handling: Requires careful use of floating-point comparisons and integer geometry tricks.
- Common Problems: Includes line intersection, polygon area, closest pair, and orientation checks.
- Algorithm Efficiency: Optimal geometric solutions often involve sorting, sweeping lines, or divide & conquer.
- Useful in Real-world Simulations: Helps solve robotics, navigation, and graphics-based CP problems.
Learn More...
- Problem-Solving with Rules: Focuses on assigning values to variables under specific constraints.
- Backtracking Techniques: Often solved using recursive backtracking with pruning (e.g., N-Queens, Sudoku).
- AI and Logic Puzzles: Frequently appears in logic-heavy challenges or interactive programming contests.
- Search Space Reduction: Techniques like forward checking and constraint propagation improve efficiency.
- Foundation for Optimization: Underpins advanced problems in scheduling, planning, and resource allocation.
Learn More...
- Basic Geometry Structure: Constructs the smallest convex polygon enclosing a set of points.
- Classic Algorithms: Implementations like Graham Scan and Andrew's Monotone Chain are common.
- Used in Complex Geometry: Important for problems involving collision detection, visibility, and clustering.
- Efficient Solutions: Can be optimized to O(n log n), a frequent requirement in time-constrained contests.
- 2D & 3D Adaptability: Concept extends to higher dimensions with more advanced techniques.
Learn More...
- Subset Sum Variant: Classic dynamic programming problem involving partitioning and sum calculation.
- DP Table Technique: Commonly solved using a 2D/1D DP array with tabulation or memoization.
- Applicable in Knapsack Problems: Forms the base for 0/1 Knapsack and partition-related challenges.
- Modular Counting: Often requires output modulo large primes due to huge result size.
- Frequent in Coding Tests: Used in Google Kickstart, LeetCode contests, and ACM-style quizzes.
Learn More...
- Prevents Hash Collisions: Especially useful in unordered maps to avoid TLE from adversarial inputs.
- Enhances Performance: Custom hashing secures performance against poor input cases (especially in C++).
- Randomized Techniques: Uses random primes and bitwise operations to generate unpredictable hashes.
- Security and Robustness: Boosts data structure resilience in contests like Codeforces where anti-hashing is a risk.
- Common in C++ STL Fixes: Popular with
gp_hash_table and unordered_map to stabilize runtime.
Learn More...
- Binary and Bitwise Use: Understanding binary formats helps solve XOR, parity, and mask problems.
- Efficient Memory Use: Bitsets, compressed tries, and custom structs optimize space in tight environments.
- Base Conversions: Required for problems involving different number systems or base-10 to base-n conversions.
- Bitmasking: A key technique in subset generation, dynamic programming, and state compression.
- Critical in Edge Cases: Precise handling avoids overflows, signed/unsigned issues, and memory errors.
Learn More...
- Advanced Geometry: Partitions a plane into triangles ensuring no point lies inside any triangle’s circumcircle.
- Used in Mesh Generation: Critical for computer graphics and finite element method problems.
- Implementation Heavy: Complex to code but necessary for some high-level geometric challenges.
- Optimizes Shape Quality: Produces well-shaped triangles avoiding skinny angles—important in simulations.
- Utilized in Closest-Pair Problems: Supports applications in clustering and Voronoi diagram construction.
Learn More...
- Component Tracking: Efficiently keeps track of connected components in graphs.
- Optimized with Path Compression: Speeds up
find() operations, achieving nearly constant time.
- Key in Kruskal’s Algorithm: Essential for building minimum spanning trees.
- Cycle Detection: Used in detecting cycles in undirected graphs.
- Foundational DS: Crucial in problems involving grouping, clustering, and dynamic connectivity.
Learn More...
- Problem Splitting Strategy: Recursively breaks down problems into smaller, manageable sub-problems.
- Reduces Time Complexity: Efficient for sorting (Merge Sort), searching (Binary Search), and inversion counting.
- Used in Geometry: Solves closest-pair, convex hull, and range queries efficiently.
- Enables Parallelization: Sub-problems can often be solved independently, useful in distributed environments.
- Popular in Contests: Frequently used as a strategy for tackling time-constrained large input problems.
Learn More...
- Deals with Changing Graphs: Focuses on maintaining information (like connectivity) in graphs undergoing edge additions or deletions.
- Key Structures: Data structures like Union-Find (Disjoint Set Union - DSU), Link-Cut Trees, and Euler Tour Trees are commonly used.
- Real-Time Queries: Enables fast answers to "Are nodes u and v connected?" even as the graph changes.
- Common in Online Problems: Used in online judges where the input graph evolves over time.
- Challenge Level: Advanced topic—commonly seen in harder problems on platforms like Codeforces and ICPC.
Learn More...
- Optimal Substructure & Overlapping Subproblems: Solves complex problems by breaking them into smaller, manageable subproblems.
- Top-Down & Bottom-Up: Approaches include memoization (recursive) and tabulation (iterative).
- Wide Application: Common in problems involving sequences, paths, knapsack variants, and game states.
- Space & Time Optimization: Techniques like rolling arrays or state compression are vital for efficient solutions.
- Must-Know Topic: Frequently appears in contests from beginner to advanced levels (e.g., Leetcode, AtCoder, Codeforces).
Learn More...
- String Similarity Measure: Calculates the minimum number of operations (insert, delete, replace) to convert one string to another.
- Dynamic Programming Based: Solved using a 2D DP table where
dp[i][j] represents edit distance for substrings.
- Common Use Case: Appears in problems related to spelling correction, DNA sequencing, or diff-checking tools.
- Time Complexity: Typically O(n × m), where n and m are lengths of the two strings.
- Optimizations Possible: Can be optimized with space-reduction techniques or bounded edit distance constraints.
Learn More...
- Graph Traversal Properties: Eulerian paths cover every edge once; Hamiltonian paths visit every vertex once.
- Existence Conditions: Eulerian paths require specific degree conditions; Hamiltonian ones are NP-complete to determine.
- Algorithmic Applications: Useful in circuit design, routing, and puzzle-solving problems like the Knight’s tour.
- Constructive Algorithms: Hierholzer’s algorithm is often used to find Eulerian circuits.
- Tricky in Contests: Hamiltonian problems are often decision-based and appear in backtracking or bitmask DP contexts.
Learn More...
- Fast Power Calculation: Reduces time complexity from O(n) to O(log n) when computing
a^b.
- Modular Arithmetic: Frequently used for modular exponentiation in problems involving large numbers.
- Key in Number Theory Problems: Critical for solving Fermat’s Little Theorem, modular inverses, and cryptographic applications.
- Iterative or Recursive: Can be implemented both recursively or using iterative loops.
- Constant-Time Optimization: Often needed for passing tight time constraints in modular math-heavy contests.
Learn More...
- Polynomial Multiplication: Efficiently multiplies two large polynomials in O(n log n) time.
- Number-Theoretic Transform (NTT): A variant used for modular integer arithmetic, avoiding floating-point errors.
- Useful for String Matching: Applied in pattern matching, convolution, and cross-correlation problems.
- High Difficulty: Often used in high-rated problems due to complexity and precision handling.
- Precision & Rounding Issues: Requires careful handling of rounding and floating-point precision during inverse FFT.
Learn More...
- Critical for Large Input/Output: Boosts speed when handling huge datasets in time-constrained problems.
- Language-Specific Methods: Uses
scanf/printf or getchar_unlocked in C++, sys.stdin.readline in Python, etc.
- Avoids TLE: Especially useful in problems where input size is 10⁵ or more.
- Buffered I/O: Implements manual buffering to minimize OS-level read/write calls.
- Tradeoff with Readability: Often makes code less readable but significantly faster for performance-intensive problems.
Learn More...
- Efficient Prefix Queries: Performs prefix sums and point updates in O(log n) time.
- Space Efficient: Requires only O(n) extra space, making it lightweight compared to segment trees.
- Easy to Implement: Simpler than segment trees for basic range operations.
- Popular in Range Queries: Commonly used in problems involving frequency counting, inversions, and dynamic sums.
- Variants Available: Can be extended for 2D grids, range updates, or difference arrays.
Learn More...
- Mathematical Modeling of Games: Analyzes optimal strategies for multi-player, turn-based games.
- Key Concepts: Includes Grundy numbers, Nim game, Sprague-Grundy theorem, and Zermelo’s theorem.
- Combinatorial Games: Appears in puzzles and logic-based challenges where players alternate moves.
- Decision-Making Under Uncertainty: Applies to problems where state transitions depend on player choices.
- High-Concept Level: Often rated medium to hard in contests due to abstract logic and number theory integration.
Learn More...
- Area and Perimeter Calculations: Uses Shoelace formula or vector-based math for polygonal measurements.
- Point-in-Polygon Tests: Ray casting and angle summation methods used to check point containment.
- Convex Hulls & Triangulation: Algorithms like Graham’s Scan or Monotone Chain build convex shapes from points.
- Sweep Line & Rotating Calipers: Handle problems like closest pair, diameter, or intersection efficiently.
- Precision Handling: Requires attention to floating-point errors and integer overflows in competitive settings.
Learn More...
- Precision and Edge Cases: Geometry problems often require handling floating-point precision and boundary conditions carefully.
- Key Concepts: Include line intersection, convex hulls, polygon area, distance formulas, angle computation, etc.
- Common Applications: Used in simulations, game development challenges, and spatial computation problems.
- Complexity Consideration: Efficient implementations (e.g., O(n log n) convex hull) are essential for passing tight time limits.
- Important Techniques: Include cross products, orientation tests, rotating calipers, and sweep line algorithms.
Learn More...
- Foundation of CP: Graphs appear in shortest path, connectivity, cycles, spanning trees, and flows—core in contests.
- Standard Techniques: Dijkstra, Bellman-Ford, Floyd-Warshall, Prim's and Kruskal's algorithms are essential.
- Graph Representation: Adjacency lists and matrices are chosen based on space/time trade-offs.
- Weighted and Unweighted Variants: Different strategies are applied depending on edge weights or their absence.
- Application Areas: Includes routing problems, dependency resolution, and map-based simulations.
Learn More...
- NP-Hard Variant: Exact minimum coloring is NP-hard, but greedy or heuristic methods are used in contests.
- 2-Coloring/Bipartite Check: A classic subproblem used to test graph parity, detect odd-length cycles.
- Applications in Scheduling: Resource allocation, register allocation, and task planning problems often reduce to coloring.
- Backtracking for Small Inputs: Exhaustive methods like backtracking work well for graphs with limited size (e.g., n ≤ 10).
- Used in Constraints Validation: Useful to detect feasible configurations in constraint satisfaction problems.
Learn More...
- Conceptual Foundation: Includes terminology like nodes, edges, degrees, paths, and types of graphs (directed/undirected).
- Understanding Graph Types: Trees, DAGs, and cyclic/acyclic graphs behave differently in competitive problems.
- Modeling Real-World Scenarios: Problems involving roads, networks, or relationships often reduce to graphs.
- Graph Construction Tricks: Converting constraints into graphs helps solve problems with logical dependencies.
- Basis for Advanced Topics: Basics are needed to grasp algorithms like topological sort, SCCs, and articulation points.
Learn More...
- Common Themes: Include pathfinding, connectivity checks, bridges, and spanning trees.
- Classical Problem Types: Eulerian path, Hamiltonian cycles, and network flow are frequent in contests.
- Interactive and Dynamic Variants: Some problems involve adding/removing edges dynamically.
- Algorithm Design Skills: Requires combining traversal, greedy, or dynamic programming with graph logic.
- Critical Thinking: Often involves reformulating the problem using graph logic to simplify and solve efficiently.
Learn More...
- Core Strategy: DFS and BFS are fundamental tools for searching and exploring graphs in O(N+M) time.
- Usage Patterns: DFS is common in cycle detection, backtracking; BFS is ideal for shortest paths in unweighted graphs.
- Tree and Component Detection: DFS helps in identifying connected components, trees, and articulation points.
- Level-wise Processing: BFS is preferred when layer-by-layer processing is needed (e.g., distance from a source).
- Memory Optimization: Use visited arrays and stack/queue techniques efficiently to avoid TLEs in large inputs.
Learn More...
- Universal Data Structure: Graphs model a wide range of problems—from routes to dependencies to flow systems.
- Directed vs Undirected: Contest problems may explicitly or implicitly use graph directionality—important to understand.
- Data Input Challenges: Understanding different edge formats and preprocessing is key in fast graph construction.
- Graph Search Algorithms: Mastery of DFS, BFS, and Union-Find is critical for competitive success.
- Foundation for Advanced Areas: Concepts like SCCs, bridges, and flows are built on graph fundamentals.
Learn More...
- Fundamental Number Theory Tool: Used in problems involving divisibility, ratios, and simplifying expressions.
- Efficient Algorithm: Euclidean algorithm finds GCD in O(log N) time and is commonly used in time-critical problems.
- Applications: Appears in LCM, modulo arithmetic, cryptography, and Diophantine equations.
- Binary GCD Optimization: A faster variant using bitwise operations, useful for large input sizes.
- Extended GCD: Helps solve linear congruences and modular inverse problems in CP.
Learn More...
- Local Optimal Choice Strategy: Selects the best immediate choice hoping it leads to a global optimum.
- Used in Classic Problems: Includes activity selection, coin change (non-uniform), interval covering, and Huffman coding.
- Proof Required: Not all problems are solvable greedily—requires mathematical or logical proof of correctness.
- Time Efficiency: Usually offers O(n log n) or better solutions, ideal for time-constrained problems.
- Fail Cases Are Insightful: Learning when greedy fails improves understanding of when to use DP or backtracking instead.
Learn More...
- Analyzing Greedy Validity: Key step is to prove that greedy solutions always lead to an optimal answer.
- Exchange Argument: A common proof technique—showing that any optimal solution can be converted into greedy one.
- Mathematical Backing: Many problems require establishing monotonicity or greedy-choice properties.
- Multiple Strategies Exist: Trying different greedy criteria (e.g., sort by weight, ratio, deadline) may yield optimal paths.
- Optimal Substructure Relevance: Greedy works best when subproblems also contain optimal solutions.
Learn More...
- Allow constant-time average-case insertion, deletion, and lookup—ideal for problems with large input sizes.
- Widely used in frequency counting, anagram detection, and sliding window problems.
- Handle collisions using techniques like chaining and open addressing.
- Standard in languages like C++ (unordered_map) and Python (dict).
- Must be used carefully in contests due to potential worst-case time of O(n) if poorly implemented.
Learn More...
- Efficiently maintain the largest or smallest element with O(log n) insertions and deletions.
- Key to solving priority-based problems like Dijkstra’s algorithm and median streams.
- Binary heaps are most common, though Fibonacci and Binomial heaps offer theoretical advantages.
- Built-in support available in C++ (
priority_queue) and Python (heapq).
- Useful in interval scheduling, job processing, and greedy strategies.
Learn More...
- Decomposes a tree into heavy and light paths for efficient path queries and updates.
- Optimizes segment tree or BIT operations on paths in logarithmic time.
- Solves problems involving LCA, subtree queries, and dynamic tree queries.
- Often used in conjunction with Euler Tour or Segment Trees.
- Complex to implement but invaluable in advanced graph problems in contests like Codeforces.
Learn More...
- Helps in solving problems on divisors, prime checking, and number theory puzzles.
- Efficient algorithms include Trial Division, Pollard’s Rho, and Fermat’s Method.
- Integral in modular arithmetic, RSA encryption, and sieve-based optimizations.
- Factoring efficiently is essential for competitive problems involving large inputs.
- Often paired with precomputation techniques like Sieve of Eratosthenes.
Learn More...
- Multi-dimensional binary search trees used for spatial data (e.g., nearest neighbor search).
- Used in computational geometry problems like range queries and point location.
- Balanced K-D trees allow O(log n) average case query and insert.
- Complexity increases with dimension—practical up to 3D or 4D in contests.
- Rare but powerful in advanced geometry problems on platforms like AtCoder or ICPC.
Learn More...
- A classic dynamic programming problem modeling item selection under constraints.
- Variants include 0/1 Knapsack, Unbounded Knapsack, and Multiple Knapsack.
- Efficient solutions use 1D DP with space optimization.
- Appears in problems involving subset sums, budgeting, and resource allocation.
- Teaches DP fundamentals like overlapping subproblems and optimal substructure.
Learn More...
- Crucial in problems involving scheduling, periodicity, and modular arithmetic.
- Can be computed via
LCM(a, b) = (a × b) / GCD(a, b) using Euclid’s algorithm.
- LCM of multiple numbers often appears in divisibility and simulation challenges.
- Used with caution to avoid overflow in large number problems.
- Often paired with prime factorization for fast multiple LCM queries.
Learn More...
- Fundamental in geometry problems—checking if two lines or segments cross.
- Requires handling of edge cases like colinearity, overlapping, and precision errors.
- Vector cross product and orientation methods are standard techniques.
- Used in sweep line algorithms for finding all intersecting pairs in O(n log n).
- Can be extended to polygon intersection and convex hull problems.
Learn More...
- A dynamic tree data structure supporting path queries and updates in amortized O(log n).
- Ideal for problems involving changing tree structures (e.g., dynamic connectivity).
- Based on Splay Trees, involving complex rotations and lazy updates.
- Solves advanced problems in dynamic graph and network optimization.
- Frequently used in high-level contests like IOI and Codeforces Div 1.
Learn More...
- Enable efficient O(1) insertions/deletions without shifting elements.
- Common in simulation, data structure implementation, and pointer-based problems.
- Doubly linked lists support bidirectional traversal and are used in LRU cache problems.
- Less common in pure algorithmic problems due to language abstraction (e.g., Python/C++).
- Important for understanding memory management and pointer manipulation.
Learn More...
- LCS is a classic dynamic programming problem used to find the longest subsequence present in two sequences.
- It has applications in string comparison, version control (e.g., diff tools), and bioinformatics.
- The standard DP approach has O(n × m) time complexity, where n and m are lengths of the input strings.
- Space can be optimized using only two arrays if only the LCS length is needed.
- Variants like printing the LCS or finding LCS of three strings often appear in advanced contests.
Learn More...
- LIS finds the longest subsequence in an array where the elements are strictly increasing.
- Solvable using DP (O(n²)) or with binary search optimization (O(n log n)), useful in time-sensitive contests.
- A common trick is using
std::lower_bound (C++) or bisect_left (Python) in the O(n log n) approach.
- Frequently used in DP-on-subsequences, sequence transformation, and game theory problems.
- Understanding LIS is essential for tackling problems on patience sorting and subsequence-based scoring.
Learn More...
- Involves finding the longest substring that reads the same forward and backward.
- Solvable using DP (O(n²)), expand-around-center (O(n²)), or Manacher’s algorithm (O(n)).
- Appears in problems related to string preprocessing, text compression, and pattern recognition.
- Manacher’s Algorithm is less common but highly efficient and worth mastering for advanced contests.
- Helps build foundational knowledge for palindrome partitioning and suffix structures.
Learn More...
- Many CP problems require proof-based thinking to justify greedy choices or DP transitions.
- Familiarity with induction, contradiction, and invariants is essential for logic-heavy problems.
- Proofs are especially crucial in constructive algorithms and optimization proofs.
- Common in Olympiad-level contests and theoretical problems on platforms like Codeforces or AtCoder.
- Enhances one’s ability to validate algorithm correctness and derive tight complexity bounds.
Learn More...
- A classic parenthesization DP problem that minimizes the number of scalar multiplications.
- Time complexity is O(n³) with bottom-up DP; often used to teach optimal substructure.
- Appears in problems involving expression evaluation, segmented DP, and tree construction.
- Requires careful indexing and recursion to avoid off-by-one errors.
- Useful in understanding interval DP, which is foundational for several partitioning problems.
Learn More...
- Solve problems related to network capacity, such as job assignment, bipartite matching, and circulation.
- Ford-Fulkerson uses DFS with residual graphs but can be slow for large graphs (O(max_flow × E)).
- Edmonds-Karp uses BFS and guarantees O(V × E²) time complexity.
- Vital for tackling problems in competitive graph theory, especially on flow and cuts.
- Frequently tested in ICPC-style contests and graph-heavy problem sets.
Learn More...
- Used to find the cheapest way to connect all nodes in a graph with minimal total edge weight.
- Kruskal’s algorithm (greedy) uses DSU and works best with sparse graphs.
- Prim’s algorithm works well with dense graphs using min-heaps or adjacency matrices.
- Often used in problems involving network design, travel cost minimization, and graph partitioning.
- Understanding MST is essential for solving variants like 2nd best MST, maximum weight MST, etc.
Learn More...
- Core technique in problems involving large integers, number theory, and cyclic behaviors.
- Includes concepts like modular inverse, modular exponentiation, and modular multiplication.
- Essential for handling large calculations in combinatorics (nCr mod p) or cryptographic-style problems.
- Fast exponentiation (binary exponentiation) is a must-know for modular powers.
- Problems often involve modulo primes, requiring Fermat’s or Euler’s theorem.
Learn More...
- Generalized topic covering max-flow, min-cut, bipartite matching, and circulations.
- Core algorithms include Dinic’s (O(V²E)) and Push-Relabel for higher efficiency.
- Appears in complex real-world simulation problems like traffic routing, resource allocation, etc.
- Requires graph modeling skills to translate real problems into flow networks.
- Common in harder CP contests (Div 1) and Olympiad-level problem sets.
Learn More...
- Includes GCD/LCM, sieve of Eratosthenes, modular arithmetic, and prime factorization.
- Problems range from simple divisibility to Diophantine equations and Euler’s theorem.
- Crucial for solving CP problems involving crypto, hashing, or counting divisors/factors.
- Mastery helps in efficiently solving large-input problems using mathematical optimizations.
- Frequently appears in math-heavy contests and number-based puzzles (e.g., Project Euler, AtCoder).
Learn More...
- Foundation for Modular Arithmetic – Vital for solving problems involving remainders and congruences.
- Includes GCD, LCM, Primes, and Divisibility – Frequently asked in contests for efficiency-based logic.
- Crucial for Cryptographic and Combinatorial Problems – Powers RSA, permutations, and counting techniques.
- Optimized Techniques Matter – Uses fast exponentiation, Euclidean algorithm, and modulo inverse.
- Applied in Number-Based Problem Patterns – Essential in puzzles involving factorials, digits, and parity.
Learn More...
- Not Typical in Online Contests, but useful for high-performance algorithmic simulations.
- Optimizes Execution Time by splitting problems across threads or systems.
- Involves Concepts like Fork/Join, MPI, and Multithreading – important for real-world large datasets.
- Advanced Category in Some Hackathons – Especially in contests involving massive input/output.
- Understanding Parallel Models can help implement concurrent data structure simulations.
Learn More...
- Enable Access to Past Versions of a data structure without full duplication.
- Common Types include persistent segment trees and persistent tries.
- Efficient for Time-Travel Queries – Used in problems involving history or undo operations.
- Require Functional Programming or Smart Memory Techniques – like path copying or node versioning.
- Advanced Topic, but Often Competitive-Grade – Especially in Codeforces or ICPC-level contests.
Learn More...
- Classical Geometry Problem used to test spatial reasoning.
- Ray Casting and Winding Number Algorithms are key techniques.
- Useful in Collision Detection or map-based simulations in competitions.
- Requires Precision Handling of floating-point arithmetic and edge cases.
- Essential for Geometry-Based Contests and often combined with polygon area or triangulation problems.
Learn More...
- Sieve of Eratosthenes is Standard Tool for fast prime generation.
- Segmented and Linear Sieve help with larger ranges and optimization.
- Core to Factorization and Primality Tests – Common in cryptographic problem sets.
- Often Used with Number Theory for solving co-primality, totients, and divisor count problems.
- Fast Implementation Helps Avoid TLE in large constraint test cases.
Learn More...
- Used in Expected Value Problems, Bayesian logic, and Monte Carlo simulations.
- Important for Randomized Problem Solving in uncertain environments.
- Probability Distributions Help in Modeling Events like coin tosses, dice rolls, etc.
- Needs Precision in Floating Point Math and Modulo Handling.
- Sometimes Combined with DP in expected operations or survival probabilities.
Learn More...
- Includes Greedy, Divide-and-Conquer, and Dynamic Programming.
- Focuses on Pattern Recognition and classifying problems by type.
- Time and Space Complexity Tradeoffs are at the core of strategy selection.
- Approaching Problems via Examples and Edge Cases is essential.
- Strategy Impacts Scoring and Speed – critical in short-duration contests.
Learn More...
- Basic Linear Data Structure used in BFS, simulation, and scheduling problems.
- Variants like Deque and Priority Queue expand problem-solving power.
- Important in Sliding Window Problems and Monotonic Queue Applications.
- Often Used with Graph Algorithms for shortest path and traversal logic.
- Standard STL Implementations in most languages make it contest-friendly.
Learn More...
- Introduce Probabilistic Solutions to otherwise deterministic problems.
- Examples Include QuickSort, Treap, and Miller-Rabin Primality Test.
- Used for Optimization and Estimations – e.g., expected value calculations.
- Helps Avoid Worst-Case Scenarios in adversarial inputs.
- Powerful in Hashing and Monte Carlo-Based Techniques.
Learn More...
- Multidimensional Data Structure used for range queries in 2D or more.
- Useful in Computational Geometry, often paired with segment trees.
- Solves Problems Like Count of Points in a Rectangle.
- Space and Time Complexity are higher than simple segment trees.
- Advanced, But Powerful in Geometry + Range Queries Hybrid Problems.
Learn More...
- Pattern Matching Tool: Useful for validating and parsing input formats quickly (e.g., email, number, custom tokens).
- Optimized for String Problems: Helps in identifying repeated patterns, substitutions, and filters efficiently.
- Widely Supported in Languages: Available in Python (
re), Java (Pattern), C++ (with libraries).
- Used in Input Sanitization: Cleans up or extracts relevant parts from large input data.
- Can Be Replaced by Manual Parsing: In time-critical contests, manual parsing may outperform regex in speed.
Learn More...
- Classic DP Problem: Involves breaking a rod to maximize profit using optimal substructure and overlapping subproblems.
- Top-Down and Bottom-Up Approaches: Teaches memoization and iterative DP formulation.
- Similar to Knapsack Variants: Helps understand bounded and unbounded knapsack patterns.
- Optimizes Resource Usage: Models scenarios of resource partitioning and cost-benefit analysis.
- Frequent in Intermediate-Level Contests: Commonly tested for DP proficiency and recursion-to-DP transitions.
Learn More...
- Binary & Linear Search Are Core: Binary search is key in ordered data problems with O(log n) complexity.
- Advanced Searches (Ternary, Exponential): Useful in optimization and unimodal function problems.
- Applied in Search Space Problems: Great for problems like “find smallest/largest possible answer.”
- Often Paired with Sorting: Sorting data before searching is a common prerequisite in many problems.
- Key for Real-Time Input Handling: Enables efficient lookups in huge datasets during runtime.
Learn More...
- Efficient Range Query Tool: Supports operations like sum, min, max, GCD over subarrays in O(log n).
- Used in Offline/Online Queries: Especially when there are multiple dynamic range updates and queries.
- Extendable with Lazy Propagation: Optimizes update operations in complex scenarios.
- Foundation for Advanced Trees: Basis for Fenwick Trees, Merge Sort Trees, and other hybrids.
- Essential for Data Structure Rounds: A must-know for range query problems in Codeforces, AtCoder, etc.
Learn More...
- Fundamental Graph Algorithms: Solve routing, travel time, and connectivity problems.
- Dijkstra is Fast for Non-Negative Weights: Uses priority queue (min-heap) to achieve O(E log V).
- Bellman-Ford Handles Negative Weights: Slower but supports edge weight validation and cycle detection.
- Tested in Grid, Network, and Map Problems: Found in classic pathfinding and dynamic graphs.
- Foundation for Advanced Graph Techniques: Basis for A*, Floyd-Warshall, Johnson’s algorithm.
Learn More...
- Used to Emulate Real-World Processes: Models games, movement, queues, etc.
- Often Requires Brute Force Optimization: Focus is on logic accuracy, not asymptotic speed.
- Edge Case Handling is Crucial: Demands meticulous care for off-by-one, limits, and constraints.
- Helps in Understanding Problem Constraints: Best for when there's no formulaic solution.
- Appears in Ad-Hoc & Implementation Problems: Common in contest rounds testing simulation logic.
Learn More...
- Efficient for Subarray Problems: Reduces nested loops to linear time (O(n)) in optimal cases.
- Solves Problems Like Max Sum/Min Length: Ideal for fixed or variable-size window queries.
- Two-Pointer Variant Used in String/Array: Common in substring checks and cumulative range updates.
- Used in Online and Streaming Data: Applies in problems needing real-time window tracking.
- Improves Time Complexity: Crucial optimization over brute-force in contests.
Learn More...
- Core Preprocessing Step: Enables binary search, greedy selection, and range grouping.
- Built-In Sorts Are Highly Optimized: Standard libraries (Timsort, Introsort) are allowed in contests.
- Custom Sort Functions are Key: Used in sorting pairs, structs, or based on custom rules.
- Enables Greedy and Sweep Line Techniques: Sorting intervals or events is foundational in many problems.
- Sorting + Binary Search = Power Combo: A frequent pattern in competitive problems.
Learn More...
- Optimizes Space for Sparse Data: Stores only non-zero elements, reducing memory usage.
- Used in Graph Adjacency and Matrix-Based Problems: Efficient in large but sparse graphs/matrices.
- Fast for Matrix Operations: Allows quicker transposes, multiplications, and traversals.
- Array of Triplets Format is Common: Stores (row, col, value) in structured representation.
- Memory-Efficient in Large Inputs: Useful in scenarios with tight space constraints.
Learn More...
- Preprocessing-Based Range Queries: Ideal for static data with immutable arrays.
- O(1) Query Time with O(n log n) Setup: Excellent for RMQ (Range Min/Max Query) problems.
- Space-Time Tradeoff: Uses more space than segment trees but gives faster results for immutable data.
- Binary Lifting Principle: Leverages powers of two for preprocessing query answers.
- Common in Advanced Rounds: Used for solving static range queries in high-rated problems.
Learn More...
- LIFO Data Structure: Operates on a Last-In-First-Out principle, useful for managing function calls, undo operations, and backtracking.
- Common Problems: Balancing parentheses, evaluating postfix/prefix expressions, and stock span problems.
- Monotonic Stack Usage: Efficient in finding nearest greater/smaller elements and solving sliding window problems.
- Time Efficiency: Allows O(1) insertion and deletion, making it ideal for real-time logic execution.
- Used in DFS and Recursion: Essential in simulating recursion and solving depth-first traversal problems.
Learn More...
- Core for Text Problems: Include algorithms for pattern matching, string searching, hashing, and transformations.
- Crucial Algorithms: KMP, Z-algorithm, Rabin-Karp, and Trie-based solutions are frequent in contests.
- String Hashing: Helps in achieving O(1) substring comparisons for large strings in coding challenges.
- Optimizes Brute Force: Avoids TLE in repeated pattern checking and multi-pattern searches.
- Used in DNA Analysis & Parsing: Applies to bioinformatics, compilers, and big data string searches.
Learn More...
- Reduces Space Complexity: Efficient for storing large strings with repeating characters (e.g., RLE).
- Challenge in Optimality: Problems often require choosing the minimal compressed size while preserving data.
- Used in Substring Analysis: Helpful in grouping repeated substrings and solving encoding/decoding problems.
- Dynamic Programming Integration: Some variants require DP to determine optimal compression strategies.
- Real-World Context: Emulates basic forms of algorithms used in gzip, LZW, and text editors.
Learn More...
- Fundamental Skill: Includes operations like reversing, slicing, modifying substrings, and character shifts.
- High Frequency in Contests: Common in basic to intermediate-level problems across all platforms.
- Requires Edge Handling: Test cases often exploit whitespace, empty strings, and Unicode characters.
- Important for Parsing: Used in data extraction, log file analysis, and input formatting.
- Efficient Libraries Help: Mastery of standard libraries (e.g.,
string, collections, StringBuilder) gives a coding edge.
Learn More...
- KMP for Linear Matching: Uses prefix function to avoid redundant comparisons—O(n + m) time.
- Rabin-Karp for Hash-Based Matching: Ideal for detecting multiple patterns using rolling hash.
- Z-Algorithm: Efficiently finds all pattern occurrences in O(n) using prefix comparisons.
- Used in Plagiarism Detection: Matching substrings and sequences across long documents.
- Avoids Brute Force: Crucial for solving large pattern-matching problems under tight constraints.
Learn More...
- Essential for Input Processing: Breaks strings into tokens based on delimiters for structured input.
- Used in Compiler Problems: Tokenizing expressions is key to building interpreters or evaluators.
- Edge Case Sensitivity: Handles escaped characters, nested expressions, and empty fields.
- Often Paired with Maps: Tokenized data is stored and processed using dictionaries or counters.
- Regex Integration: Regular expressions often enhance or simplify parsing in competitive tasks.
Learn More...
- Graph Theory Core: Detects subsets of nodes where each node is reachable from every other node in the subset.
- Kosaraju’s & Tarjan’s Algorithms: Used for efficient SCC detection in O(V + E) time.
- Used in Deadlock Detection: Practical in system design and dependency analysis problems.
- Foundation of 2-SAT Solvers: SCCs form the backbone of Boolean satisfiability problems.
- Enhances Graph Decomposition: Often a substep in more complex graph algorithms like condensation DAGs.
Learn More...
- Classic DP Problem: Checks if a subset of given numbers can sum up to a target value.
- Foundation for Knapsack: Basis of the 0/1 Knapsack problem and many combinatorial variants.
- Used in Partitioning Problems: Essential for solving equal sum partitions, multi-set decisions, etc.
- Bitmask Variants: Small constraints allow backtracking or bitmask solutions for subsets.
- Optimizations via Memoization: Dynamic programming with memoization handles large inputs efficiently.
Learn More...
- Efficient Text Indexing: Stores lexicographically sorted suffixes of a string to enable fast search.
- Alternative to Suffix Trees: Easier to implement with lower memory overhead.
- Used in Pattern Matching: Helpful in solving longest repeated substring, LCP arrays, and substring frequency queries.
- Suffix + LCP Combo: Combines with Longest Common Prefix for advanced string problems.
- Time Efficient: Built in O(n log n) using algorithms like doubling or induced sorting (SA-IS).
Learn More...
- Compressed Trie of Suffixes: Allows linear-time operations like substring search and pattern matching.
- Built Using Ukkonen’s Algorithm: Efficient O(n) construction using online techniques.
- Solves Complex Problems: Used in LCS (Longest Common Substring), palindrome detection, and data compression.
- Higher Memory Use: More memory intensive than suffix arrays, but powerful in substring handling.
- Important in Bioinformatics: Facilitates genome sequence matching and DNA pattern analysis.
Learn More...
- A technique used to process events in a sorted order, often from left to right (e.g., on a plane).
- Efficient for solving geometry-based problems like interval intersections and line segment overlaps.
- Relies on event queues and balanced trees or multisets for active intervals.
- Frequently used in problems involving overlapping rectangles, skyline, or computational geometry.
- Helps achieve O(n log n) time complexity in problems that seem quadratic otherwise.
Learn More...
- A linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u → v, u comes before v.
- Essential in scheduling, task ordering, and course prerequisite problems.
- Implemented using Kahn’s Algorithm (BFS) or DFS with stack.
- Frequently appears in dependency resolution problems.
- A prerequisite concept for solving dynamic programming on DAGs.
Learn More...
- A classic NP-hard optimization problem: find the shortest route visiting all cities once and returning to the start.
- Solved via brute-force (O(n!)), Dynamic Programming + Bitmasking (O(n²·2ⁿ)), or Approximation Algorithms.
- Common in contests as a test of bitmasking and state compression.
- Real-life applications in logistics, route optimization, and robotics.
- Frequently combined with graph traversal or heuristics (e.g., Nearest Neighbor).
Learn More...
- A randomized balanced binary search tree that combines a binary search tree (BST) and heap.
- Maintains order using keys and random priorities to ensure expected O(log n) operations.
- Useful in problems requiring ordered sets, splits, merges, and range queries.
- Supports operations like insertion, deletion, and k-th element search efficiently.
- Common in competitive programming contests and segment tree alternatives.
Learn More...
- Hierarchical data structures fundamental to graph theory and recursion in competitive programming.
- Tree problems involve DFS, BFS, LCA (Lowest Common Ancestor), and dynamic programming on trees.
- Common types include binary trees, N-ary trees, and rooted trees.
- Used to model hierarchies, file systems, and network topologies.
- Key for solving path queries, diameter, and centroid decomposition.
Learn More...
- A set of operations (insert, search, delete) performed on a prefix tree or Trie.
- Allows efficient string matching and prefix queries in O(length) time.
- Useful for problems involving dictionaries, autocomplete, and word search.
- Can be extended to handle bitwise operations (e.g., maximum XOR queries).
- Appears in competitive problems on strings, tries, and word combinations.
Learn More...
- A tree-based data structure for string processing, where each node represents a character.
- Excellent for storing large datasets of strings with overlapping prefixes.
- Useful in problems involving pattern matching, longest prefix, and auto-completion.
- Often paired with bitwise tricks or DP for optimization problems.
- Appears in online judges for dictionary-based or string-search challenges.
Learn More...
- A method using two indices to traverse data, typically arrays or strings.
- Best suited for sorted arrays or problems involving subarray/substring windows.
- Solves problems like pair sums, longest subarray with condition, or sliding window max efficiently.
- Optimizes many brute-force approaches from O(n²) to O(n).
- Commonly used in binary search + greedy combo techniques.
Learn More...
- A computational geometry structure that partitions space based on proximity to a set of points.
- Each cell contains points closer to its seed point than any other.
- Used in problems involving nearest neighbor queries, path planning, and map generation.
- Complex but powerful, with O(n log n) construction using Fortune’s algorithm.
- Applied in advanced geometry and real-world simulation problems.
Learn More...
- An efficient string matching algorithm that computes the Z-array in O(n) time.
- Z[i] denotes the length of the longest prefix starting at i that matches the prefix of the string.
- Useful in pattern matching, string compression, palindrome detection, and bioinformatics.
- More optimal than brute force in cases like substring searches or prefix queries.
- Frequently appears in Codeforces, AtCoder, and string-based contest problems.
Learn More...