algorithms

Choosing Algorithms

Constraints reject costs. Structure suggests a method. An invariant justifies it.

Published 2026-04-08 · Updated 2026-10-18

On this page

Find a section

A length bound of 100,000 is useful evidence against a pairwise scan. It does not choose between hashing, sorting, a heap or a sliding window. Those methods maintain different information and solve different questions.

Use the decision tree to produce one or two candidates. Then test the conditions and total cost. Several branches can apply at once: a shortest-path algorithm can use a heap; a board-word search can combine backtracking with a trie.

Start with the requested answer

Write what an answer contains: one value, original indices, a count, an ordered sequence, a shortest route or every valid arrangement. Specify duplicates, ties, empty input and permitted mutation. These are part of the problem, not final implementation details.

Distinguish contiguous subarrays from subsequences. Distinguish source-to-vertex distances from total spanning-tree weight. Distinguish “can reach” from “use every edge.” The same input representation can require different algorithms because the objective changes.

Specify the answer contract.
Write a correct baseline.
Estimate its total cost.
Use input structure to propose a better method.
Prove why the method is correct.
Test the conditions and edge cases.

A small input allows expensive work; it does not require an expensive solution. Return to an earlier step when a proof or counterexample changes the model.

A roadmap organizes study topics. This reader instead organizes the questions needed when an unfamiliar statement arrives. The static sections below contain every decision path, including its failure condition.

Follow a decision path

Choose a family, then an operation. Search matches labels, conditions, counterexamples and costs across all 50 leaves.

Find a decision

Choose the operation that matters. These branches can be combined; return to a parent to investigate another candidate.

Connections: objective before traversal

A state and its legal transitions form a graph even when the statement describes cells, moves or dependencies. A tree supplies additional structure: one parent path and independent child subtrees.

For equal-cost moves, BFS layers give shortest edge counts. Weighted distances require relaxation. Negative cycles affect only reachable destinations whose routes can pass through them; they do not invalidate every pair automatically. Grid right/down counting can use acyclic DP, while a no-revisit word path must keep branch-specific visited state.

A tree with parent–child structure

Need information from children

Postorder DFS. Compute child results before the parent result.

What can break it: Recording a node before its children does not supply their returned heights.

Cost: $O(n)$ for constant work per node; $O(h)$ active stack. Open the mechanism →

Carry information from ancestors

Top-down DFS. Pass the path state; restore shared changes between siblings.

What can break it: One branch must not leave its path sum in a sibling.

Cost: $O(n)$ for constant work per node, excluding copied paths. Open the mechanism →

Need levels or nearest depth

BFS. The tree edges have equal transition cost.

What can break it: A level count is not a weighted path distance.

Cost: $O(n)$ ; queue width can be $O(n)$ . Open the mechanism →

Search or restrict a BST range

BST pruning. The complete subtree ordering contract holds.

What can break it: A binary tree without search ordering cannot discard a subtree by value.

Cost: $O(h)$ lookup; h can be n without balance. Open the mechanism →

Reachability or components

Static graph or grid

DFS/BFS with visited tracking. Future reachability depends on the vertex, not the route used to reach it.

What can break it: A no-revisit word path needs path-specific state, not one global visited set.

Cost: $O(V+E)$ , or $O(RC)$ for a bounded-degree grid. Open the mechanism →

Undirected edges arrive incrementally

Union-Find. The query asks whether endpoints share a component as edges are added.

What can break it: A basic Union-Find does not undo deletions or return shortest paths.

Cost: Near-constant amortized operations with rank/size and path compression. Open the mechanism →

Shortest paths or minimum transitions

All edges have the same nonnegative cost

BFS. Queue layers match the number of edges from the source.

What can break it: Choosing the first discovered weighted route can miss a cheaper indirect path.

Cost: $O(V+E)$ . Open the mechanism →

Weights are only 0 and 1

0–1 BFS. Relax distances; put weight-0 improvements at the front and weight-1 at the back.

What can break it: An ordinary FIFO queue treats zero and one as equal steps.

Cost: $O(V+E)$ under the standard distance/deque implementation. Open the mechanism →

General nonnegative weights

