Data Structures & Algorithms curriculum

Constant cost regardless of index is the property every array-backed structure is built on, and it is why a list of lists is slower than a flat array with computed offsets: the second one is still arithmetic, the first is a pointer chase.

The loop that reads one past the end and the loop that skips the last element come from the same confusion. Write the bound as a half-open range, start inclusive and end exclusive, and the count is the difference with nothing to adjust.

The distinction decides whether a refactor matters: pulling work out of an inner loop changes the class, running it afterwards does not. Count the deepest nesting over the same n and the exponent falls out.

Run it on unsorted input and it does not error, it returns a confident wrong answer. That silence is why sortedness has to be an invariant someone owns, not a property the caller remembers to arrange.

The bug needs an array past half the integer range to appear, so it survives every small test and then wraps to a negative index in production. The subtraction form costs nothing and cannot overflow for any valid pair.

Picking the wrong one is the commonest binary-search bug after the loop bound, because all three compile and all three return a plausible index. Decide what the answer means before writing the comparison.

A base case that is unreachable rather than missing fails the same way, which is the subtler version: a recursion that decrements by two will step over an odd base case forever. Prove the argument strictly approaches it.

Depth is the cost, not the number of calls, so a linear recursion over a million items overflows where a loop would not. Tail-shaped recursion only helps in a language that eliminates the frame, and most do not.

Most-recent-first is the right order whenever work nests: the matching bracket, the enclosing scope, the previous page. Where arrival order matters instead, this is the wrong structure and a queue is the one to reach for.

Arrival order is a fairness property, so a queue is what makes a worker pool starve nobody. The implementation detail that bites is a naive array queue, where dequeueing from the front shifts everything unless the head index moves instead.

Generalizing both gives one structure for sliding windows, undo-redo and work stealing. The cost is that it supports operations a caller may not want: exposing a deque where a queue is meant permits a push at the wrong end.

The structure is the references, so there is no block of memory to index into and nothing to resize. That is the whole trade: insertion is cheap because nothing moves, and lookup is expensive for the same reason.

Nothing shifts because nothing is adjacent in memory, so the cost is one allocation and two assignments whatever the list's length. This is the operation linked lists exist for; almost every other one is worse than an array's.

The move is linear even though the insert is one write, so building a list by repeated front-insertion into an array is quadratic. Append instead and reverse once, or choose a structure whose insert does not shift.

Indexing is a walk, so a loop that reads the kth element for each k is quadratic rather than linear — the classic accidental blow-up when an array is swapped for a list. Iterate with the cursor the structure gives you.

Deletion given a node is the operation that buys the extra pointer, and it is what makes an LRU cache work: a hash map hands you the node and the removal is local. Without a back pointer that removal is a scan from the head.

Any constant growth factor above one gives amortized constant appends; growing by a fixed number of slots does not. The factor trades wasted space against copy frequency, which is why implementations pick between 1.5 and 2.

Scaling is the part that survives a faster machine, which is why the class is the thing to reason about during design. The constant still decides which of two same-class implementations to ship, and only measurement settles that.

Using O where Θ is meant makes a claim weaker than intended and sometimes vacuous: every terminating algorithm is O of something enormous. Say Θ when the bound is tight, and say which case you mean.

The crossover is a real number, not a theoretical one, which is why library sorts switch to insertion sort on small runs. Memory behavior is the most often forgotten term: a cache-friendly quadratic pass can beat a pointer-chasing linear one.

The gaps matter more than the names. Between linear and quadratic lies the difference between a job finishing and a job being abandoned at scale, and between quadratic and exponential lies the difference between slow and impossible.

Inside the notation the base is absorbed, which is why a binary and a four-way search are the same class. It does matter when you are counting actual probes or levels, and that is where dropping the base causes a wrong estimate.

The worst case is the only one a caller can rely on, so it is what a contract should state. The average case needs a stated input distribution to mean anything, and the best case is almost never useful outside adaptivity claims.

Counting the input would make every algorithm at least linear, so the useful measure is the extra. In place is a strong claim: a recursion holding log n frames is not O(1) extra, however little it allocates on the heap.

Summing per level is what turns a recurrence into a class without any theorem: draw the work at each depth and see whether the levels are equal, geometric upward, or geometric downward. Those three shapes cover most recurrences you will meet.

The comparison is the whole method: whichever of the split work and the combine work dominates sets the answer, and when they match a log factor appears. It does not apply when the subproblems are unequal or the combine cost is irregular.

An amortized bound holds for every sequence, including an adversarial one; an average-case bound holds only under an input distribution. So amortized is a guarantee you can build on and average-case is a statistical claim that needs its assumption stated.

