Aligning two 100k-character documents needs 10^10 table cells. What do you change before writing the loop?

## Read the number correctly Two documents of 100,000 characters give a table of about 10^10 cells. Two things follow, and candidates usually only see the second. 1. **Time.** Ten billion cell updates is the dominant problem. Even at a very optimistic billion updates per second that is on the order of ten seconds, and realistically minutes. 2. **Memory.** At a few bytes per cell that is tens of gigabytes, which is simply unavailable. The reflex answer — "keep one row instead of the whole table" — fixes only the second. It is a correct optimization and it is not an answer to this question. Say that out loud; it is the discriminating remark. ## Step 1: change what a cell compares For documents, characters are rarely the right unit. Comparing whole lines cuts `n` from 100,000 characters to perhaps 3,000 lines, and 10^10 becomes 10^7 — a table you can simply fill. Reduce each line to a fixed-size fingerprint once, up front, so each cell's comparison is constant time instead of proportional to line length. This single decision usually ends the conversation, and it is the one real systems make. Also strip the common prefix and the common suffix before building anything. Edits are almost never uniformly distributed across a document; a config file that gained a section in the middle shares tens of thousands of identical leading and trailing characters, and neither contributes anything to the alignment. ## Step 2: exploit the shape of the answer The key structural insight is about *paths*. An alignment is a monotone path from one corner to the other; a diagonal step costs nothing when the units agree, while every off-diagonal step corresponds to an insertion or a deletion. So a path that ends up `d` columns away from the main diagonal has spent at least `d` insert-or-delete operations. If you only need to know whether the distance is at most `k`, every path that could possibly answer yes stays inside the band `|i - j| <= k`. Fill only that band and treat cells outside it as infinite: - cost becomes `O(n * k)` time and `O(n * k)` space (or `O(k)` if you keep one banded row) - the answer is exact when the true distance is `<= k`, and otherwise you learn only that it exceeds `k` When `k` is unknown you can start small and double it, re-running until the reported distance is comfortably inside the band; the geometric growth keeps the total work proportional to the final run. This is the standard threshold trick, and it is what makes near-identical inputs cheap: for a typo-scale difference, `k` is single digits and `n*k` is linear for practical purposes. The same insight has a difference-driven form used by real diff tools: search by increasing number of differences `d`, so the work scales with `(n + d) * d`. Two near-identical documents have a tiny `d` and finish almost instantly; two unrelated documents degrade back toward quadratic, which is the honest tradeoff. ## Step 3: only then, the space-only fix If you genuinely need a full alignment over inputs where the quadratic time is acceptable but the table is not, Hirschberg's divide and conquer recovers the alignment in `O(min(m,n))` space: compute forward scores over the first half and backward scores over the second half, find the column where they meet, and recurse on the two halves. The time stays `O(m*n)` — roughly doubled by the recursion, with the halving series summing to a constant factor. Name it as the tool for that specific constraint, and do not offer it as an answer to a time problem. ## Step 4: when it is a search, prefilter If the real task is finding near matches among many candidates rather than aligning one pair, the alignment should run last and rarely. Two cheap filters do most of the work: the length bound, since the distance is at least `|m - n|`, so any candidate whose length differs by more than `k` is rejected without a table; and a cheap overlap test on short character groups, since inputs within `k` edits must share most of their short groups. Only survivors get a table, and each of those tables is banded. ## What a good answer sounds like "Ten billion cells is a time problem before it's a memory problem, so a rolling row isn't the answer. I'd trim the shared prefix and suffix, compare fingerprinted lines instead of characters — that alone drops it by orders of magnitude — and if the question is really 'within k edits?', fill only the `|i-j| <= k` band for `O(n*k)`, doubling `k` if needed. Full alignment with a memory ceiling is where a linear-space divide-and-conquer belongs, but it doesn't buy back any time."