Dijkstra. Finalize the smallest current tentative distance; ignore stale heap entries.

What can break it: First insertion is not finalization. Negative edges invalidate that guarantee.

Cost: Common binary-heap bound $O((V+E)\log V)$ ; account for parallel edges and heap size. Open the mechanism →

Negative weights may occur

DAG relaxation or Bellman–Ford. Acyclic dependencies allow topological relaxation; otherwise account for reachable negative cycles.

What can break it: A reachable negative cycle can make affected shortest distances unbounded.

Cost: DAG $O(V+E)$ ; standard Bellman–Ford $O(VE)$ . Open the mechanism →

Need distances between all pairs

Floyd–Warshall. The vertex count is small enough for a dense distance table and cubic work.

What can break it: A few hundred vertices is a heuristic, not proof of fitting a runtime budget.

Cost: $O(V^3)$ time, $O(V^2)$ space; handle negative cycles. Open the mechanism →

Prerequisites or directed ordering

Topological sort / directed-cycle DFS. A full topological order exists exactly when the directed graph is acyclic.

What can break it: Undirected parent tracking is not a directed-cycle proof.

Cost: $O(V+E)$ . Open the mechanism →

Connect all vertices at minimum total cost

Kruskal or Prim. The objective is an undirected minimum spanning tree, or a forest if disconnected.

What can break it: A shortest-path tree minimizes a different quantity.

Cost: Typically sorting/heap work plus connectivity checks. Open the mechanism →

Use every edge exactly once

Hierholzer traversal. Check degree and connectivity conditions for the directed/undirected case.

What can break it: A greedy walk can get stuck before using all edges; an Euler route is not a Hamiltonian route.

Cost: $O(V+E)$ with efficient edge consumption. Open the mechanism →

Sequences: order and contiguity

Ask which relationship the answer preserves. A complement lookup preserves a previously seen value; a window preserves a contiguous range; a monotonic stack preserves unresolved candidates. None follows merely from the word “array.”

Sorted order makes some eliminations safe. For a pair sum, increasing the left value cannot decrease the sum. For a target boundary, comparison can rule out a half. Those arguments fail if the claimed ordering does not hold.

An alphabet restricted to 26 lowercase English letters permits a fixed frequency array when the caller checks that domain. For sorted triplets, fix one index and scan the remaining pair with two pointers. This adds an outer factor: the usual scan costs O(n²), not the pair scan's O(n). Sorting may add preprocessing and must preserve original indices when requested.

Membership, duplicates, counts or complements

Hash map/set or frequency array. Store exactly the information required; use a manageable alphabet/range for arrays.

What can break it: One stored presence bit cannot answer how many occurrences exist.

Cost: Expected $O(n)$ for bounded-cost hash operations; count key work. Open the mechanism →

A contiguous subarray or substring

Fixed-length sums or counts

Rolling window. Remove the outgoing contribution and add the incoming one.

What can break it: Recomputing each entire window adds a factor equal to window length.

Cost: $O(n)$ for constant-cost updates. Open the mechanism →

Maximum/minimum in every fixed-size window

Monotonic deque. Remove expired indices and dominated candidates; equality policy matches the output.

What can break it: The outgoing maximum cannot generally be recovered from a single running maximum.

Cost: $O(n)$ total push/pop work; $O(k)$ candidates. Open the mechanism →

Variable length with a safe forward boundary

Sliding window. Prove that discarded starts cannot become useful later for the requested objective.

What can break it: [5,−2] sums to 3: shrinking a too-large prefix of 5 loses it.

Cost: Often $O(n)$ , with each boundary moving forward and cheap updates. Open the mechanism →

Exact sum with signed values

Prefix sums + frequency map. For current prefix P, count earlier prefixes equal to P−target.

What can break it: A presence set undercounts repeated prefixes; query before inserting the current prefix.

Cost: Expected $O(n)$ with bounded-cost keys; $O(n)$ map storage. Open the mechanism →

Maximum contiguous sum

Kadane / best-ending DP. Keep the best nonempty sum ending here; define whether the empty segment is allowed.

What can break it: Initializing the answer to zero is wrong for a nonempty all-negative input.