Bounding the whole sequence first is the simplest of the three because it needs no bookkeeping — just a total. It works when the expensive operations are easy to count, and stops working when their frequency depends on the state.

Assigning each operation a charge above its real cost makes the argument local: show the credit never goes negative and the bound follows. The skill is choosing the charge, and a charge that is too small shows up as a deficit partway through.

Expressing the credit as a function of the state rather than as a running balance is what makes it composable, so it handles structures where the stored work depends on shape. It is the method that generalizes; the other two are special cases.

The geometric sum is the entire argument: the copies before the last one total less than the last one, so the whole history is linear. That is why the bound survives any number of appends rather than holding on average over a few.

Amortized bounds say nothing about any individual call, so a latency budget cannot be met with one. Where a tail percentile matters, pre-size the structure or use an incremental variant that spreads the copy over later operations.

The inner loop looks quadratic and is not, because the total number of pops is bounded by the total number of pushes. Recognizing that shape is what makes next-greater-element, histogram areas and span problems linear instead of nested scans.

The interleaving is what makes it hard: a graph search answers one connectivity query, but recomputing it after every union is quadratic. The structure exists because the question arrives repeatedly while the graph is still changing.

Rewriting the array on every union is the defect, and it is invisible in a query-heavy test. Building n components with n unions is quadratic, which is why this version is the worked wrong answer rather than an option.

Moving the work from union to find swaps one quadratic for another, since a degenerate chain makes every find a walk. It is the right structure with the wrong attachment rule, which is what the next two entries fix.

Attaching by size keeps every tree shallow, and the proof is simple: a node's depth increases only when its tree is the smaller one, which can happen at most log n times. One comparison per union buys the whole bound.

The flattening pays for itself because the walk has already been done — repointing the nodes costs the same pass. Done alongside weighting it is what takes the structure from logarithmic to effectively constant.

The function grows so slowly that it is below five for any input that fits in a computer, so treating the operations as constant is honest in practice. It is not literally constant, which matters only in theoretical lower-bound arguments.

Knowing two sites connect without knowing the route is exactly what makes the structure cheap — it stores a representative, not a graph. When the path itself is wanted, this is the wrong tool and a search is the right one.

Already in FINAL position is the strong part: the prefix never changes again, so the algorithm is insensitive to the input's order. That is also why it cannot exploit nearly-sorted data the way the next sort can.

Exactly n exchanges makes it the choice when a move is far more expensive than a compare — large records, or items whose relocation triggers work. Where moves are cheap, the quadratic compare count is what you actually pay.

Sorted-but-not-final is what lets later items push into the prefix, and it is the whole difference from selection sort. It also makes the sort ONLINE: items can arrive one at a time and the prefix stays valid.

Adaptivity is why it survives inside production sorts: real data is often partly ordered, and on such input it beats every asymptotically faster algorithm. Reverse-sorted input is its worst case, and sorting-then-reversing is the way to avoid it.

Exactly, not approximately — each exchange removes one inversion, so the count IS the work. That makes the inversion count a precise measure of how unsorted an input is, and the reason the sort is linear when it is nearly ordered.

Same class, strictly more work, and no property that recommends it — there is no input on which it is the right choice. It persists in teaching because the mechanism is easy to see, not because anything ships it.

Letting an item jump h positions at a time is what breaks the quadratic bound: distant inversions are removed early, so the final pass has little left to do. Its cost depends on the gap sequence, which has no clean closed form.

Below the crossover the recursive overhead and the auxiliary space cost more than the extra compares, so the faster class loses. The threshold is measured per implementation, which is why library sorts carry a tuned constant rather than a principle.

The combine step is where the cost lives, which is the general lesson: halving alone gives log n levels, and what you do per level sets the class. A constant-time combine would give linear; a quadratic one would give quadratic.

One pass with two cursors is what makes the whole bound work, and the auxiliary array is what makes the pass simple. Trying to merge in place is possible and much more intricate, which is the trade the standard version declines.

Log n levels of linear work is the arithmetic to internalize, because the same shape appears everywhere: any divide-and-conquer with a linear combine and a halving split lands in this class, whatever the problem.

Linear extra space is the price of the simple merge, and it is a real constraint on a memory-bound job or an embedded target. Where it cannot be paid, heapsort gives the same class in place, at the cost of stability and cache behavior.

Taking the left run on a tie is the single line that makes it stable, and it is why it is the sort behind multi-key ordering. Reverse that comparison to a strict one and stability is silently lost.

Needing only sequential access is the property, so the splitting and merging are pointer rewiring rather than copying — which removes the auxiliary array entirely. Quicksort, which depends on indexing, has no comparable list form.

