Text diff — Myers algorithm

Before touching Myers, build your intuition on the classical O(MN) LCS DP table. Given two sequences A and B, the LCS is the longest sequence of elements that appear in order in both — not necessarily contiguous. The recurrence is simple: if A[i] == B[j] extend the LCS from [i-1][j-1]; otherwise take the best of [i-1][j] and [i][j-1]. The table encodes every alignment choice, and the backtrack through it yields the actual LCS elements, not just the length. Getting backtrack right is non-trivial: diagonal moves (match), left moves (skip B[j]), and up moves (skip A[i]) must reproduce the same LCS length from every cell. Implement this as a generic `lcs<T>(a: T[], b: T[]): T[]` and prove it for strings, numbers, and mixed-type arrays. The O(MN) table will later motivate Myers as the upgrade that finds the minimal diff without materialising the full table.

The LCS tells you what to keep; everything else is a delete (in A but not in the LCS) or an insert (in B but not in the LCS). Backtrack the DP table simultaneously through both sequences: a diagonal step emits a `keep`, a leftward step emits an `insert` from B, an upward step emits a `delete` from A. The resulting array of `{op, value}` objects is the edit script. Two invariants must hold: (1) reading `keep` + `insert` ops in order yields B exactly — these are the elements you keep from A and the new elements you add; (2) reading `keep` + `delete` ops in order yields A exactly — these are the elements kept and the elements removed. These invariants make the script applicable: you can reconstruct either side from the other without storing both. Get the ordering of ops right: they must follow the alignment of A and B, not be arbitrarily reordered. A common bug is emitting all deletes before all inserts for a changed region — a correct script interleaves them as the alignment dictates.

The O(MN) DP table materialises every alignment; Myers's insight is that you only need to find the shortest edit script (minimum number of inserts and deletes, called D) and that the edit graph has structure you can exploit. A diagonal k = x − y in the edit graph advances both pointers when elements match (a snake), and you walk snakes greedily. You iterate over D = 0, 1, 2, … until you reach the bottom-right corner; at each D you only explore the reachable diagonals (k ∈ {−D, −D+2, …, D}) and store only the furthest-reaching x-coordinate on each diagonal in an array V. The outer loop runs in O(D) passes, each pass touches O(D) diagonals, and each diagonal extension is O(1) amortised (snakes move in O(N) total across all diagonals), giving O(ND) overall — which is O(N + D²) and often much better than O(MN) when the diff is small. Store the V arrays at each D so you can backtrack the path and recover the edit script. This is the algorithm that powers `git diff`, GNU diff, and every line-diff tool in production.

A diff algorithm is only useful if its output is minimal — the shortest possible edit script. Myers guarantees minimality by construction (it finds the smallest D by definition), but you must verify it empirically: the number of non-keep ops in your script must equal the true edit distance between A and B. The edit distance (Levenshtein with insert/delete only, no substitution) is len(A) + len(B) − 2 × len(LCS), because every element not in the LCS must be either deleted from A or inserted from B. Compare your diff's op count to this formula on at least five diverse pairs. A correct implementation will always match. An incorrect one will over-count (producing redundant ops) or under-count (corrupting the round-trip). This milestone also forces you to handle the degenerate cases cleanly: identical arrays (D=0, all keeps), one empty array (D=len of the other, all inserts or all deletes), single-element arrays, and very long arrays where D ≪ N.

An edit script is only as good as its applicability. Implement `apply<T>(base: T[], script: EditOp<T>[]): T[]` that reconstructs the target by consuming keep and insert ops (in order, with delete ops consumed but not emitted). The apply function must be strict: if the base element at a keep or delete position does not match the expected value in the op, throw — a misapplied patch is worse than no patch because it silently corrupts data. Verify the forward round-trip: `apply(a, diff(a, b))` deep-equals `b`. Then verify the inverse: `apply(b, invertScript(diff(a, b)))` deep-equals `a`, where `invertScript` swaps inserts and deletes. These two round-trips together prove the script is not just syntactically valid but semantically correct. Test with strings (character diffs), numbers, and objects compared by a custom equality function passed as a parameter — `lcs<T>` and `diff<T>` must accept an optional `eq: (x: T, y: T) => boolean` for non-primitive equality.

A raw edit script is a flat list of ops. What humans (and patch tools) work with is hunks: contiguous groups of changed ops with a configurable number of context lines (unchanged keeps) on each side. A standard unified diff uses 3 context lines; patch and git accept the context size as a flag. Group the edit script into hunks: scan for runs of inserts/deletes separated by more than 2×context keeps; each such run plus its context lines becomes one hunk. The hunk header carries line numbers in both the original and the target (`@@ -M,N +P,Q @@` in unified diff notation), computed by counting ops emitted so far. Implement `toUnifiedDiff(a: string[], b: string[], context = 3): string` that produces valid unified diff text and `fromUnifiedDiff(patch: string): Hunk[]` that parses it back. The round-trip `fromUnifiedDiff(toUnifiedDiff(a, b)).apply(a)` must reproduce b exactly. This is the format that `git apply`, `patch(1)`, and code review tools consume — getting the line numbers wrong by one is the canonical off-by-one that trips up every diff implementation.