cf.completefrontend
ALGORITHMS IN FRONTEND WORK · CORE

Line-by-line text diff

Show how one text became another by keeping the longest run of shared lines and marking the rest as deleted or added.

Time O(n * m)Space O(n * m)5 practice problemsStep-through picture

The idea

A diff shows the changes between two versions of a file: lines that stayed, lines that were removed (marked -), and lines that were added (marked +). Code review tools, git diff, and snapshot tests all show diffs.

A good diff keeps as many lines as possible unchanged. The lines both versions share, in the same order, form a common subsequence: they don't have to be next to each other, but their order must be the same. The longest one is the longest common subsequence, or LCS. Every line not in it is either deleted from the old text or added in the new one, so a longer LCS means fewer marked lines.

The method here fills a table lcs[i][j]: the LCS length of the old lines from i onward and the new lines from j onward. Then it walks from the top: equal lines are kept, and otherwise it deletes or adds, whichever keeps the most shared lines ahead. Git's default diff uses Myers' algorithm, a faster way to find the same kind of shortest edit, but the idea of keeping the longest common part is the same.

An everyday example

Comparing two shopping lists

Last week's list says bread, milk, eggs. This week's says bread, eggs, jam. You want to tell someone the changes in as few words as possible. Bread and eggs are on both, in the same order, so you keep them. Milk is gone, so you say "cross out milk". Jam is new, so you say "add jam". Keeping the most shared items is what makes the list of changes short.

How the example maps to the code
In the exampleIn the code
Last week's and this week's listsThe arrays a and b
Items on both lists in the same orderThe longest common subsequence, measured by lcs
Cross out an itemPush "- " + a[i]
Add an itemPush "+ " + b[j]
Keep an itemPush " " + a[i]

From the slow way to line-by-line text diff

  1. Start with the obvious way: compare the two files line by line by position, a[0] with b[0], a[1] with b[1], and so on. Add one import line at the top of a 300-line file and every line after it shifts down by one. Now every pair differs, and the diff claims 300 changes for a one-line edit.
  2. So change the goal. Keep as many lines as possible unchanged, in the same order in both files, and mark every other line as deleted or added. If kept lines are kept, the diff has n + m - 2 * kept marked lines. The fewest changes means the most kept lines: the longest common subsequence, or LCS, of the two lists of lines.
  3. Trying every set of lines to keep would take about 2^n tries. But the best answer for "the old lines from i on and the new lines from j on" depends only on i and j. If a[i] === b[j], keep that pair and solve from i + 1, j + 1. If not, at least one of the two lines isn't kept, so take the better of skipping a[i] or skipping b[j]. There are only (n + 1) * (m + 1) such pairs, so store the answers in a table lcs, filled from the bottom-right.
  4. The table gives counts, not the diff itself. So walk it from i = 0, j = 0. Equal lines are kept and both indexes move. Otherwise step toward the neighbor that still allows the most kept lines: moving i prints - a[i], moving j prints + b[j]. On a tie, delete first, so a changed line shows as - then +. That table and walk are the line-by-line text diff.

How it works

  1. Make a table lcs with n + 1 rows and m + 1 columns of zeros. lcs[i][j] will be the LCS length of a from line i and b from line j.
  2. Fill it from the bottom-right: if a[i] === b[j], lcs[i][j] = lcs[i + 1][j + 1] + 1; otherwise it is the bigger of lcs[i + 1][j] and lcs[i][j + 1].
  3. Walk with i = 0 and j = 0 until both texts are used up.
  4. If a[i] === b[j], the line stays: push it with two spaces and move both i and j.
  5. Otherwise, if b is used up or skipping a[i] keeps at least as many shared lines (lcs[i + 1][j] >= lcs[i][j + 1]), push - a[i] and move i.
  6. Otherwise push + b[j] and move j.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function lineDiff(a, b) {
  2. const n = a.length;
  3. const m = b.length;
  4. const lcs = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
  5. for (let i = n - 1; i >= 0; i--) {
  6. for (let j = m - 1; j >= 0; j--) {
  7. lcs[i][j] = a[i] === b[j] ? lcs[i + 1][j + 1] + 1 : Math.max(lcs[i + 1][j], lcs[i][j + 1]);
  8. }
  9. }
  10. const result = [];
  11. let i = 0;
  12. let j = 0;
  13. while (i < n || j < m) {
  14. if (i < n && j < m && a[i] === b[j]) {
  15. result.push(" " + a[i]);
  16. i++;
  17. j++;
  18. } else if (j === m || (i < n && lcs[i + 1][j] >= lcs[i][j + 1])) {
  19. result.push("- " + a[i]);
  20. i++;
  21. } else {
  22. result.push("+ " + b[j]);
  23. j++;
  24. }
  25. }
  26. return result;
  27. }

