DSA Workbook

Converging or parallel pointers scan arrays and strings in linear time, replacing nested O(n²) loops with single O(n) sweeps. Most useful when the data is sorted or has a symmetric structure (palindromes, pair sums).

Floyd's tortoise-and-hare. Speed-2 vs speed-1 pointers detect cycles, find midpoints, and solve linked-list-as-functional-graph problems in O(1) extra space. The atomic cycle-detection primitive.

Maintain a contiguous window over an array or string, expanding and shrinking to preserve an invariant. Powers most 'longest / shortest / count substring with property X' problems, often turning O(n²) brute force into O(n).

Sort intervals by start, then sweep linearly. Merge, intersect, count overlaps, and detect meeting-room collisions all fall out of a single linear pass. A min-heap of end times adds resource-allocation flavors on top.

Reverse, reorder, rotate, and partition linked lists by rewiring `next` pointers — O(1) space. Building blocks: dummy head, three-pointer reversal, head-insertion within a sublist, and the split-reverse-weave composition.

Priority queues answer 'what's the smallest or largest right now?'. Use bounded heaps for top-k, dual heaps for running medians, and lazy deletion for sliding-window extrema.

Merge k sorted streams via a min-heap of frontiers — one entry per stream. The foundation for kth-smallest across multiple sources, sorted-matrix queries, and external sorting.

Bounded heap of size k: min-heap for top-k-largest, max-heap for top-k-smallest. When one-shot O(n) average is acceptable, quickselect partitions around a pivot instead.

Binary search beyond plain sorted arrays: rotated, bitonic, peaked, on the answer value, or on a real-valued range. The only requirement is a monotone predicate.

DFS enumeration of subsets, permutations, and combinations. Start-index for combinations; in-place swap for permutations; sort-and-skip for dedup on duplicate inputs.

Take the locally-best move and prove (via exchange argument or matroid) that it leads to a globally optimal solution. Sorts, heaps, and running aggregates are the usual scaffolding.

Recursive search with pruning. Build candidate solutions incrementally and abort branches that violate constraints early. Bitmasks compress constraint state when feasible.

Express the answer as overlapping subproblems with optimal substructure; cache results. Flavors range from 1D rolling DP through 2D knapsack, interval DP, state machines, and bitmask DP.

Place value `v` at index `v - 1` via in-place swaps. The canonical O(n) / O(1) primitive for missing-or-duplicate problems on arrays containing the integers `[1, n]`.

Linear ordering of a DAG respecting dependencies. Kahn's BFS for indegree-based ordering; DFS post-order for the reverse. Cycle detection comes for free.

Sorting exposes structure that a linear or binary-search sweep can then exploit. The most versatile 'preprocess then query' pattern — applies whenever pairs, ranges, or extremes matter.

Treat the 2D grid as the data structure. In-place markers, layer-by-layer iteration, spiral traversal, transpose-then-reverse rotation, prefix sums, and staircase walks.

LIFO order captures 'last-seen-first-out' semantics. Monotonic stacks find next-greater or next-smaller in O(n); expression evaluation and nested-structure validation are direct applications.

Encode relations as edges. BFS for shortest unweighted paths, DFS for connectivity and topological order, Dijkstra / Bellman-Ford for weighted shortest paths, A* when a heuristic is available.

Recursive depth-first traversal. Pre / in / post-order, path-sum aggregation, LCA, height, diameter, serialization, BST validation — most tree questions reduce to a single DFS with carefully chosen return values.

Level-order traversal via a queue. Right-side view, zigzag, per-level aggregation, connecting next-right pointers, and shortest path in unweighted trees.

Prefix tree for word lookups, autocomplete, prefix counting, and word-search-in-grid. Each node has up to |Σ| children; operations are O(L) in the word length.

Constant-time keyed lookup. Frequency counting, complement search, anagram grouping, two-sum, and running aggregations keyed by computed signatures — the most reused primitive in the entire toolkit.

Run a rolling aggregation (sum, count, last-seen index) over a stream and test it against a target. A cousin of hash maps that emphasizes mutable state over time.

Disjoint-set forest with path compression and union by rank. Maintain connected components dynamically as edges arrive in near-O(1) per op (inverse Ackermann).

Compose primitives — hash + linked list, twin heaps, segment trees, balanced BSTs — to satisfy an unusual operation spec in optimal time. LRU, LFU, time-keyed stores, snapshot arrays.

Each bit is a flag or part of an integer encoding. XOR cancels pairs, AND masks, popcount counts set bits. Subset masks, parity tricks, position toggles, and arithmetic without operators.

Number theory (GCD, modular arithmetic, primes), big-number arithmetic on strings, coordinate geometry, area and orientation tests, and modular exponentiation.

A grab-bag of foundational problems that appear in interviews regardless of pattern. Two Sum, Maximum Subarray, Trapping Rain Water — the canonical warm-ups.