Cost: $O(n)$ time and $O(1)$ state for the value alone. Open the mechanism →

Palindrome segments

Expand around centers or interval DP. Include odd and even centers, or define substring validity by endpoints.

What can break it: A subsequence palindrome may skip characters; a substring cannot.

Cost: Basic center expansion $O(n^2)$ , $O(1)$ extra space for boundaries. Open the mechanism →

A sorted order you can exploit

Locate a value or boundary

Binary search. Each comparison safely excludes one side; bounds shrink.

What can break it: Unsorted values do not support value-based half elimination.

Cost: $O(\log n)$ comparisons, excluding expensive key access. Open the mechanism →

Find a pair or compare opposite ends

Two pointers. Sorted order makes the proposed pointer move exclude only impossible pairs.

What can break it: Sorting values alone loses original indices if the output requires them.

Cost: $O(n)$ pair scan; sorting adds $O(n\log n)$ . Open the mechanism →

Merge ordered sources

Merge pointers / source-head heap. Each source head precedes every remaining item in that source.

What can break it: One unsorted source invalidates the head-frontier proof.

Cost: Two sources $O(N)$ ; K sources $O(K+N\log(\max(2,K)))$ with heapify. Open the mechanism →

Next greater/smaller or blocking boundary

Monotonic stack. Each entry represents an unresolved candidate with a specified strict/non-strict rule.

What can break it: Equal values may or may not resolve one another; decide the tie contract.

Cost: $O(n)$ amortized total stack operations. Open the mechanism →

Rearrange or compact in place

Read/write pointers or partitioning. Preserve the processed-prefix invariant and the permitted mutation policy.

What can break it: Overwriting unread input loses information needed later.

Cost: Often $O(n)$ , $O(1)$ auxiliary state. Open the mechanism →

A subsequence or alignment

Sequence DP; specialized optimizations when justified. A state must describe relevant prefixes or endpoints, not just a contiguous window.

What can break it: Sliding windows cannot freely skip interior values. LIS has a specialized $O(n\log n)$ alternative.

Cost: Count states × transitions; LCS commonly $O(nm)$ . Open the mechanism →

Choices: preserve or compress the future

Enumeration preserves distinct paths. DP merges histories only when their future options and costs agree. Greedy commits a choice only when an exchange or dominance proof makes alternatives unnecessary.

“Minimum,” “maximum” and “number of ways” name outputs, not algorithm families. Minimum hops may be BFS. Maximum compatible interval count may be greedy. A binary search may call a greedy feasibility test. A DP may run on a tree.

Produce all valid answers

Backtracking / enumeration. Each valid answer has a branch; pruning must rule out every completion.

What can break it: Caching only a boolean can lose distinct answers reached through different prefixes.

Cost: Include output size: materialized subsets $\Theta(n\,2^n)$ , permutations $\Omega(n\,n!)$ . Open the mechanism →

A proven safe local choice exists

Greedy. An exchange, dominance or stay-ahead argument justifies commitment.

What can break it: Coins [1,4,5], target 8: largest-first uses 4 coins, but 4+4 uses 2.

Cost: Cost of ordering plus the scan/state updates; fitting does not prove correctness. Open the mechanism →

Different histories have the same future

One index or remaining amount

1-D DP / memoization. The state contains everything needed for future legality and cost.

What can break it: A remaining amount is insufficient if earlier choices change which items remain.

Cost: Reachable states × transitions; $O(nS)$ for standard nonnegative target DP. Open the mechanism →

Two prefixes or index plus capacity

2-D DP. Specify both coordinates, bases and dependency order.

What can break it: Rolling storage does not turn a logically 2-D recurrence into 1-D state.

Cost: Often $O(nm)$ or $O(nS)$ ; compression may reduce retained memory. Open the mechanism →

The selected subset changes future moves

Bitmask DP. The universe is small; the mask and other state describe the future.

What can break it: Mask states can need n transitions each: 2ⁿ states does not imply 2ⁿ work.

Cost: Often $O(n\,2^n)$ , sometimes with another state dimension. Open the mechanism →

Can test a monotone candidate answer

Binary search on the answer. Prove one truth-value transition and valid answer bounds; supply a correct checker.

