Data structures & algorithms

01Arrays and linear scans

Summarize a sequence while preserving positions and tie rules.

Baseline

Sort to find an extreme, or make separate passes for each summary.

Improvement

A linear scan keeps only the running total and first maximum position. Constantly many separate scans are already O(n); one pass also supports streams.

Cost: O(n) time; O(1) extra space. Sorting adds O(n log n) work.

02Strings and frequency maps

Compare required and available multiplicities, not just membership.

Baseline

Rescan the input for every requested symbol: quadratic work in the worst case.

Improvement

Frequency maps count each input once, then subtract counts to report shortages.

Cost: Expected O(n + m) counting time; sorting d output keys adds O(d log d).

04Prefix sums

Answer many range-sum queries over unchanged data.

Baseline

Sum every queried range independently: O(nq) for q queries.

Improvement

Prefix sums store cumulative totals. Each range becomes a subtraction of two boundaries.

Cost: O(n) preprocessing and space; O(1) per query, O(n + q) overall.

05Sliding windows with counts

Find the longest contiguous range under a distinct-value limit.

Baseline

Try every start/end pair and recount values: quadratic work or worse.

Improvement

A sliding window and frequency map expand the right boundary and shrink the left only when the limit is exceeded.

Cost: Expected O(n) time: each position enters and leaves the window once.

06Sorting and two pointers

Find a pair meeting a target without testing every pair.

Baseline

Enumerate pairs from distinct positions: O(n²).

Improvement

Sort a copy, then move inward pointers. Sorted order proves which endpoint cannot participate in a remaining solution.

Cost: O(n log n) including sorting; O(n) scan if already sorted. Hashing is an alternative when its tradeoffs fit.

07Binary search on the answer

Find the smallest capacity or rate that makes a workload feasible.

Baseline

Test every candidate value, rerunning the feasibility scan each time.

Improvement

Binary search the answer: a monotone feasibility predicate eliminates half the candidate range at each step.

Cost: O(n log R) time for an answer range of R integers; the shipping check uses O(1) extra space.

09Stacks and nested operations

Validate nested operations and last-in-first-out histories.

Baseline

Repeatedly search or remove matching operations: up to O(n²).

Improvement

A stack retains unmatched work. Each operation is pushed and popped at most once.

Cost: O(n) time; O(n) worst-case stack space.

03KMP string search

Find exact substring matches, including overlaps.

Use case: Exact matching in repetitive text or a stream where rewinding is expensive.

Baseline

Try each starting position and repeat comparisons: O(nm).

Improvement

KMP stores matched prefix/suffix lengths so a mismatch reuses progress instead of restarting.

Cost: O(n + m) time; O(m) auxiliary space, excluding matches.

08Linked lists and node identity

Remove linked nodes while preserving surviving object identities.

Use case: In-memory work queues where other components retain references to pending jobs.

Baseline

Rebuild nodes from filtered values, or linearly rescan b blocked values for each node.

Improvement

Use a sentinel and predecessor to relink survivors. A hash set answers blocked-value membership without repeated scans.

Cost: Expected O(n + b) time; O(b) set storage and O(1) pointer state. Finding a node is still linear.

10Monotonic deques

Find an extreme in every fixed-size sliding window.

Use case: Rolling peaks or troughs in telemetry and time-series monitoring.

Baseline

Rescan each window of k elements: O(nk).

Improvement

A monotonic deque drops expired indices and candidates dominated by a newer value.

Cost: O(n) total time; O(k) space. Each index is inserted and removed at most once.

11Heaps and k-way merge

Merge k sorted inputs while retaining only their current heads.

Use case: Merge chronological logs, sorted result streams, or external-sort runs.

Baseline

Scan all k heads to choose each of N output values: O(Nk).

Improvement

A min-heap stores one head per active input; replacing the extracted head keeps the next choice cheap.

Cost: O(k + N log(k + 1)) time; O(k) frontier space, excluding output.

12Greedy interval scheduling

Choose the maximum number of non-overlapping intervals.

Use case: Select the most jobs or reservations when each accepted interval has equal value.

Baseline

Enumerate compatible subsets: exponential search.

Improvement

Greedy scheduling sorts by finish time and takes the next compatible interval. An exchange argument justifies the choice.

Cost: O(n log n) time; O(n) scan after sorting. Weighted rewards need a different algorithm.

13Dynamic programming: minimum coins

Reach an amount with the fewest coins when greedy choices can fail.

Use case: Exact denomination or fixed-size bundle composition when largest-first is not valid.

Baseline

Recursively try coin sequences, repeatedly solving the same remaining amounts.

Improvement

Dynamic programming stores the minimum for each amount and extends it with one coin.

Cost: O(Ac) time and O(A) space for amount A and c denominations; pseudo-polynomial in A.

140/1 knapsack

Maximize value under a budget, choosing each item at most once.

Use case: Select indivisible features, purchases, or workloads under one resource budget.

Baseline

Enumerate all item subsets: O(2^n) candidate subsets.

Improvement

0/1 knapsack DP reuses item/budget states. Descending budget updates prevent reusing the current item.

Cost: O(nW) time and O(W) space for budget W; pseudo-polynomial, not polynomial in its bit length.

15Edit distance

Find the minimum insertions, deletions, and substitutions between strings.

Use case: Typo similarity and approximate matching under a defined unit-edit model.

Baseline

Branch recursively on possible edits without caching; prefix pairs recur exponentially.

Improvement

Edit-distance DP solves each prefix pair once. Two rows suffice when only the distance is required.

Cost: O(nm) time; O(min(n, m)) auxiliary space for distance alone.

16Backtracking and pruning

Explore assignments subject to constraints, undoing invalid choices.