Streaming is the property both uses rest on: a merge needs only the front of each run, so runs can live on disk or on different cores. That is why it underlies external sorting and most parallel sort implementations.

The constant-width strip is the insight, and the reason the bound holds: geometry limits how many points can crowd into it, so the across-the-divide check is linear rather than all-pairs. Without that argument the recursion buys nothing.

Changing representation is the move: in point-value form multiplication is elementwise, so the work shifts entirely into the transform and back. It is the canonical example of solving a problem by choosing a different basis for the input.

One element reaching final position per partition is what makes the recursion shrink, and it is why no merge step is needed. Everything else about the algorithm — the cost, the worst case, the fixes — follows from how balanced that split is.

Long-range exchanges are what buy the in-place property and what destroy stability, so the two cannot both be had from this scheme. When ordering of equal keys matters, that rules quicksort out regardless of its speed.

Size n−1 subproblems give n levels instead of log n, so the cost is the sum of a linear series. The worry is not that it is possible but that for a fixed pivot rule it is reachable by a specific, often natural, input.

The most common real input is the worst case, which is the defect in its sharpest form — a sort that gets slower on tidy data. Already-sorted arrays arrive constantly, so this is not a contrived adversary.

Randomizing moves the bad case from the input's control to chance, so there is no sequence a caller can supply to force it. Shuffling first and choosing randomly each time are equivalent; doing neither leaves the trap above live.

Equal keys defeat a two-way split because they all land on one side, recreating the maximally unbalanced partition. It matters because duplicate-heavy data is normal — booleans, categories, grades — not an edge case.

Putting the equal keys in the middle and never recursing on them turns the duplicate problem into an advantage: with few distinct keys the depth collapses. This is the fix to the previous entry rather than a separate optimization.

Recursing into one side only turns the log n levels into a geometric series, which sums to linear. It gives the kth element without the ordering of the rest, so use it for medians and percentiles instead of sorting.

Only the extreme is accessible, and that restriction is what buys the log n cost — maintaining a total order would cost more. Reaching for a sorted list because you also want the second item is usually the wrong trade.

The condition is local — parent against children — which is why repairs touch one path rather than the whole structure. It says nothing about siblings, so two nodes at the same depth are in no particular relation.

No pointers means no allocation per node and contiguous memory, which is a large constant-factor win. It depends on the tree being complete; a heap with holes could not use address arithmetic to find a child.

One compare per level is the entire cost model, and both operations follow a single root-to-leaf path. Knowing which one applies is the practical part: a key that grew swims, a key that shrank sinks.

The bound is the height, and a complete tree's height is logarithmic by construction — which is why completeness is maintained rather than treated as a nicety. Breaking it would make the depth, and so the cost, unbounded.

Bottom-up wins because most nodes are near the leaves and sink barely at all, while repeated insertion makes every node travel from the bottom. The sum of heights is linear; the sum of depths is not.

Partially ordered is the thing to hold onto: printing the array looks almost sorted and is not, which is a tempting and wrong shortcut. Only repeated removal yields sorted order, and that is heapsort.

Constant extra space with a guaranteed n log n is a combination neither mergesort nor quicksort offers, which makes it the safe choice under a hard memory bound. Its weakness is cache behavior: the sink path jumps around memory.

Keeping only k and evicting the minimum bounds both the memory and the log factor, so it works on a stream of unknown length. Sorting everything to take k is the reflex to unlearn when k is small.

Counting leaves is the argument: n! orderings need that many distinguishable outcomes, and a binary decision tree of depth d has at most 2^d of them. It bounds COMPARISON sorts only, which is exactly the opening the next entry uses.

Using the key as an index rather than comparing sidesteps the decision tree entirely, so the bound does not apply. The cost is a different constraint: the key range has to be small enough to allocate an array over.

Direction follows from the key length. Right-to-left needs every key the same width and relies on a stable pass per digit; left-to-right handles variable length and finishes early, at the cost of recursive bookkeeping per bucket.

It is a property of the ALGORITHM, not of a run, so it either holds for every input or it does not. It only becomes visible when equal keys carry other distinguishing data, which is why its absence passes most tests.

The split is not arbitrary: insertion sort only ever moves an item past strictly greater ones, and mergesort breaks ties toward the left run, while the others exchange across arbitrary distances. Any sort can be made stable by appending the original index to the key.

Secondary first works only if every pass is stable, which is the condition people forget — with an unstable sort the earlier ordering is destroyed. A composite comparator avoids the dependency and makes the intent explicit in one place.

A comparator that reports both a < b and b < a, or that is inconsistent across calls, is undefined behavior rather than a slightly wrong order. Subtracting two ints to compare them breaks it on overflow, which is the usual cause.