What can break it: A faster speed helps a deadline, but arbitrary optimization scores need not be monotone.

Cost: $O(C\log U)$ , with checker cost C and finite answer range U. Open the mechanism →

No useful state compression; choices split independently

Backtracking / meet-in-the-middle. Half summaries must combine to the requested answer without retaining incompatible histories.

What can break it: At n=40, $2^{40}$ is huge, but two sets of $2^{20}$ sums may be workable.

Cost: Typically $O(n\,2^{n/2})$ with sorting and $O(2^{n/2})$ space for subset sum. Open the mechanism →

Operations: choose the maintained state

Choose a data structure by the repeated operation that would otherwise be expensive. A heap maintains the current extreme, not full order. A trie shares prefix work, not arbitrary substring lookup. A stack preserves pending last-in-first-out work.

Intervals make this distinction concrete. Sort starts to merge coverage. Sort finishes to maximize an unweighted compatible count. Track active endpoints to count simultaneous demand. Weighted rewards change the objective and usually require a different recurrence.

Repeated extreme/rank operations

Values arrive or leave; need next extreme

Heap / priority queue. The root exposes the best currently active candidate; invalid entries must be discarded.

What can break it: A heap array is not globally sorted and arbitrary deletion is not cheap by itself.

Cost: Peek $O(1)$ ; push/pop $O(\log n)$ ; heapify $O(n)$ . Open the mechanism →

One static kth element or top k

Quickselect, bounded heap or sorting. Clarify duplicate ranks, requested ordering and input mutation.

What can break it: Returning a heap does not return a sorted top-k list.

Cost: Selection expected $O(n)$ , worst $O(n^2)$ for simple pivots; heap $O(n\log(\max(2,k)))$ . Open the mechanism →

Running median after each insertion

Two heaps. Keep ordered halves and balanced sizes; query only after repair.

What can break it: Size balance alone does not ensure the lower half lies below the upper half.

Cost: Insert $O(\log n)$ , query $O(1)$ , storage $O(n)$ . Open the mechanism →

Resolve the most recently opened item

Stack. The top holds the last unresolved nested operation.

What can break it: A queue reverses the required bracket/return order.

Cost: Usually $O(n)$ with constant-cost entry processing. Open the mechanism →

Overlapping intervals or timeline events

Merge covered regions

Sort by start then scan. The last merged endpoint summarizes the current coverage frontier.

What can break it: Touching intervals depend on closed/half-open and coalescing policy.

Cost: $O(n\log n)$ unless already sorted. Open the mechanism →

Maximize count of compatible intervals

Earliest-finish greedy. Rewards are equal and compatibility has a consistent endpoint rule.

What can break it: Weighted rewards invalidate the maximum-count exchange objective.

Cost: $O(n\log n)$ sorting plus $O(n)$ scan. Open the mechanism →

Count simultaneous resources

Sweep line / end-time heap. Track active events and process tied endpoints in the specified order.

What can break it: Counting allocated rooms is not the same heap invariant as storing active meetings.

Cost: Typically $O(n\log n)$ . Open the mechanism →

Repeated dictionary searches

Exact whole-word membership

Hash set. Only full-key membership is required; account for key length.

What can break it: A trie is unnecessary merely because the keys are strings.

Cost: Expected lookup plus hash/equality work. Open the mechanism →

Prefixes or shared character branching

Trie. Queries exploit shared prefixes or prune absent character branches.

What can break it: A reachable prefix is not necessarily a stored complete word.

Cost: $O(L)$ query steps; node storage can be significant. Open the mechanism →

Manipulate linked nodes

Saved-next rewiring / fast–slow / offset pointers. Choose the operation: middle/cycle, kth from end, reversal or merging.

What can break it: Equal values do not prove node identity; rewiring before saving next can lose a suffix.

Cost: Often $O(n)$ ; live pointer state can be $O(1)$ . Open the mechanism →

Many range aggregates, possibly with updates

Prefix sums / Fenwick tree / segment tree. Static sums use prefixes; updates need a structure supporting the required aggregate.

What can break it: Prefix subtraction is not a general range-minimum operation.