Use case: Constraint search such as placements and small scheduling instances.

Baseline

Generate complete assignments, then validate them.

Improvement

Backtracking rejects invalid partial states immediately. Column and diagonal sets prune N-Queens placements before completion.

Cost: Still exponential in the worst case; pruning reduces explored states, not the complexity class.

17Binary trees and level-order traversal

Visit a binary tree one depth level at a time.

Use case: Level-wise inspection or visualization of hierarchical data.

Baseline

Traverse again for every depth: O(nh) for tree height h in the worst case.

Improvement

Breadth-first traversal uses a FIFO queue; process the current queue length to separate levels.

Cost: O(n) time; O(w) frontier space for maximum width w, excluding output.

18Binary search trees

Maintain ordered keys with insertion, deletion, and predecessor queries.

Use case: Ordered lookup such as the greatest available key not exceeding a requested value.

Baseline

Scan an unsorted collection for each lookup or floor query: O(n).

Improvement

A BST follows key comparisons to discard one subtree at each step; deletion preserves the ordering invariant.

Cost: O(h) per operation. Balanced height gives O(log n); an unbalanced tree can degrade to O(n).

19Tries and prefix search

Find dictionary completions for an exact prefix.

Use case: Autocomplete and repeated prefix lookup over a relatively stable dictionary.

Baseline

Filter every word and sort matching results on each query.

Improvement

A trie shares character prefixes. Walk the prefix once, then enumerate only the matching subtree.

Cost: Expected O(n + T) construction for n words and T input characters; O(p) prefix lookup. Enumeration and ordering cost extra; one query may not justify building the index.

20Graphs and breadth-first search

Find shortest hop counts when every edge has equal cost.

Use case: Fewest-hop navigation, degrees of separation, and equal-cost state transitions.

Baseline

Enumerate simple paths and retain the shortest; path counts can grow factorially.

Improvement

BFS discovers vertices in distance layers. Mark on enqueue so each vertex enters the frontier once.

Cost: O(V + E) time and representation space. Unequal edge costs need a different method.

21Topological sorting

Order directed dependencies and detect cycles.

Use case: Build dependencies, prerequisite plans, and startup ordering.

Baseline

Test vertex permutations for a valid ordering: factorial candidate orders.

Improvement

Kahn’s algorithm tracks indegrees and emits currently legal vertices. A min-heap chooses the smallest legal vertex when that order is required.

Cost: O(V + E) with a queue; O(E + V log V) for the current smallest-first contract.

22Dijkstra shortest paths

Find source distances with nonnegative, unequal edge costs.

Use case: Least-cost routing over nonnegative travel times or transmission costs.

Baseline

Enumerate paths, or repeatedly scan all unsettled vertices to find the next minimum.

Improvement

Dijkstra uses a min-heap frontier. Ignore stale entries and relax outgoing edges from the cheapest current distance.

Cost: O(V + E log(E + 1)) with a lazy heap; supports parallel edges. Negative edges invalidate the settling argument.

23Bellman–Ford shortest paths

Handle negative edges and detect cycles that make costs unbounded.

Use case: Validate relative timing constraints in a schedule; a negative cycle signals incompatible limits.

Baseline

Enumerate simple paths and inspect reachable cycles separately.

Improvement

Bellman–Ford relaxes every edge for at most V−1 rounds, then checks for a further reachable improvement.

Cost: O(VE) time; O(V) distance state. The local exercise rejects source-reachable negative cycles.

24Floyd–Warshall all-pairs shortest paths

Compute shortest-path costs between every pair of vertices.

Use case: Precomputed distance matrices for many queries over a small fixed network.

Baseline

Run Bellman–Ford from every source: O(V²E).

Improvement

Floyd–Warshall reuses subpaths while allowing one more intermediate vertex at each stage.

Cost: O(V³) time; O(V²) space. Suits modest or dense graphs; sparse nonnegative graphs can favor repeated Dijkstra.

25Kruskal and disjoint sets

Connect every vertex at minimum total edge cost without cycles.

Use case: Minimum-cost connection planning and incremental component tracking.

Baseline

Sort edges, then traverse the accepted graph for every cycle check: up to O(EV) traversal work.

Improvement

Kruskal replaces repeated traversals with disjoint sets. Path compression and union by size/rank make connectivity checks cheap.

Cost: O(V + E log(E + 1)) overall, dominated by sorting; near-constant amortized DSU operations.

26Prim minimum spanning trees

Find an MST when connection costs are supplied as a dense matrix.

Use case: Connection planning when pairwise costs are already available or cheap to compute.

Baseline

Materialize all matrix edges and sort them: O(V² log V).

Improvement

Dense Prim keeps the cheapest edge from the growing tree to each remaining vertex; scan and update the frontier directly.

Cost: O(V²) time; O(V) extra space beyond the input matrix. An MST is not a shortest-path tree.

27Fenwick trees

Mix point additions with repeated range-sum queries.

Use case: Mutable counters, frequency tables, and cumulative activity totals.

Baseline

Scan each range, or rebuild static prefix totals after changes: O(n) for one of the two operations.

Improvement

A Fenwick tree stores overlapping binary-sized sum blocks. Updates and prefix queries touch only logarithmically many cells.

Cost: O(log n) per update/query; O(n) space. A straightforward repeated-add build costs O(n log n).

28Segment trees

Mix point replacements with range-minimum queries.

Use case: Live interval summaries such as minimum capacity or temperature over changing measurements.

Baseline

Scan each queried range: O(n). Prefix-sum subtraction does not recover a range minimum.

Improvement

A segment tree stores mergeable interval summaries. A changed leaf repairs only its ancestors; queries combine covering intervals.

Cost: O(n) build and space; O(log n) per point update or range query.