Exploiting existing runs is the part that distinguishes a production sort from a textbook one: real input is rarely random, so a sort that detects ordered stretches skips most of its work. That is why benchmarking on random data overstates the cost.

Overwrite rather than append is the semantic that distinguishes it from a multimap, and the one people trip over when counting occurrences. Uniqueness is the whole contract; everything else is an implementation choice.

Linear is the baseline every other implementation is measured against, and it is genuinely fine below a few dozen entries where the constant is tiny. The point of the chapter is what you buy by giving up the simplicity.

Fast reads with expensive writes is a real design point, not a failed attempt: a table built once and queried often is exactly this shape. Interleave insertions and it is quadratic, which is what the tree chapters fix.

These are the operations a hash table cannot offer at any price, so they are the reason to choose an ordered structure. Needing just one of them — a nearest match, a range scan — settles the choice on its own.

They are inverses, which is why one implementation gives both and why a structure maintaining subtree sizes gets them in log n. Together they turn an ordered table into something you can take percentiles from.

Decide by the QUERIES, not by the speed: if every lookup is an exact key, hash; if any query asks for a neighborhood, an order or a range, the log factor is the price of being able to answer at all.

The entry is not corrupted so much as unreachable — it sits in the slot its old hash chose, and the new hash looks elsewhere. Nothing throws, which is why the rule is to use immutable keys rather than to mutate carefully.

Inheriting the costs exactly is the useful part: every tradeoff above transfers, so a hash set loses ordering and a tree set keeps it. Choosing a set implementation is the same decision as choosing a map implementation.

The condition is about the whole SUBTREE, not just the immediate children, which is the error that produces a tree failing search while looking locally correct. A node must beat every key below it on the relevant side.

Sorted output falls out of the structure for free, so a BST is a sorted container you can also insert into cheaply. It is also the cheapest validity check: walk inorder and assert the sequence increases.

Every operation is one path, so the whole performance question reduces to how tall the tree is — which is why the next entries are about shape rather than about code. Balance is not an optimization here; it is the cost model.

Random order gives a logarithmic height with a small constant, which is why unbalanced trees perform well in benchmarks. The catch is that real key arrival is rarely random, and the next entry is what happens then.

Sorted input is the common case and the worst case at once, the same trap as naive quicksort. A tree built from an ordered export has linear search and looks fine until the data grows.

Two cases, and the second is the one that gets forgotten: with no right child you walk up until you turn right. Getting both right is what makes an inorder iterator work without recursion or a stack.

Always promoting from the same side is what skews the tree, so a long run of deletions degrades the height even if insertions were random. It is the reason deletion is the hardest operation to get right on an unbalanced tree.

The task picks the order: pre-order for copying or serializing a structure, in-order for sorted output, post-order for freeing children before a parent or evaluating an expression bottom-up.

Recursion gives depth-first by construction, so breadth-first needs an explicit queue — there is no recursive formulation. That queue is also what makes level-by-level processing and shortest-path-in-edges possible.

Turning an expectation into a guarantee is the whole value: the average case was already logarithmic, and what balancing removes is the adversarial input. Pay for it when the key order is outside your control.

Growing at the ROOT rather than the leaves is what keeps every path the same length, so the tree stays perfectly balanced by construction. It is the mechanism red-black trees and B-trees both implement.

Encoding a wider node as a colored link keeps every node two-child, so the implementation stays ordinary binary-tree code. The color carries the 2-3 structure that would otherwise need variable-sized nodes.

The two conditions together bound the height within a factor of two of perfect, which is the guarantee. Perfect black balance does the bounding; forbidding consecutive reds is what keeps the red links from undoing it.

Leaving the key sequence unchanged is what makes a rotation safe to apply anywhere: it is a pure reshaping, so search correctness cannot break. All balancing schemes are built from this one local, order-preserving move.

Counting BLOCK READS rather than compares is the shift: with a large fanout the height is three or four, so a lookup is a handful of I/Os. Comparing keys inside a loaded node is effectively free by comparison.

Matching the node to the hardware's transfer unit is the design, which is why the same idea appears at two scales — disk blocks for databases, cache lines for in-memory variants. The algorithm is chosen by the memory system, not the reverse.

Trading rotations for randomness gives a much simpler implementation and local updates, which is what makes concurrent versions tractable. The bound is expected rather than guaranteed, which is the cost of dropping the invariants.

Turning a lookup into arithmetic is the whole idea, and it is why the cost does not grow with the number of keys. Everything difficult about hash tables is what happens when two keys want the same index.

The one-way direction is what people invert: a hash that differs for equal objects loses them, while a hash that matches for unequal ones merely costs a comparison. Override equality and you must override hashing in the same change.