Cost: Static O(n+q); common update/query structures $O(\log n)$ each. Open the mechanism →

Mathematics: use a real invariant

Arithmetic shortcuts need an input contract too. Pair cancellation uses exact multiplicities. A coordinate transform needs its origin and orientation. A repeated process needs a sufficient state before cycle detection is valid.

Pairs cancel with one unpaired integer

XOR. All other occurrences appear twice under the stated integer representation.

What can break it: Arbitrary multiplicities do not satisfy pair cancellation.

Cost: $O(n)$ fixed-width word operations, $O(1)$ accumulator. Open the mechanism →

Small universe, flags or powers of two

Bitmasks / bit operations. Define width, sign and whether each bit encodes a membership or count.

What can break it: A boolean mask loses multiplicity; arbitrary-precision integer work grows with width.

Cost: Depends on mask width and number of states. Open the mechanism →

Divisibility or repeated remainders

GCD / modular arithmetic. The arithmetic invariant must match the question and signed remainder convention.

What can break it: Modulo reduction is not ordinary division and cannot always be inverted.

Cost: Count operand bits and arithmetic operations. Open the mechanism →

Coordinates, rotations or matrix traversal

Geometry / simulation. Write the coordinate transform and movement boundary contract.

What can break it: Rotation order, origin and integer overflow can change the answer.

Cost: Count cells, points or steps, not just one dimension. Open the mechanism →

Huge number of repeated transitions

Formula / cycle detection / fast composition. The next state is determined and repeated states or composable operations can be identified.

What can break it: A large step count alone does not create a periodic state sequence.

Cost: Depends on state-space size or logarithmic composition depth. Open the mechanism →

Estimate the baseline work

Describe a correct straightforward solution before improving it. Count the operation repeated most often, then substitute the maximum input sizes. Do not multiply loop bounds blindly: a pointer or stack entry can be processed only a constant number of times despite nested syntax.

At n=100,000, growth separates candidate costs
Growth expression	Count
n	100,000
$n\log_2 n$	Approximately 1.66 million
$n^2$	10 billion
$n^3$	1 quadrillion

Big-O gives an asymptotic upper bound. It is not a measured duration and does not identify the constant factor. State whether a bound is worst-case, expected or amortized. Expected hashing depends on key distribution, load management and hash/equality cost; it is not an unconditional worst-case constant guarantee.

Cost models and input-dependent guarantees ↗ · Hashing assumptions and key work ↗

Cost one operation, then count repetitions

A data structure accelerates a specific operation
Structure / operation	Cost	Condition
Binary heap: inspect the root	$O(1)$	Existing nonempty heap; min or max depends on direction
Binary heap: insert or remove the root	$O(\log n)$	Worst-case repair path; bounded-cost comparison
Binary heap: build from an array	$O(n)$	Bottom-up heapify, not repeated insertion
Hash table: membership / insert / remove	Expected amortized $O(1)$	Suitable hashing/load policy and bounded-cost keys; not universal worst case

Here n is the number of stored entries. Multiplying a per-operation cost by the number of operations gives a whole-task estimate. Hashing a long string adds key work. A balanced binary heap is partially ordered; its array is not a sorted sequence. Heap invariant →

Change n without predicting wall-clock time

Integer n ranges from 1 to 1,000,000; q ranges from 0 to 1,000,000. Counts use exact integer arithmetic where the expression is integer-valued.

Input length nQuery count q

Different models of work; not comparable CPU instruction counts
Expression	Count	Meaning
n	100,000	One pass over explicit input
$n\log_2 n$	≈ 1,660,964	Growth model, not an exact comparison count
$\frac{n(n-1)}{2}$	4,999,950,000	All unordered distinct-index pairs
$n^3$	1,000,000,000,000,000	One unit for each ordered triple
nq	10,000,000,000	Scan n values for each of q queries
n+q	200,000	Growth model for static prefix preprocessing + queries

The table scrolls horizontally on narrow screens. Focus it to scroll with arrow keys.

An n×n table has 10,000,000,000 cells. At 8 bytes per cell, raw values alone use 80,000,000,000 bytes (≈ 80 decimal GB). Headers, references and other objects are excluded.