How fast it is

TimeO(n * m)
Extra memoryO(n * m)

The table has one cell for each pair of lines, and each cell is filled with a single comparison. The walk takes at most n + m steps.

  • Best caseO(n * m)

    Even two identical files fill the whole table first. The walk is then only n steps, but the table already cost n * m.

  • Average caseO(n * m)

    Any pair of files: one cell per pair of lines, each filled with one comparison.

  • Worst caseO(n * m)

    Two 2,000-line files fill about 4 million cells. Time doesn't depend on how different they are, only on their sizes.

Common mistakes

  • Comparing lines by position only (a[i] with b[i]). One inserted line at the top makes every later line look changed.
  • Forgetting the extra row and column. Reading lcs[i + 1] on the last row then fails or returns undefined.
  • Reading lcs[i + 1][j] when i is already n. Check which text is used up before comparing table values.
  • Expecting one exact diff. Several diffs can be equally short; fix a tie rule if the output must be predictable.

When to use it

Look for these clues in a problem:

  • You compare two versions of a list or text and must show what was kept, removed, and added.
  • The question asks for the fewest insertions and deletions to turn one sequence into another.
  • It mentions a diff, a patch, a change summary, or how similar two texts are.
  • The order of items matters, but items can be removed from between others.

Check yourself

Answer each one in your head first, then open it.

If n = 10, m = 12, and lcs[0][0] = 7, how many - and + lines does the diff have?

8: 10 - 7 = 3 deleted lines and 12 - 7 = 5 added lines, which is n + m - 2 * 7.

Why is the table filled starting from the bottom-right?

Each cell uses the cells below it and to its right. Filling from the end means those cells are always ready when needed.

What changes if ties prefer adding over deleting?

A changed line shows as + new before - old. The diff has the same number of changes; only the order of equal-cost steps differs.

Why is comparing lines by position the wrong approach for text?

Lines get inserted and deleted, which shifts everything after them. Comparing by position then reports every shifted line as changed.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The table is correct because of how a best answer is built. If a[i] === b[j], some longest common subsequence of the two remaining parts starts with this pair: any best answer that doesn't use it can swap its first match for this pair and stay just as long. If the lines differ, no answer can match them to each other, and it can't use both of them matched elsewhere either, because those two matches would cross. So one of the lines is skipped, and the best is the larger of the two skip cells.

The fill order makes this work. Each cell needs the cells below it and to its right, so the loops run i from n - 1 down and j from m - 1 down. The extra row and column of zeros are the answer when one text has no lines left.

The walk keeps one rule: lines kept so far plus lcs[i][j] always equals lcs[0][0]. A match adds one kept line and moves to lcs[i + 1][j + 1], which is exactly one less. A delete happens only when lcs[i + 1][j] is the larger neighbor, so it equals lcs[i][j]; the same goes for an add. Every step moves i or j, so the walk ends after at most n + m steps, at the zero corner. By then exactly lcs[0][0] lines were kept, so the number of marked lines is the smallest possible.

Going deeper

3 more ideas

Why the walk gives the fewest changes

lcs[0][0] is the most lines that can be kept. Each step of the walk moves to a cell that still allows that many kept lines: matching lines add one and move diagonally, and a delete or add moves to the neighbor with the larger value. So the walk keeps exactly lcs[0][0] lines, and the number of - and + lines is n + m - 2 * lcs[0][0], the smallest possible.

How fast it is

The table has (n + 1) * (m + 1) cells and each takes O(1) to fill, so time and memory are O(n * m). For two 1,000-line files that is a million cells, which is fine. Myers' algorithm runs in O((n + m) * D), where D is the number of changed lines, which is much faster when the files are mostly the same.

Breaking ties

When deleting and adding keep the same number of shared lines, this code deletes first. That is why a changed line shows as - old then + new, like in git diff. Different tie rules give different but equally short diffs, so any test that checks exact output must say which rule to follow.

Work it by hand

Every step in a table, with why

Diff the outline of a page where nav became search and a pager was added. The tie at step 2 decides that - comes before +.

a = ["header", "nav", "list", "footer"], b = ["header", "search", "list", "pager", "footer"]