Inevitable means the design question is never how to avoid them but how to resolve them, which is what the next entries are about. A scheme that assumes a perfect hash is a scheme with an unhandled case.

The load factor being the average chain length is what makes the structure predictable: keep it near one and lookups are a slot plus a short walk. It degrades gracefully, which is its advantage over probing.

Blanking a slot on deletion breaks every key whose probe sequence passed through it, so the search stops early and reports absent. Either rehash the cluster or use a tombstone — doing neither loses entries silently.

Compounding is the mechanism: a run grows by absorbing every key that lands anywhere in it, so cost rises faster than the load factor suggests. Quadratic probing and double hashing exist to break that feedback.

The climb is non-linear, so a table at 0.9 is far worse than twice a table at 0.45 — which is why implementations resize well before full. Rehashing every key is the latency spike that an amortized bound hides.

The guarantee is only probabilistic, which becomes a security question when an attacker chooses the keys: deliberate collisions turn a lookup into a scan. Randomized seeds per process are the standard defense.

Unspecified iteration order is the part that causes bugs rather than slowness: code that happens to work because a small table iterated conveniently breaks when the table grows and rehashes.

The asymmetry is what makes it useful: a negative is certain, so it can safely short-circuit an expensive lookup, while a positive only means check properly. Use it as a filter in front of real storage, never as the storage.

Neither structure alone can do it — the map has no recency and the list has no lookup — so the composition is the answer. The map stores the NODE rather than the value, which is what makes the list removal constant.

The vocabulary is the modeling step: naming what a vertex and an edge represent is what turns a problem into a graph problem, and getting it wrong is the commonest reason the right algorithm gives a useless answer.

Quadratic space is the binding constraint, not the edge test: a million vertices need a trillion entries whatever the edge count. Choose it only when the graph is genuinely dense or when you need matrix operations on it.

Linear in the graph's actual size is why this is the default, and neighbor iteration is the operation every traversal performs. Its weakness is the edge test, which costs a scan of one vertex's list rather than a lookup.

Representation decides feasibility because it sets the MEMORY, and a graph that does not fit cannot be traversed at any speed. Count the edges against V² before choosing: real graphs are overwhelmingly sparse.

The marking is what makes it a search rather than an infinite walk, since any cycle would otherwise loop forever. Mark on ENTRY, not on exit — marking late lets a vertex be entered twice before either call returns.

The failure is an overflow rather than a slowdown, so it arrives as a crash on large input while the complexity analysis says linear. A long path or a deep chain is enough; convert to an explicit stack when depth is unbounded.

Settling in distance order is the reason it yields shortest paths, and it only holds for UNWEIGHTED edges — each level is one more edge. Add weights and the ordering argument fails, which is what Dijkstra restores.

Same cost, different answers: depth-first finds a path and reveals structure, breadth-first finds the shortest one and explores outward. Pick by what you need from the result, not by performance — they are the same class.

One pass over the vertices with a search from each unmarked one is linear overall, because every vertex and edge is touched once. It is also the pattern for any whole-graph property: iterate the vertices, search from the unvisited.

Exactly when — the coloring is not a heuristic but a complete test, so a conflict is a proof of an odd cycle. That makes one traversal both the check and the construction of the two sides.

Excluding the parent is the whole subtlety: without it every single edge looks like a cycle, since the neighbor you came from is marked. With a multigraph you must exclude the parent EDGE, not the parent vertex.

One-way reachability is why a directed graph needs twice the thinking: the component structure, the connectivity question and the algorithms all split into forward and backward versions. Undirected intuitions quietly fail here.

The equivalence is exact in both directions, so acyclicity is not a precondition you check separately — it IS orderability. Any algorithm needing a valid order therefore doubles as a cycle test.

Reverse postorder works because a vertex finishes only after everything it reaches has finished, so finishing times already encode the dependency. One depth-first pass gives the order with no extra bookkeeping.

Leftover vertices being a cycle proof is the useful part: the algorithm reports WHICH vertices are involved, which is what a build tool needs to name the offending dependency loop. It also parallelises, since all zero-indegree vertices are independent.

On the CURRENT stack, not merely marked — a marked vertex may simply have been finished by an earlier branch, which is an ordinary cross edge. Confusing the two reports cycles in a perfectly acyclic diamond.

Mutual reachability is the right notion because one-way reachability is not an equivalence relation. The reverse-graph pass is what makes the two-pass algorithm work: it finds the vertices that can reach back.

Always acyclic, by construction — a cycle between components would merge them. That is what lets any directed graph be processed as a DAG of components, which is how cyclic dependency graphs are still scheduled.

Recognizing the shape is the transferable part: anything with must-happen-before constraints is this problem, and the cycle case is a genuine user-facing error rather than an algorithmic inconvenience.