No result is marked “passes.” Hardware, operation cost, language, input/output and memory limits remain external to this model. For q=0, building a prefix table may be unnecessary.

Use bounds to form hypotheses

Study heuristics, not judge-specific pass thresholds
Maximum size	Candidate work	What to investigate
About 8–10	n!	Permutation enumeration; include output copying
About 20	2ⁿ or n·2ⁿ	Subsets, small-universe bitmask state
About 40	$2^{n/2}$ with combination factors	Meet-in-the-middle if the choices split
About 100–300	n³ may fit	Interval DP, all-pairs distances
About 1,000–3,000	n² may fit	Pairs, quadratic DP
About 100,000	Usually n log n or n	Sorting, heaps, hashing, pointers
About 1,000,000	Prefer near-linear work	Scans, counting, prefix summaries; sorting may still fit

These approximate ranges generate candidates. They are not universal runtime budgets. $20\cdot2^{20}$ is 20,971,520 state-transition-scale operations, and objects for all states can dominate memory. A simple linear method remains preferable when it is also correct on ten values.

A scalar as large as $10^{18}$ may support logarithmic answer search or arithmetic. An explicit n-element input still needs Ω(n) inspection when every element can affect the answer. Numeric magnitude and amount of input are different variables. Constraint heuristics and constant-factor caveats ↗

Replace repeated work, not the objective

For two distinct indices whose values sum to a target, brute force checks each unordered pair once. At n=100,000, this is 4,999,950,000 checks. The size bound rejects that cost, but does not supply a faster algorithm.

\binom{n}{2}=\frac{n(n-1)}{2}=4{,}999{,}950{,}000

n=100,000 indexed values. The general pair formula holds for nonnegative integer n; pairs use distinct indices and order does not matter.

The relationship supplies the improvement: for value x, only target−x can be its partner. Store previously seen values and look up that complement before inserting x. Lookup-before-insertion prevents reusing the current index. Expected time becomes O(n), with O(n) extra state under bounded-cost hashing.

def two_sum(nums, target):
    seen = {}
    for i, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return [seen[complement], i]
        seen[value] = i
    return None

This callable function accepts integer values and an integer target. It does not mutate the input. It returns one valid index pair, or None when none exists. Repeated values replace their earlier stored index; any returned pair still contains distinct indices. It does not enumerate all pairs.

Sorting plus two pointers is another valid candidate. Preserve original indices if the output needs them; sorting adds work and may mutate caller data. Already sorted input supports a direct O(n) pair scan. The complement trace → and sorted-pair trace → expose the distinct invariants.

Subset sum has several size variables

Suppose each value can be selected once, and ask whether some subset totals S. Three regimes illustrate why length alone is insufficient.

One objective, different representations
Regime	Method	Work/storage condition
About n=20	Enumerate subsets	$2^{20}=1{,}048{,}576$ leaves; carry the sum instead of rebuilding it
About n=40	Split, enumerate half sums, find complements	$2^{40}=1{,}099{,}511{,}627{,}776$ full subsets; two halves have $2^{20}$ sums each
Many values, small nonnegative integer S	Reachable-sum DP	O(nS) time and O(S) rolling storage, with descending updates for one-use items

Meet-in-the-middle combines a left sum a with right sum S−a. Generating half sums recursively takes work proportional to their number. Sorting one list and searching for each complement introduces logarithmic factors, giving the typical $O(n\,2^{n/2})$ time bound and $O(2^{n/2})$ storage.

The O(nS) method is pseudo-polynomial: its cost depends on the numeric value S, not only the $O(1+\log(S+1))$ bits needed to encode nonnegative S. Nonnegative values permit discarding sums above a nonnegative target; signed values require a different reachable range or representation. The item-reuse trace → shows why update direction changes the problem.

A lost prefix can become valid later

For nonnegative values, adding an element cannot decrease a window sum, and removing its left element cannot increase it. This supports some forward-only boundary rules. It does not prove every sum problem is a window problem.

For target 3, [5,−2] is valid even though the first prefix is 5. Removing 5 immediately because it exceeds the target loses the later answer. Prefix sums avoid that assumption: a subarray totals target exactly when an earlier prefix equals current prefix minus target.


