Skip to content
AfluidityAlgorithm Atlas
Pattern MatchingAll categories
CoreConcept & Pseudocode EntryAI Reviewed (ai-reviewed)

Myers Diff Algorithm

Computes the shortest edit script (minimum insertions and deletions) between two files or sequences in O((N + M) D) time by greedily advancing furthest-reaching paths along diagonals of the edit graph.

Explore relationshipsOpen 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Pattern Matching
Difficulty
Intermediate
Family
Sequence Alignment & Diff
Tier
Core
Status
Reviewed
Review
AI Reviewed
Sources
1
Formulas
1
Relationships
1
Code example
Not ready
Visualization
Ready
Aliases
Myers Shortest Edit Script, O(ND) File Diff, Git Default Diff

Overview

Eugene Myers's O(ND) diff algorithm (the default diff engine in Git and GNU diff) frames sequence comparison as finding a minimum-cost path from (0,0) to (N,M) in an edit graph where diagonal moves (matching lines/tokens) have cost 0 and horizontal/vertical moves (deletions/insertions) have cost 1. By tracking the furthest-reaching x-coordinate V[k] on each diagonal k = x - y for edit distance d = 0, 1, ..., D, it runs in O((N + M) D) time, which is near-linear when two file versions have few differences D.

Core Concepts

edit graph diagonals k = x - yfurthest-reaching D-path diagonal snake extensionshortest edit script (SES)

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(N + M) when D = 0

Average

O((N + M) D)

Worst

O((N + M)^2)

Space

O(D^2) for full trace or O(N + M) with linear-space middle-snake divide-and-conquer

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Myers Diff Algorithm across input scales.

Input Scale N:
JIT-compiled JS/TS (~350M primitive ops/sec)
Est. Average TimeO((N + M) D)

714.3 µs

60 FPS Frame-Safe (<16ms)~250.0k ops
Est. Worst-Case TimeO((N + M)^2)

0.2 min

Offline Batch / Timeout Risk~5.00B ops
Est. Working MemoryO(D^2) for full trace or O(N + M) with linear-space middle-snake divide-and-conquer

149.01 GB

High RAM PressureN=100,000

When to Use

  • Use Myers Diff when comparing two versions of a file, document, or list where the number of changed lines/items D is much smaller than the total length N + M.
  • Use its linear-space middle-snake variant when diffing large files in O(N + M) memory.

When Not to Use

  • Avoid when substitutions carry a custom cost different from delete + insert, or when comparing completely unrelated strings where D ~ N + M (use Levenshtein or Needleman-Wunsch).

What It Does

  • Finds the shortest edit script (minimal line/element insertions and deletions) transforming sequence A into sequence B
  • Runs in O((N + M) D) time where D is the minimum edit distance, making it extremely fast when files share most lines

Use Cases

  • Source code version control diffs and patch generation (`git diff`, GNU `diff`)
  • Virtual DOM and UI list reconciliation with minimal insertions and removals
  • Document revision comparison and merge conflict detection

Inputs

  • Original sequence/lines A[0..N-1] and modified sequence/lines B[0..M-1]

Outputs

  • Shortest edit script (sequence of Keep, Insert, and Delete operations) and edit distance D

Key Formulas (1)

Edit Graph Diagonal

k = x − y, D = N + M − 2 · |LCS(A, B)|
k = x - y, D = N + M - 2 * |LCS(A, B)|

Relates shortest edit script distance D (insertions + deletions) to the longest common subsequence.

Pseudocode

  1. 1.Initialize V[-MAX..MAX] = 0 with V[1] = 0, where MAX = N + M
  2. 2.For edit distance d from 0 to MAX:
  3. 3. For diagonal k from -d to +d step 2:
  4. 4. If k == -d or (k != d and V[k - 1] < V[k + 1]): x = V[k + 1] (move down: insertion)
  5. 5. Else: x = V[k - 1] + 1 (move right: deletion)
  6. 6. Set y = x - k
  7. 7. While x < N and y < M and A[x] == B[y]: x += 1; y += 1 (follow diagonal snake)
  8. 8. Set V[k] = x; if x >= N and y >= M, backtrack through saved V traces to emit the Shortest Edit Script

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

  1. Initialize V[-MAX..MAX] = 0 with V[1] = 0, where MAX = N + M
  2. For edit distance d from 0 to MAX:
  3. For diagonal k from -d to +d step 2:
  4. If k == -d or (k != d and V[k - 1] < V[k + 1]): x = V[k + 1] (move down: insertion)
  5. Else: x = V[k - 1] + 1 (move right: deletion)
  6. Set y = x - k
  7. While x < N and y < M and A[x] == B[y]: x += 1; y += 1 (follow diagonal snake)
  8. Set V[k] = x; if x >= N and y >= M, backtrack through saved V traces to emit the Shortest Edit Script

Canonical Example

Input
A = ['a', 'b', 'c'], B = ['a', 'x', 'c']
Output
Keep 'a', Delete 'b', Insert 'x', Keep 'c' (edit distance D = 2)
Explanation
Myers advances along diagonal 0 for 'a', takes one right step (-'b') and one down step (+'x'), then slides along diagonal 0 for 'c'.

Implementation Notes

  • Hash each line to an integer ID first so line equality checks inside the inner snake loop take O(1) time.

Common Pitfalls

  • Indexing array V[k] without an offset of maxD, since diagonal k = x - y ranges from -D to +D.
  • Storing full V snapshots for all D steps on huge dissimilar files without switching to the linear-space middle-snake recursion.

Interactive Mechanism Walkthrough & State Debugger

Sequence Window & Automaton Alignment
Input:ABABABCABAB
Window:ABAB
shift offset s0
window T[s..s+m]"ABAB"
pattern P"ABAB"
alignmentExact Match ✓
Step 1 of 8: Initialize V[-MAX..MAX] = 0 with V[1] = 0, where MAX = N + M

Sources (1)

What each reference supports for this entry.

Myers (1986) — An O(ND) Difference Algorithm and Its Variations

Paper

Algorithmica paper introducing the O(ND) furthest-reaching diagonal diff algorithm.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Improves onLongest Common Subsequence

Pattern Matching · Core

Solves the dual LCS/diff problem in O((N + M) D) output-sensitive time instead of always filling an O(N M) table.

Compare with this

Relationships

View full relationship page
Improves onLongest Common Subsequence

Solves the dual LCS/diff problem in O((N + M) D) output-sensitive time instead of always filling an O(N M) table.

Related Algorithms

Longest Common SubsequenceLevenshtein DistanceHirschberg Algorithm

Tags

Pattern MatchingDiffEdit DistanceDynamic Programming