Exactly V−1 edges is the counting fact to keep: fewer cannot connect every vertex, more must close a cycle. It also means the answer's size is known in advance, which is a useful loop bound and a cheap sanity check.

Some MST, not every MST — with equal weights there may be several, which is why a greedy choice is safe without being unique. This property is what justifies both algorithms below; they differ only in which cut they consider next.

The mirror of the cut property, and the reason Kruskal may safely skip an edge: the heaviest edge on a cycle is never needed. Together the two give a complete rule for including and excluding edges.

Union-find is the cycle test, and that pairing is the whole algorithm: sorting dominates the cost, and the connectivity check is effectively constant. It builds a forest that merges, rather than one growing tree.

Always one connected tree is the difference from Kruskal, which means no union-find and no global sort — the priority queue holds only the frontier. That locality is what suits it to dense graphs.

Density decides because their costs scale differently: Kruskal pays to sort every edge, so a dense graph punishes it, while Prim's frontier work is bounded by the vertices. An edge list that arrives already sorted makes Kruskal nearly free.

Only comparisons matter, so no shift or offset is needed — unlike shortest paths, where a negative edge breaks the central invariant. The contrast is worth holding: the same input is harmless here and fatal there.

Minimizing the TOTAL is a different objective from minimizing any one distance, so the MST path between two vertices can be much longer than their shortest path. Using an MST as a routing table is the mistake this prevents.

One primitive underlies every algorithm in the chapter, and what distinguishes them is only the ORDER in which edges are relaxed. Seeing that collapses four algorithms into one operation plus a scheduling decision.

Final once settled is what makes it efficient — no vertex is ever reconsidered — and it is exactly the claim the next entry breaks. The invariant rests on every edge being non-negative, so nothing later can shorten a settled route.

It returns a wrong answer rather than failing, which is the danger: the algorithm completes, the distances look plausible, and some are too large. Check for negative weights at the entry point rather than trusting the input.

Density decides again: with E near V² the heap's log factor is pure overhead, and the simple scan wins. The lesson is that the asymptotically better structure is not automatically the faster one.

Topological order already guarantees each vertex is final when reached, so the priority queue's whole job is done for free — which is why it also tolerates negative weights. Check for acyclicity first; it buys a faster and more general algorithm.

The round count comes from the path length bound, which is why V−1 is sufficient and not arbitrary. It is slower than Dijkstra by design: the price of handling negative edges is giving up the settle-once shortcut.

A further improvement proves a cycle because no simple path can be longer than V−1 edges, so any extra gain must come from going round. Reporting that no answer exists is the correct output here, not a failure.

The dynamic program is over the ALLOWED INTERMEDIATE SET, which is why the three nested loops must have the intermediate vertex outermost. Swap that loop inward and the recurrence is wrong while the code still runs.

Negation fails because it creates negative cycles, and the algorithms that tolerate negative edges then report that no answer exists. The asymmetry is a genuine complexity boundary, not a missing technique.

The key living in the PATH rather than in a node is what makes the structure unusual: no node stores a whole key, and two keys sharing a prefix share those nodes. Every property below follows from that one arrangement.

Independence from the key count is the property worth having — a million keys cost no more to search than a hundred. The length of the key is the bound, so long keys over a small set are the case where it loses.

Links per node, times nodes, is where the memory goes, so a large alphabet is expensive even for few keys. Ternary search tries and compressed tries exist to pay less for sparse branching.

Sorting the suffixes gives the same substring answers in a flat array rather than a pointer structure, which is why it scales to a whole genome or corpus. The common-prefix array is what replaces the tree's shared branches.

These are the queries that justify the memory: a hash of whole keys can answer none of them, because hashing destroys the relationship between a key and its prefixes. Autocomplete and routing tables are the usual reasons.

Backing up in the TEXT is the defect, not the compare count: it means the input cannot be streamed, and a partial match must be re-read. That single property is what the next three algorithms each remove differently.

Never re-reading a text character is what makes it streamable and worst-case linear, and the precomputed table is where the pattern's self-overlap is recorded. The cost is that the table has to be right, and it is subtle.

Verifying only on a hash match is what keeps it fast while staying correct — the hash can collide, so the check is required. It generalizes best of the four: multiple patterns, or two-dimensional matching, cost little extra.

Scanning backwards means a mismatch on a character absent from the pattern skips the whole pattern width, so long patterns get FASTER per character. The usual mismatched-character variant is sublinear in practice and still quadratic in the worst case.

Exactly when — without repetition there is nothing to cache, so a divide-and-conquer that splits into disjoint parts gains nothing from a table. Check for the overlap before reaching for DP; its absence means the problem is a different shape.

