I Implemented Myers Diff in 130 Lines, Then Lost Half a Day to an Off-by-One Bug

I Didn't Want Another Dependency

I could have installed a diff library and been done in five minutes. I know.

But my developer tool suite PureMark has a strict zero-dependency policy. The JSON Formatter, Base64 decoder, URL Encoder — all hand-written. Letting the Diff Checker be the one exception didn't sit right.

Besides, I use git diff every single day, and I couldn't explain what was actually happening behind the scenes. That bothered me.

Turns out, it's a 1986 algorithm by Eugene Myers. git diff, the Unix diff command — they all use it under the hood. Nearly 40 years old and still the standard. When I implemented it, it fit in about 130 lines of TypeScript.

This article covers how the algorithm works and the off-by-one bug that cost me half a day.

Try the finished product here: PureMark Diff Checker

Paste two blocks of text and see the diff highlighted instantly.

Reframing Diff as a Shortest Path Problem

The core insight of Myers' algorithm is turning a diff problem into a shortest-path problem on a graph.

Given two texts A (old) and B (new), imagine a grid with A on the x-axis and B on the y-axis:

     B[0]  B[1]  B[2]  B[3]

      |     |     |     |

  (0,0)-->(1,0)-->(2,0)-->(3,0)-->(4,0)

    |  \    |  \    |       |       |

    v   \   v   \   v       v       v

  (0,1)-->(1,1)-->(2,1)-->(3,1)-->(4,1)

    |       |  \    |  \    |       |

    v       v   \   v   \   v       v

  (0,2)-->(1,2)-->(2,2)-->(3,2)-->(4,2)



-> Right  = Delete (remove a line from A)

|  Down   = Insert (add a line from B)

\  Diagonal = Match (cost 0)

The shortest path from (0,0) to the bottom-right corner gives you the minimal edit sequence.

Diagonal moves cost zero — when lines match, you skip ahead for free. That's the source of Myers' efficiency.

The algorithm increments the edit distance d = 0, 1, 2, ... one step at a time, recording the farthest reachable point at each step. Once it reaches the goal, it backtracks to reconstruct the edit sequence.

This "shortest path on a coordinate grid" mental model makes both the algorithm and the implementation far more approachable.

130 Lines. It Worked. Or So I Thought.

Here's the core:

function myers(a: string[], b: string[]): EditOp[] {

  const n = a.length, m = b.length, max = n + m;

  const v = new Int32Array(2 * max + 1);

  const offset = max;

  v[offset + 1] = 0;

  const trace: Int32Array[] = [];



  for (let d = 0; d <= max; d++) {

    trace.push(v.slice());  // Snapshot the V array

    for (let k = -d; k <= d; k += 2) {

      let x = (k === -d || (k !== d && v[offset+k-1] < v[offset+k+1]))

        ? v[offset+k+1] : v[offset+k-1] + 1;

      let y = x - k;

      while (x < n && y < m && a[x] === b[y]) { x++; y++; }

      v[offset + k] = x;

      if (x >= n && y >= m) return backtrack(trace, offset, n, m, a, b);

    }

  }

  return backtrack(trace, offset, n, m, a, b);

}

Key points:

• 
  Int32Array makes slice() snapshots fast


• The trace array stores V state at each step — the key to backtracking


• The while loop (diagonal follow) skips matching lines at zero cost

I tested it. Short text diffs — perfect. JSON comparisons — no issues. Longer code blocks — looked correct.

I deployed.

The Bug Showed Up the Next Day

Long text, and the diff display was wrong. Deletions and insertions were in the wrong positions.

Short texts worked fine. But as line counts grew, the path drifted. Classic off-by-one smell.

I traced through the backtrack function — the part that walks backward from the goal, reconstructing "which diagonal were we on at each step." The problem was one line:

- const v = trace[d - 1];  // Wrong

+ const v = trace[d];      // Correct

Why I got it wrong.

trace.push(v.slice()) runs at the beginning of each loop iteration. So trace[d] holds "the V state before step d starts" — which is the same as "the V state after step d-1 completes."

To unwind step d, you need the state at the start of step d — that's trace[d], not trace[d-1].

The trap is the intuition that "trace[d] was saved during step d, so it must contain the state after step d." Wrong. Because the save happens at the top of the loop, it actually contains the state before step d.

With short texts, d stays small and the path drift doesn't surface. With long texts, d grows large, and a one-step offset snowballs into a visible bug.

The scary thing about this bug: short test cases won't catch it. I had unit tests, but the test data was too small. Bugs that only manifest with production-sized data are the most dangerous kind.

After the fix, I added long-text test cases. All tests pass.

See this implementation in action: PureMark Diff Checker

Toggle between side-by-side and unified views to compare how diffs are displayed.

Bonus: Solving Key Order in JSON Diff

Text diff alone has a problem with JSON.

{ "a": 1, "b": 2 } and { "b": 2, "a": 1 } are semantically identical, but a text comparison shows them as different. The solution: recursively sort keys before comparing.

function sortKeys(value: unknown): unknown {

  if (value === null || typeof value !== 'object') return value;

  if (Array.isArray(value)) return value.map(sortKeys);

  const sorted: Record<string, unknown> = {};

  for (const key of Object.keys(value as Record<string, unknown>).sort()) {

    sorted[key] = sortKeys((value as Record<string, unknown>)[key]);

  }

  return sorted;

}

JSON.parse() -> sort keys -> JSON.stringify(null, 2) -> regular text diff. That's all it takes for key-order-independent structural comparison. In PureMark Diff Checker, there's a "JSON Diff" toggle for this.

Takeaways

The biggest lesson: the off-by-one bug wasn't in the algorithm logic itself — it was in how I read the data structure. The trace array's save timing (top of loop vs. end of loop) was the entire issue. Short test cases can't find it. Bugs that only show up with real-world data are the scariest.

Before reaching for a library, try implementing it yourself. 130 lines of investment, and git diff output went from "magic" to "something I actually understand."

PureMark Diff Checker | PureMark — Zero-click simplicity for developers.

References

• 
  An O(ND) Difference Algorithm and Its Variations (Eugene Myers, 1986) — The original paper


• 
  The Myers diff algorithm (blog.jcoglan.com) — An excellent walkthrough series


• 
  PureMark — Developer tool suite