Glossary

A handful of terms come up in almost every article here. Each one is defined at its first use, but this is the place to look them up.

Invariant#

A statement you arrange to be true before a loop starts, keep true through every single iteration, and therefore know is still true once the loop ends.

Invariants are how you know a loop is correct without tracing every possible input. If the statement holds at the end and the loop has finished, the answer follows. Most off-by-one bugs are a step that quietly broke an invariant nobody had written down.

Loop invariant#

The same idea, named for where it lives. Writing a loop invariant down before you write the loop is the single most reliable way to get boundary conditions right — it converts “does this need < or <=?” from a guess into something you can check.

Closed and half-open intervals#

Two conventions for describing a range of indices.

• Closed, written [left, right] — both ends are inside the range. An empty range is left > right.
• Half-open, written [left, right) — the left end is inside, the right end is one past the last item and is never read. An empty range is left == right.

Neither is more correct. What matters is picking one and letting it dictate every boundary update, which is exactly what the binary search article works through.

In place#

Rearranging the input itself rather than building a new structure, using O(1) extra space. “In place” does not mean no extra variables — a couple of indices are fine. It means the extra memory does not grow with the size of the input.

Off-by-one#

An error of exactly one position: a loop that stops one step early, an index one past the end, a range that includes a boundary it should exclude. They are common precisely because they survive casual testing — the code works on most inputs and fails at the edges.

Amortised#

An average cost per operation taken across a whole run, rather than the worst case of any single operation.

It matters when an inner loop looks expensive but cannot run often. In a sliding window the inner while can shrink the window several times in one iteration, which looks quadratic — but the left pointer only ever moves forward, so across the entire run it advances at most n times. The amortised cost per step is constant, and the whole scan is O(n).