A recurrence without it is wrong rather than slow, which is why this is the first thing to argue rather than the last. The usual failure is a state that hides a constraint, so a sub-answer that looks optimal is not usable by the whole.

Computing only what is reached is the advantage: on a sparse state space it visits a fraction of the table. The cost is the call stack, which is a real limit at depth, and the hashing of the key.

No stack and better locality, at the price of needing the dependency order up front — and of filling states that may never be needed. Where the order is obvious and the table is dense, this is the faster of the two.

And nothing more is the half that gets ignored: an extra dimension multiplies the work for no gain, while a missing one makes the recurrence wrong. Ask what the remaining decisions actually need to know.

Multiplying them is how to price a DP before writing it, which is the step that prevents building a solution that cannot run. It is also the lever for optimization: shrink the state, or make each transition cheaper.

The demonstration is worth tracing once because the tree makes the repetition visible: the same argument appears at many depths, and caching it collapses the branching entirely. Nothing about the recurrence changes, only what is recomputed.

Density greedy fails because an indivisible item can force wasted capacity, so the locally best ratio is not extendable. Capacity-indexed states are what let every remaining allowance be considered instead of committed to.

Branching on the last characters is the move that makes the grid work: equal characters reduce both sequences, unequal ones try each reduction. Diff tools and spell-checkers are this recurrence with different costs attached.

Keeping the smallest possible tail per length is the insight, and that array is sorted — which is what admits the binary search. It yields the LENGTH directly; recovering the subsequence needs predecessor pointers.

The loop order silently changes WHICH problem is solved, and both versions run and return a number. Decide first whether order matters in the answer, then write the loops to match; there is no way to tell from the output alone.

The table answers how good, not which choices, so reconstruction is a separate step people forget to budget for. A back-walk needs no extra memory and re-derives each decision; parent pointers cost space and are simpler to get right.

Provably extendable is the bar: it is not enough that the choice looks best, it must be shown that some optimal solution contains it. That proof is what separates a greedy algorithm from a heuristic that usually works.

Test cases cannot establish it because counterexamples to greedy rules are often large or structured, so a wrong rule passes everything you think to try. An exchange argument is the standard tool: show any optimum can be rewritten to use your choice.

The two plausible alternatives both fail, which makes this the best example of why the proof matters: earliest start loses to one long interval, shortest duration loses to a short one straddling two others.

Splittability is the hinge, and it is the clearest case of one problem being greedy and its near-twin needing DP. Check whether a unit can be divided before choosing the paradigm; the input often looks identical either way.

Merging the two rarest is the greedy choice, and the proof is an exchange argument: the two least frequent symbols can always be made deepest siblings. The result is optimal among prefix codes, which is a bounded claim rather than optimal compression.

An arbitrary denomination set is the counterexample to keep because the natural rule — take the largest coin that fits — is so convincing. Real currencies are built so it works, which is exactly why the failure is surprising.

Commit versus keep is the distinction, and it decides the cost: greedy explores one path, DP explores the frontier it cannot prune. Greedy is DP with a proof that lets you discard every alternative immediately.

The pruning is what makes it practical rather than exhaustive, and the quality of the bound decides everything: a weak bound explores almost the whole space. Finding a good solution early makes every later prune sharper.

Each index moves one way only, which is why the pass is linear and why sortedness is required — the comparison tells you which pointer to advance. Without the order there is no such signal and the technique has nothing to drive it.

Meeting is a PROOF of a cycle, not a hint: on a cycle the gap closes by one each step, so a meeting is guaranteed. It also needs no extra memory, which is what distinguishes it from marking visited nodes.

Each index advancing at most once is what makes the nested loop linear, the same amortization argument as the monotonic stack. Counting the inner loop's iterations instead of its depth is what reveals the real cost.

Applying it to a non-monotone predicate is the commonest misuse, and it fails silently — the window shrinks past a valid answer and never returns to it. Check the direction of the constraint before choosing the technique.

One pass buys constant-time range queries, which turns a nested-loop scan into a linear one. It only works for invertible operations: sums and XOR yes, maximum no, since a prefix maximum cannot be subtracted away.

Searching the answer space is the move to recognize, and the precondition is monotone feasibility — if a value works, every larger one must too. It converts an optimization problem into a sequence of yes-or-no checks.

It is the cheap middle ground: prefix sums are static and a segment tree is general, and this handles point updates with one array and a few lines. Its limit is that the operation must be invertible, like the prefix sums it generalizes.

Precomputing power-of-two jumps turns any ancestor walk into a binary decomposition of the distance, which is the same idea as writing a number in binary. The table costs n log n space, which is the trade for dropping a linear walk.