Stepija[i] vs b[j]lcs[i + 1][j] vs lcs[i][j + 1]PushedWhy
1--fill the tablelcs[0][0] = 3-The nested loops fill all 5 by 6 cells from the bottom-right. At most 3 lines can be kept: header, list, footer.
200header = headernot needed" header"Equal lines are always kept. Both i and j move on.
311nav vs search2 vs 2"- nav"Skipping either line still allows 2 kept lines. On a tie the code deletes first.
421list vs search1 vs 2"+ search"Skipping list would leave only 1 kept line ahead, but skipping search leaves 2, so search is added.
522list = listnot needed" list"Equal again: keep it.
633footer vs pager0 vs 1"+ pager"Deleting footer would keep nothing more. Adding pager keeps the chance to match footer.
734footer = footernot needed" footer"The last pair is equal. Now i = 4 and j = 5, so both texts are used up and the loop ends.

The diff is [" header", "- nav", "+ search", " list", "+ pager", " footer"]: 3 kept lines and 4 + 5 - 2 * 3 = 3 marked lines, the fewest possible.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Line-by-line text diffO(n * m)O(n * m)Files of up to a few thousand lines, or an interview, where a clear table-based answer matters most.
Myers' diffO(n · d)O(n)Real tools comparing large files with few changes. Here n is the total number of lines and d the number of changed ones.
Hirschberg's linear-space LCSO(n * m)O(n + m)The files are big enough that an n * m table doesn't fit in memory, but you still want an exact LCS.
Compare by positionO(n)O(1)Lines can't move or be inserted, like two snapshots of a fixed-size table. Otherwise one inserted line makes everything look changed.

Extra memory: O(n * m) for the lcs table, which dominates. The result has at most n + m lines. Hirschberg's method finds an equally short diff in O(n + m) memory by splitting the problem in the middle.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Line-by-line text diff and the other approaches, on a scale where each line up is 10 times more steps.
  • Line-by-line text diff, Myers' diff, Hirschberg's linear-space LCS O(n * m)
  • Compare by position O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Line-by-line text diff1001 million1 trillion
Myers' diff1001 million1 trillion
Hirschberg's linear-space LCS1001 million1 trillion
Compare by position101,0001 million

Inputs that need care

5 tricky inputs
The old text is empty: a = [], b = ["x", "y"]
Only the last branch can run, so the result is ["+ x", "+ y"].
The new text is empty: a = ["x", "y"], b = []
j === m from the start, so every line is deleted: ["- x", "- y"].
No line in common: a = ["a", "b"], b = ["c", "d"]
Every cell is 0, so every step is a tie and deletes win: - a, - b, + c, + d. All deletions come first.
Many repeated lines, like closing braces }
Several LCSs have the same length, and the tie rule can match a } from one function with a } from another. The diff is still the shortest, but may be hard to read. Patience diff fixes this by first matching lines that appear only once.
Whitespace or line-ending changes, like "foo" vs "foo ", or \r\n vs \n
The strings differ, so the line shows as - and +. Split with /\r?\n/, and trim lines before comparing if whitespace shouldn't count, like git diff -w.

Variations and follow-ups

Twists interviewers add

Myers' algorithm

Instead of filling the whole table, Myers' method looks for the shortest edit by trying 0 changes, then 1, then 2, and so on, skipping over runs of equal lines without counting them as changes. Its time is O((n + m) * D) for D changed lines, so two nearly equal files are very fast. Git and Jest's diff-sequences use it.

Patience and histogram diff

git diff --patience first matches lines that appear exactly once in both files, like function names, and diffs the gaps between them. --histogram is a faster relative of it. Both give diffs that people find easier to read for code full of repeated lines.

Word or character diff

The same method works on any list of tokens. Split each changed line into words or characters and diff those, to highlight exactly which word changed inside a - and + pair, as code review tools do.

Turning the diff into hunks

Real diff output groups changes into hunks: runs of changes with a few kept lines around them for context, and headers like @@ -12,7 +12,8 @@ giving the line numbers. Long runs of kept lines are hidden.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "show what changed", "fewest insertions and deletions", "diff", or "longest common subsequence". If replacing a line also counts as one step, it's edit distance instead.
  • Explain in two parts: first the recurrence for lcs[i][j] and why it's filled from the bottom-right, then the walk and its tie rule. Say the formula for the number of changes: n + m - 2 * lcs[0][0].
  • Test by hand: an empty old text, an empty new text, two identical texts, and one changed line in the middle. The changed line should come out as - then +.
  • Expect the follow-up "what about two 100,000-line files?". The table would have 10 billion cells, which is too big. Answer with Myers' algorithm, which is fast when few lines changed, or Hirschberg's method for linear memory.

Where frontend code uses it

The same idea in real UI code
  • git diff and the code review views on GitHub and GitLab show line diffs computed with Myers' algorithm by default.
  • Jest's snapshot and toEqual failure messages use the diff-sequences package, an implementation of Myers' algorithm, to show - expected and + received lines.
  • Collaborative editors, version history panels in document and design tools, and "compare revisions" views in content systems all show diffs like this.

Related algorithms