| Space Optimization (In-Place Computation) | Modify array in-place (e.g., Remove Duplicates) | No change | O(N) → O(1) | Modifies input data without extra space to save memory. Used in in-place sorting, removing duplicates, modifying linked lists. |
| Boyer-Moore Voting Algorithm | Majority Element (LeetCode #169) | O(N) (Single pass) | O(N) → O(1) | Efficiently finds the majority element in O(N) time & O(1) space. |
| Hashing (Frequency Maps, Sets) | Fast Lookups, De-duplication, Caching | O(N) → O(1) (Avg Case) | O(N) → O(1) (Perfect Hashing) | Uses hashmaps & hashsets for fast lookups, counting occurrences, and duplicate detection. |
| Meet in the Middle | Subset Sum, Combinatorial Problems | O(2^N) → O(2^(N/2)) | No change | Splits a problem into two halves to reduce exponential complexity for subset sum & combinatorial problems. |
| Mo’s Algorithm | Range Queries (Distinct Elements, RMQ) | O(N) → O(sqrt(N)) | No change | Optimizes range queries (like number of distinct elements in a range) using sqrt decomposition. |
| Heavy-Light Decomposition (HLD) | Tree Path Queries (LCA, Sum on Path) | O(N) → O(log N) | No change | Optimizes tree path queries like LCA (Lowest Common Ancestor) and sum on a path by decomposing trees into logarithmic chains. |
| Bitmasking | Subset Problems, XOR Queries | O(2^N) → O(N * 2^N) | O(N) → O(1) | Uses bitwise operations to store & process subsets efficiently, useful in XOR problems & Dynamic Programming. |
| Sqrt Decomposition | Range Queries, Update Problems | O(N) → O(sqrt(N)) | No change | Divides data into sqrt(N) blocks for efficient range sum, min/max, and frequency queries. |
| Bloom Filter | Fast Approximate Membership Queries | O(N) → O(1) (Probabilistic) | O(N) → O(1) | Probabilistic data structure for fast membership testing (e.g., checking if an element exists in a dataset). Used in Google Safe Browsing, databases, and network security. |
| Line Sweep Algorithm | Overlapping Intervals, Event Processing | O(N log N) (Sorting step) | No change | Processes sorted events in order to efficiently solve interval problems like meeting rooms, skyline problems, and sweep-line intersections. |
| Segment Trees | Range Queries (Sum, Min, Max, Lazy Propagation) | O(N) → O(log N) (Query/Update) | O(N) → O(N) | Data structure for efficient range queries (sum, min/max, range updates) in O(log N). |
| Fenwick Tree (Binary Indexed Tree – BIT) | Prefix Sum, Inversions Count, Range Queries | O(N) → O(log N) (Query/Update) | O(N) → O(N) | Optimizes prefix sum & range updates with O(log N) time. Simpler than segment trees, used for inversions counting & frequency tables. |