Associativity is the only requirement, which is why one structure answers sums, minima, maxima and GCDs. Lazy propagation is what extends it to range UPDATES, by deferring work until a query forces the node to resolve.

Seeing the operations as arithmetic is what makes them predictable instead of magic: a mask is a sum of chosen powers, and a shift is a multiplication. Every trick below is derivable once that correspondence is held.

Four roles, and the one worth separating is XOR: masking and setting are idempotent, toggling is not, so applying it twice restores the original. That reversibility is what the swap and unpaired-element tricks rest on.

Discarding the remainder is where the equivalence stops being exact: a right shift truncates, and for negative numbers that truncation rounds toward negative infinity rather than toward zero. Division and shifting are not interchangeable on signed values.

Which one you get is decided differently per language: C and its relatives pick by the operand's signedness, while Java and JavaScript give the two their own operators. Either way, using a signed type as a bit container is how the sign-filling surprise arrives.

The asymmetric range is the consequence people meet first: negating the most negative value overflows back to itself, because its positive counterpart does not exist. Any absolute-value or negation code has that one input as a special case.

Three idioms covering the whole interface, and the clear is the one worth reading carefully: the complement builds a mask of all ones except the target. Writing a shift without parentheses is the usual bug, since precedence favors the arithmetic.

Both work because subtracting one flips the lowest set bit and everything below it, which is the single fact behind them. Clearing in a loop runs once per SET bit rather than once per bit width, which is why it beats a scan on sparse values.

Self-inverse means pairs cancel wherever they appear, so order does not matter — which is what makes the single-unpaired-element scan work in one pass with no memory. The no-temporary swap is a curiosity; the cancellation is the useful part.

The asymmetry comes from the array underneath: the end has spare capacity, the front does not. Building a sequence by inserting at index zero is quadratic, and appending then reversing is the linear equivalent.

Same syntax, different class, which is what makes this a frequent accidental quadratic: a membership test inside a loop over a list. If the collection is only ever tested for membership, it should not be a list.

The middle is the cost: a deque is blocks of elements, so indexing walks the blocks. Reach for it when both ends are hot and nothing indexes, and keep a list when random access matters more than the front.

Average, with the usual caveat — and the practical form of that caveat is latency rather than throughput, since a resize rehashes everything at once. Pre-sizing a known-large dict avoids the spike.

Negating the keys is the standard workaround and it has a trap: it works for numbers and breaks for tuples carrying non-numeric tiebreakers. Wrapping items in a comparison object, or pushing a (priority, counter, item) tuple, is the safer form.

The log search does not make the structure cheap to update, so maintaining a sorted list by repeated insertion is quadratic. Use it for a list built once and searched often, and a tree or heap when it changes.

Each step copies the whole accumulated string, which is the same shape as growing an array by one. Collecting the pieces and joining once is linear, and it is the single most common accidental quadratic in string code.

Pick by the OPERATION MIX, not by what the data is: the same items belong in different containers depending on whether you look them up, order them, or work both ends. Counting the operations in the hot loop settles it.

The direction is the whole content, and reversing it is the classic error: showing your problem reduces to a hard one proves nothing about yours. To prove hardness, reduce a KNOWN hard problem TO the new one.

Solving versus checking is the distinction, and it is why the question is open: nobody has shown that verifying a certificate is genuinely easier than finding one. Most practical problems are in P; the interesting ones in NP are the ones below.

Every problem in NP reducing to it is what makes one of these a universal case: a polynomial algorithm for any single NP-complete problem would give one for all of them. That is why nobody expects to find one, and why the label ends a search.

NP-hard is the weaker membership and the stronger difficulty claim: it means at least as hard as NP-complete, with no requirement to be in NP or even to be a yes-or-no question. Optimization versions of NP-complete problems are typically NP-hard, not NP-complete.

Knowing the list is practical rather than academic: recognizing that a requirement IS one of these stops a search for an exact efficient algorithm and starts the conversation about approximation or problem reformulation.

Real instances are not worst cases, and modern solvers handle large structured inputs routinely. The honest response to NP-hardness is to change what you promise — approximate, bound the input, or accept a time limit — not to give up.

Reductions prove lower bounds as well as upper ones: if an easier-to-bound problem reduces to yours, your problem inherits its floor. That is how a geometric problem gets a bound derived from sorting.

The equality is the useful part, because it gives a certificate: the cut proves the flow cannot be improved. That is also why so many matching, scheduling and partition problems are solved by being reduced to a flow.

One pass with bounded memory is what makes it work when the total count is not known in advance, which is the case no shuffle-and-take can handle. The probability is uniform at every prefix, so the sample is valid even if the stream is cut short.