def count_exact_sum(values, target):
    frequency = {0: 1}
    prefix = answer = 0
    for value in values:
        prefix += value
        answer += frequency.get(prefix - target, 0)
        frequency[prefix] = frequency.get(prefix, 0) + 1
    return answer

The function accepts integers, counts nonempty subarrays, and leaves the input unchanged. Empty input returns zero. Query before inserting the current prefix so it cannot match itself as an empty subarray. Counts, rather than presence alone, preserve repeated prefixes. For [0,0] and target 0, three nonempty subarrays match; the empty prefix initializes the map but is not an extra answer. For no-repeat substrings, counts supply another monotone validity rule; watch its boundary repair →.

Count dimensions, queries and representation

The hidden quantity can change feasibility
Quantity	Account for it
Grid	R·C cells, not just rows
Graph	V vertices and E edges; sparse versus dense representation
Strings	Hashing/comparison can inspect L characters
DP	Reachable states × transitions, plus reconstruction/output
Queries	Preprocessing + q query costs + update costs
Test cases	Use a stated total-length bound when available
Memory	Cells × bytes plus container/object/reference overhead

For n=q=100,000 static range-sum queries, scanning each range can cost O(nq). Prefix construction and subtraction queries reduce the growth model to O(n+q). Point updates invalidate a static prefix snapshot; Fenwick or segment trees support relevant aggregates with logarithmic operations.

At $n=100{,}000$ , an $n^2$ table has ten billion cells: about 10 decimal GB even at one byte per cell. Ordinary Python containers can require much more. Rolling rows may reduce a DP table from O(nm) to O(m), but only when dependencies permit overwriting. Reconstructing an actual solution may need extra history.

Known data does not by itself guarantee a linear heap build: bottom-up heapify does. Inserting all known values separately still costs O(n log n) in the worst case. Heap construction → owns the proof.

Ask what a step is allowed to discard

A feasible cost is not a correctness argument
Candidate	Necessary argument
Binary search	A comparison/predicate safely removes a half and the interval shrinks
Window	Discarded starts cannot become better candidates later
DP	Equal states have equal future options/costs; recurrence and base are correct
Greedy	The local commitment can replace an optimum choice without worsening it
Backtracking	Every valid answer has a branch; every prune excludes only impossible completions
Heap frontier	The root is best among the candidates that correctly represent remaining work

Coins [1,4,5] and target 8 break largest-first coin count: 5+1+1+1 needs four coins, while 4+4 needs two. Large search spaces may motivate heuristics, but do not convert them into exact solvers. Greedy counterexamples and proof conditions ↗

A shortest grid route uses global discovery state; a board-word path uses branch-local occupied cells and can prune through a trie. An acyclic prerequisite order uses directed cycle/dependency state. A warmer later value resolves a pending smaller value in a monotonic stack. A larger feasible speed supports answer search. These are invariant examples, not separate exercise pages.

Turn the candidate into a tested contract

Name the answer and size variables, including target, queries, value range and total test-case size.
Describe a correct baseline and count its repeated work.
Reject time or memory costs that conflict with the actual limits.
Identify a structural property and one or two candidate methods.
State the invariant, recurrence or exchange argument before coding.
Account for setup, key work, output, mutation and reconstruction.
Compare tiny cases with brute force; test the assumption most likely to fail.

Keep a brief record after solving: clue, maintained state, proof condition and why the tempting alternative fails. This is more reusable than memorizing an exercise title or associating one keyword with one algorithm.

Test empty/singleton input, equal keys, signed values, ties, repeated queries, stale state and repeated calls. A method passing samples is evidence, not a proof. If no candidate is valid, revisit the state and objective instead of selecting the cheapest-looking leaf.

Sources and related mechanisms

NeetCode roadmap ↗ · External algorithm-selection aid ↗ · Algorithm analysis ↗ · Constraint estimates ↗

The decision aid is an original synthesis of the local notes, not a reproduction of the external chart. It supplies conditions and counterexamples, not a universal classifier.

Sorting execution → · Traversal frontiers → · Complement lookup →