Inside the Myers Diff Algorithm: How Git Finds Code Changes (And How to Build One in Vanilla JS)

Every single day, millions of software engineers run git diff, inspect pull requests on GitHub, or review merge conflicts in VS Code.

We take for granted that when we modify a 2,000-line file, our version control system instantly identifies:

  • The exact three lines we deleted (highlighted in red with a -).
  • The four lines we inserted (highlighted in green with a +).
  • The unchanged surrounding code kept intact for visual context.

Have you ever stopped to consider the mathematical problem behind this?

If you have an original file with $N$ lines and a modified file with $M$ lines, there are mathematically thousands of valid ways to transform File A into File B. You could theoretically delete the entire file and re-type the whole thing from scratch—that is technically a valid diff, but it is completely useless to a human reviewer.

The goal of a diff engine is not just to find any sequence of edits. It is to find the Shortest Edit Script (SES)—the absolute minimal number of additions and deletions required to turn one file into another.

When building the Text Diff Checker for Urban Mixo, we avoided heavy npm dependencies like jsdiff and implemented the diff engine directly in vanilla JavaScript.

Here is the graph theory behind Eugene Myers’ landmark 1986 diff algorithm, how it powers Git, and how to build a zero-dependency diff engine in the browser.

1. Diffs as a Directed Coordinate Graph

In 1986, computer scientist Eugene W. Myers published a paper titled An O(ND) Difference Algorithm and Its Variations. Myers reframed what seemed like an abstract string-comparison problem into a classic graph search problem on a 2D Cartesian coordinate plane.

Imagine comparing two sequences:

  • Original ($A$): [A, B, C, A, B, B, A] (Length $N = 7$)
  • Modified ($B$): [C, B, A, B, A, C] (Length $M = 6$)

Myers represented these two files as an $(N + 1) \times (M + 1)$ grid:

  • The x-axis represents lines in the original file $A$ (from $0$ to $N$).
  • The y-axis represents lines in the modified file $B$ (from $0$ to $M$).
  • The search starts at the top-left origin $(0, 0)$ and must reach the bottom-right terminal $(N, M)$. 
 (Original File A) A B C A B B A 0---1---2---3---4---5---6---7 C 0 | | | \ | | | | | 1 |---|---|---|---|---|---|---| B 1 | | \ | | | \ | \ | | 2 |---|---|---|---|---|---|---| A 2 | \ | | | \ | | | \ | 3 |---|---|---|---|---|---|---| B 3 | | \ | | | \ | \ | | 4 |---|---|---|---|---|---|---| A 4 | \ | | | \ | | | \ | 5 |---|---|---|---|---|---|---| C 5 | | | \ | | | | | 6 ----------------------------- (7, 6)

The Three Rules of Movement:

  1. Move Right ($x + 1$): Deletes a line from original file $A$ (Cost = 1 edit).
  2. Move Down ($y + 1$): Inserts a line from modified file $B$ (Cost = 1 edit).
  3. Move Diagonally ($x + 1, y + 1$): Occurs whenever line $A[x]$ matches line $B[y]$. Because the line is identical, it costs 0 edits.

Finding the cleanest, shortest diff is mathematically identical to:

Finding the shortest path from $(0, 0)$ to $(N, M)$ while taking as many free diagonal shortcuts as possible.

2. The Dynamic Programming Baseline: Longest Common Subsequence (LCS)

Before exploring Myers' greedy optimization, it helps to understand the classic Longest Common Subsequence (LCS) algorithm using dynamic programming.

If you find the longest common sequence of lines shared between both files in identical order, everything else is simply an insertion or a deletion:

$$\text{Shortest Edit Distance} = (N + M) - 2 \times |LCS|$$

A Zero-Dependency LCS Implementation

Here is how we built the foundational LCS matrix in browser memory using typed arrays (Int32Array) for cache-friendly memory locality:

/** * Computes the Longest Common Subsequence (LCS) edit matrix. * Implemented with typed Int32Arrays to prevent V8 memory thrashing. */ function computeLCSMatrix(arr1, arr2) { const m = arr1.length; const n = arr2.length; // Allocate matrix using flat typed buffers const dp = Array.from({ length: m + 1 }, () => new Int32Array(n + 1)); // Build LCS table for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (arr1[i] === arr2[j]) { dp[i + 1][j + 1] = dp[i][j] + 1; // Take diagonal shortcut } else { dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]); } } } // Backtrack from (m, n) to (0, 0) to assemble the shortest edit script const editScript = []; let x = m; let y = n; while (x > 0 || y > 0) { if (x > 0 && y > 0 && arr1[x - 1] === arr2[y - 1]) { // Unchanged line editScript.unshift({ type: 'equal', value: arr1[x - 1] }); x--; y--; } else if (y > 0 && (x === 0 || dp[x][y - 1] >= dp[x - 1][y])) { // Line inserted into modified file editScript.unshift({ type: 'add', value: arr2[y - 1] }); y--; } else { // Line deleted from original file editScript.unshift({ type: 'delete', value: arr1[x - 1] }); x--; } } return { diff: editScript, similarity: ((2 * dp[m][n]) / (m + n)) * 100 }; }

This dynamic programming model runs in $O(NM)$ time and space complexity. For files with several hundred lines, it executes in under 2 milliseconds directly inside browser memory.

3. Why Myers’ $O(ND)$ Algorithm Is Revolutionary

The standard dynamic programming matrix above has an inefficiency: it computes every single cell in the $(N \times M)$ grid, even if the two files are 99% identical!

If you modify two lines in a 10,000-line codebase, an $O(NM)$ algorithm computes $10,000 \times 10,000 = 100,000,000$ operations.

Myers realized that software revisions are rarely completely rewritten; they are mostly identical with a small number of edits ($D$).

Instead of searching the entire coordinate space, Myers’ algorithm searches by increasing edit distance $D = 0, 1, 2, 3...$:

  1. Group by Diagonals ($k$): Myers defined diagonal lines across the grid using the constant $k = x - y$. Moving right (deletion) moves you to diagonal $k + 1$. Moving down (insertion) moves you to diagonal $k - 1$.
  2. Greedy Traversal: For each edit step $D$, the algorithm determines the furthest point reachable on each diagonal $k$. After taking an edit step (horizontal or vertical), it immediately slides along all available free diagonal matches (identical lines) as far as possible (a "snake").
  3. Early Termination: The moment a path reaches $(N, M)$, the algorithm halts.

Because its time complexity is $O(ND)$ (where $D$ is the number of differences), if two large files differ by only 5 lines, $D = 5$. The algorithm finishes in a fraction of a millisecond, searching only a tiny sliver along the central diagonal. This is why Git can diff massive codebases almost instantly.

4. Line-by-Line vs. Word-by-Word Granularity

When building a user-facing diff tool like our Text Diff Checker or our Universal Word Counter, an essential architectural decision is tokenization boundaries:

Line-by-Line Tokenization: text.split('\n') Word-by-Word Tokenization: text.split(/(\s+)/)
  • Line-by-Line: Ideal for source code (Python, JavaScript, Go, JSON), where formatting, line endings, and indentation scoping dictate logic.
  • Word-by-Word: Critical for prose, contract legal review, and academic essays. If an author changes one word inside a 200-word paragraph, a line-by-line diff flags the entire paragraph as deleted and re-created in green. A word-level tokenization cleanly isolates the single altered phrase.

5. The Security Imperative: Zero-Server Code Comparison

Beyond algorithmic elegance, there is a serious data security argument for in-browser diffing.

Consider what developers paste into diff checkers:

  • API access tokens and .env configuration files.
  • Proprietary algorithms and unreleased source code.
  • Database SQL dumps with customer records.
  • Pre-release legal terms and NDA contracts.

When you use conventional online diff tools, that data is transmitted across an HTTP POST request to a backend server. If that server logs requests, uses third-party analytics, or experiences a vulnerability, your confidential code is compromised.

By building on a 100% client-side architecture:

  • The array splits, the LCS matrix, and the DOM render execute in the browser's local sandbox memory.
  • Refreshing or closing the tab destroys the data from RAM.
  • There is no backend database to breach because there is no backend server involved in the computation.

6. Engineering Takeaways

  1. Reframe problems into graphs: When faced with comparative string evaluation, transforming sequence operations into pathfinding along a coordinate grid often reveals the optimal solution.
  2. Use typed arrays for numerical matrices: Allocating large 2D dynamic programming matrices using standard JavaScript arrays ([]) causes high garbage collection overhead. Pre-allocating contiguous buffers with Int32Array delivers significant runtime speedups.
  3. Keep private tools on the client: Utilities that process sensitive intellectual property should be architected to execute locally in the browser, eliminating privacy liabilities and cloud server costs simultaneously.

Resources & Open-Source Tools

How does your team handle text comparison in internal tooling? Have you implemented custom diff heuristics for domain-specific files? Share your thoughts below!