Diff Algorithm: LIS Step-by-Step Derivation and the Dual Role of key

Chapter 15: The Diff Algorithm — LIS Step-by-Step and the Dual Role of key

Vue 3's diff algorithm has an O(n log n) worst case, while React's traditional tree diff has an O(n³) worst case — but Vue 3's Block Tree design brings the typical real-world diff cost close to O(k), where k is the number of actually changed dynamic nodes, completely independent of the total template node count.

Core question of this chapter: When a list is reordered, how does Vue transform the old DOM into the new DOM using the minimum number of operations? What role does the Longest Increasing Subsequence play?

After reading this chapter you will understand:

• The two prerequisites for Vue 3's diff (Block Tree + patchFlag)
• What each of the five diff steps does concretely
• The complete step-by-step derivation of the LIS algorithm (O(n log n))
• The dual role of key at compile time and at runtime
• Why using index as a key causes hidden disasters

Level 1 · What You Need to Know (1–3 Years Experience)

The Prerequisite: Most Nodes Don't Need to Be Diffed

To understand Vue 3's diff, first understand what it does not diff.

Vue 3's compiler analyzes templates and collects all dynamic nodes (nodes with variable bindings) into an array called dynamicChildren. This design is called the Block Tree.

<template>
  <div>                    <!-- Block root -->
    <h1>Title</h1>         <!-- static, not in dynamicChildren -->
    <p>{{ text }}</p>      <!-- dynamic, in dynamicChildren -->
    <span class="box">Description</span>  <!-- static, not in dynamicChildren -->
    <img :src="imgUrl" />                 <!-- dynamic, in dynamicChildren -->
  </div>
</template>

During updates, the renderer diffs only the 2 nodes in dynamicChildren, not all 5 nodes in the template. Static content is completely skipped.

For a component with 1,000 nodes and only 3 dynamic ones, Block Tree reduces the diff cost from O(1000) to O(3).

What key Is: One Answer for Two Different Scenarios

Scenario 1: v-for lists

Without a key, Vue reuses by position: old item 1 is matched with new item 1, old item 2 with new item 2, etc. If the list is reversed, every node is re-rendered.

With a key, Vue reuses by key value: old key="3" is matched with new key="3", regardless of position changes. If the list is reversed, only DOM nodes need to be moved — content does not need to be re-rendered.

Scenario 2: Conditional rendering

<template>
  <!-- Problem: switching preserves the old input value -->
  <input v-if="isLogin" placeholder="Username" />
  <input v-else placeholder="Email" />

  <!-- Solution: key forces Vue to destroy the old node and create a new one -->
  <input v-if="isLogin" key="login" placeholder="Username" />
  <input v-else key="register" placeholder="Email" />
</template>

Practical guidelines:

Why index as key Is Dangerous

<template>
  <ul>
    <li v-for="(item, index) in list" :key="index">
      <input v-model="item.checked" />
      {{ item.name }}
    </li>
  </ul>
</template>

<script setup>
const list = ref([
  { id: 1, name: 'Apple', checked: false },
  { id: 2, name: 'Banana', checked: true },
  { id: 3, name: 'Orange', checked: false },
])

function removeFirst() {
  list.value.shift()
}
</script>

After calling removeFirst():

Before deletion:
  key=0 → Apple   (input: unchecked)
  key=1 → Banana  (input: checked)
  key=2 → Orange  (input: unchecked)

Expected result after deletion:
  key=0 → Banana  (input: checked)    ← should be checked
  key=1 → Orange  (input: unchecked)

Vue's actual diff behavior (using index as key):
  Old key=0 (Apple) matches new key=0 (Banana) → reuse old DOM, only update text
  Old key=1 (Banana) matches new key=1 (Orange) → reuse old DOM, only update text
  Old key=2 (Orange) has no match → delete

Result:
  The li at key=0 reused Apple's DOM: the input's checked state is still false!
  Displays "Banana" but the input is unchecked — state is corrupted!

Root cause: index has no semantic meaning — it represents only a position, not "who is who".

Level 2 · How It Actually Works (3–5 Years Experience)

Five-Step Diff Flow: Complete Diagram

Vue 3's core diff function is patchKeyedChildren, which processes keyed lists. The flow has five steps:

Example old and new node arrays:
  Old: [A, B, C, D, E, F, G]
  New: [A, B, D, F, E, C, H, G]

────────────────────────────────────────────────────────
Step 1: Sync from start (skip identical prefix, left to right)
────────────────────────────────────────────────────────

  Old: [A, B, C, D, E, F, G]
        ↑                         i = 0
  New: [A, B, D, F, E, C, H, G]
        ↑

  Compare: A == A? Yes. patch, i++
  Compare: B == B? Yes. patch, i++
  Compare: C == D? No. Stop.

  Result: i = 2, A and B are handled.

────────────────────────────────────────────────────────
Step 2: Sync from end (skip identical suffix, right to left)
────────────────────────────────────────────────────────

  Old: [A, B, C, D, E, F, G]
                           ↑      e1 = 6
  New: [A, B, D, F, E, C, H, G]
                              ↑   e2 = 7

  Compare: G == G? Yes. patch, e1--, e2--
  Compare: F == H? No. Stop.

  Result: e1 = 5 (position of F), e2 = 6 (position of H)
  Suffix G is handled.

  Current state:
  Old: [A, B | C, D, E, F | G]    (unhandled range [2, 5])
  New: [A, B | D, F, E, C, H | G] (unhandled range [2, 6])

────────────────────────────────────────────────────────
Step 3: Check if old sequence is exhausted (only additions remain)
────────────────────────────────────────────────────────

  Condition: i > e1 AND i <= e2
  Current: i=2, e1=5. 2 > 5? No. Skip this step.

────────────────────────────────────────────────────────
Step 4: Check if new sequence is exhausted (only deletions remain)
────────────────────────────────────────────────────────

  Condition: i > e2 AND i <= e1
  Current: i=2, e2=6. 2 > 6? No. Skip this step.

────────────────────────────────────────────────────────
Step 5: Handle the disordered middle section
────────────────────────────────────────────────────────

  Old unhandled range: [C, D, E, F] (positions 2–5)
  New unhandled range: [D, F, E, C, H] (positions 2–6)

  5a. Build key → index map for new nodes:
      { D:2, F:3, E:4, C:5, H:6 }

  5b. Traverse old nodes, look up reusable nodes in the map:
      C → found, new position 5, mark reusable, record newIndexToOldIndexMap[5-2] = 2+1 = 3
      D → found, new position 2, mark reusable, record newIndexToOldIndexMap[2-2] = 3+1 = 4
      E → found, new position 4, mark reusable, record newIndexToOldIndexMap[4-2] = 4+1 = 5
      F → found, new position 3, mark reusable, record newIndexToOldIndexMap[3-2] = 5+1 = 6
      (H does not exist in old nodes → will be mounted as a new node)

  newIndexToOldIndexMap = [4, 6, 5, 3, 0]
  (0 means "this is a new node, needs mounting")

  5c. Compute LIS (Longest Increasing Subsequence):
      Input: [4, 6, 5, 3, 0]
      LIS: [4, 5] or [4, 6], length 2
      LIS positions: [0, 2] or [0, 1]

      LIS tells us: nodes at those positions are "already in correct relative order"
      Only move the others.

  5d. Traverse new unhandled range from back to front, move or mount:
      H (newIndexToOldIndexMap=0) → new node, mount
      C (not in LIS) → move before F
      E (in LIS, position stable) → do not move
      F (not in LIS) → move before E
      D (in LIS, position stable) → do not move

Complete Step-by-Step Derivation of LIS

Input: [5, 3, 4, 0, 7, 2, 1, 6]

Goal: Find the longest increasing subsequence and record the positions of those elements in the original array.

Algorithm uses two helper arrays

• tails[]: stores the smallest tail value for each known LIS of a given length
• predecessor[]: records each element's predecessor position (for path reconstruction)

Step-by-step trace (Patience Sorting + Binary Search)

Initial: tails = [], predecessor = []

Element 5 (position 0):
  tails is empty, append directly. tails = [5]
  position[0] = 0 (ends at tails index 0)

Element 3 (position 1):
  3 < tails[0]=5, binary search → position 0, replace. tails = [3]
  position[1] = 0

Element 4 (position 2):
  4 > tails[0]=3, append. tails = [3, 4]
  position[2] = 1
  predecessor[2] = 1 (predecessor is element 3 at position 1)

Element 0 (position 3):
  0 < tails[0]=3, binary search → position 0, replace. tails = [0, 4]
  position[3] = 0

Element 7 (position 4):
  7 > tails[1]=4, append. tails = [0, 4, 7]
  position[4] = 2
  predecessor[4] = 2 (predecessor is element 4 at position 2)

Element 2 (position 5):
  tails[0]=0 < 2 <= tails[1]=4, binary search → position 1, replace. tails = [0, 2, 7]
  position[5] = 1
  predecessor[5] = 3 (predecessor is element 0 at position 3)

Element 1 (position 6):
  tails[0]=0 < 1 <= tails[1]=2, binary search → position 1, replace. tails = [0, 1, 7]
  position[6] = 1
  predecessor[6] = 3 (predecessor is element 0 at position 3)

Element 6 (position 7):
  tails[1]=1 < 6 <= tails[2]=7, binary search → position 2, replace. tails = [0, 1, 6]
  position[7] = 2
  predecessor[7] = 6 (predecessor is element 1 at position 6)

Backtracking to reconstruct the LIS path

Final tails = [0, 1, 6], length 3 (LIS length is 3)
Last element confirmed in LIS tail: position 7 (value 6)

Backtrack:
  7 (value 6) ← predecessor[7] = 6 (value 1)
  6 (value 1) ← predecessor[6] = 3 (value 0)
  3 (value 0) ← predecessor[3] = -1 (no predecessor, start)

LIS original array positions (reversed): 3, 6, 7
LIS values: 0, 1, 6

Verify: 0 < 1 < 6, it is increasing. ✓

How LIS Is Used in Vue's Diff

Meaning of LIS: nodes at LIS positions are "already in correct relative order"
Only nodes outside the LIS need to be moved; LIS nodes stay put.

For newIndexToOldIndexMap = [4, 6, 5, 3, 0]:
  LIS positions: [0, 1] (values [4, 6])
  → D (position 2 in new) and F (position 3 in new) do not need to move
  → C (position 5 in new) needs to move
  → E (position 4 in new) needs to move
  → H (position 6 in new, value 0) needs to be mounted

  Final operations: mount H, move C, move E (D and F stay)
  Only 3 DOM operations instead of 5

Unkeyed Diff: Comparison by Position

Lists without keys (or deliberately without keys) use patchUnkeyedChildren:

function patchUnkeyedChildren(c1, c2, container, anchor) {
  const oldLength = c1.length
  const newLength = c2.length
  const commonLength = Math.min(oldLength, newLength)

  // Compare one-to-one by position
  for (let i = 0; i < commonLength; i++) {
    patch(c1[i], c2[i], container, anchor)
  }

  if (oldLength > newLength) {
    // Old has extra nodes, unmount them
    unmountChildren(c1, commonLength)
  } else {
    // New has extra nodes, mount them
    mountChildren(c2, container, anchor, commonLength)
  }
}

This algorithm is simple and runs in O(n) time, with no reuse optimization. It is suitable for scenarios with a small number of nodes that do not contain stateful child components.

The Dual Role of key: Compile Time and Runtime

Role of key in the compiler (static analysis phase):

<template>
  <!-- v-for with key: compiles to KEYED_FRAGMENT -->
  <div v-for="item in list" :key="item.id">{{ item.name }}</div>

  <!-- v-for without key: compiles to UNKEYED_FRAGMENT -->
  <div v-for="item in list">{{ item.name }}</div>
</template>

Compiled output (simplified):
  // with key
  createVNode(Fragment, null, renderList(list, item =>
    createElementVNode('div', { key: item.id }, item.name)
  ), PatchFlags.KEYED_FRAGMENT)  ← bit 7 of patchFlag

  // without key
  createVNode(Fragment, null, renderList(list, item =>
    createElementVNode('div', null, item.name)
  ), PatchFlags.UNKEYED_FRAGMENT)  ← bit 8 of patchFlag

Different patchFlags → different diff functions at runtime:
  KEYED_FRAGMENT   → patchKeyedChildren()    (five-step flow)
  UNKEYED_FRAGMENT → patchUnkeyedChildren()  (position-based)

Role of key in runtime diff:

Core code of step 5 (simplified):
  // Build key → new position map for new nodes
  const keyToNewIndexMap = new Map()
  for (let i = s2; i <= e2; i++) {
    const newChild = c2[i]
    if (newChild.key != null) {
      keyToNewIndexMap.set(newChild.key, i)
    }
  }

  // Traverse old nodes, look up in the map
  for (let i = s1; i <= e1; i++) {
    const oldChild = c1[i]
    const newIndex = keyToNewIndexMap.get(oldChild.key)
    if (newIndex === undefined) {
      unmount(oldChild)  // Old node not in new sequence → unmount
    } else {
      newIndexToOldIndexMap[newIndex - s2] = i + 1  // Record reuse relationship
      patch(oldChild, c2[newIndex], ...)  // Reuse, update content
    }
  }

Level 3 · Design Docs and Source Code (Senior Developers)

Key Implementation of patchKeyedChildren in Source Code

// packages/runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, container, parentAnchor, ...) => {
  let i = 0
  const l2 = c2.length
  let e1 = c1.length - 1
  let e2 = l2 - 1

  // Step 1: sync from start
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = (c2[i] = optimized ? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i]))
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container, null, ...)
    } else {
      break
    }
    i++
  }

  // Step 2: sync from end
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = (c2[e2] = optimized ? cloneIfMounted(c2[e2] as VNode) : normalizeVNode(c2[e2]))
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container, null, ...)
    } else {
      break
    }
    e1--
    e2--
  }

  // Step 3: common sequence + mount
  if (i > e1) {
    if (i <= e2) {
      const nextPos = e2 + 1
      const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
      while (i <= e2) {
        patch(null, (c2[i] = ...), container, anchor, ...)
        i++
      }
    }
  }
  // Step 4: common sequence + unmount
  else if (i > e2) {
    while (i <= e1) {
      unmount(c1[i], ...)
      i++
    }
  }
  // Step 5: unknown sequence
  else {
    const s1 = i
    const s2 = i
    const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
    for (i = s2; i <= e2; i++) {
      const nextChild = (c2[i] = ...) as VNode
      if (nextChild.key != null) {
        keyToNewIndexMap.set(nextChild.key, i)
      }
    }

    let j
    let patched = 0
    const toBePatched = e2 - s2 + 1
    let moved = false
    let maxNewIndexSoFar = 0
    const newIndexToOldIndexMap = new Array(toBePatched).fill(0)

    for (i = s1; i <= e1; i++) {
      const prevChild = c1[i]
      if (patched >= toBePatched) {
        unmount(prevChild, ...)
        continue
      }
      let newIndex
      if (prevChild.key != null) {
        newIndex = keyToNewIndexMap.get(prevChild.key)
      } else {
        for (j = s2; j <= e2; j++) {
          if (newIndexToOldIndexMap[j - s2] === 0 &&
              isSameVNodeType(prevChild, c2[j] as VNode)) {
            newIndex = j
            break
          }
        }
      }
      if (newIndex === undefined) {
        unmount(prevChild, ...)
      } else {
        newIndexToOldIndexMap[newIndex - s2] = i + 1
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex
        } else {
          moved = true  // Detected need to move (new index went backwards)
        }
        patch(prevChild, c2[newIndex] as VNode, container, null, ...)
        patched++
      }
    }

    // 5.3 move and mount
    const increasingNewIndexSequence = moved
      ? getSequence(newIndexToOldIndexMap)
      : EMPTY_ARR
    j = increasingNewIndexSequence.length - 1

    for (i = toBePatched - 1; i >= 0; i--) {
      const nextIndex = s2 + i
      const nextChild = c2[nextIndex] as VNode
      const anchor = nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor

      if (newIndexToOldIndexMap[i] === 0) {
        patch(null, nextChild, container, anchor, ...)
      } else if (moved) {
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
          move(nextChild, container, anchor, MoveType.REORDER)
        } else {
          j--  // In LIS, no need to move
        }
      }
    }
  }
}

The Complete getSequence Implementation (LIS Core)

// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]): number[] {
  const p = arr.slice()    // predecessor array (path recording)
  const result = [0]       // result[i] = index in arr, arr[result[i]] is increasing
  let i, j, u, v, c
  const len = arr.length

  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {  // 0 means new node, skip
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        p[i] = j        // Record predecessor
        result.push(i)  // Append
        continue
      }
      // Binary search: find first position where arr[result[u]] >= arrI
      u = 0
      v = result.length - 1
      while (u < v) {
        c = (u + v) >> 1  // Right shift 1 = divide by 2 (floor)
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          v = c
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]  // Record predecessor
        }
        result[u] = i  // Replace
      }
    }
  }

  // Backtrack to reconstruct actual path
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

isSameVNodeType: When Can a Node Be Reused?

// packages/runtime-core/src/vnode.ts
export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
  return n1.type === n2.type && n1.key === n2.key
}

Just two lines. Same type (same kind of node) AND same key (same logical node) are both required for reuse.

This means:

• <div key="1"> vs <span key="1">: different type → cannot reuse → destroy and recreate
• <div key="1"> vs <div key="2">: different key → cannot reuse → destroy and recreate
• <div key="1"> vs <div key="1">: can reuse → only update content

Why Math.random() as key Is Worse Than No key

// Wrong: generates new keys on every render
<li v-for="item in list" :key="Math.random()">{{ item.name }}</li>

Analysis:

• No key: Vue uses patchUnkeyedChildren, reuses DOM by position; old DOM nodes are patched in place
• Random key: On every render, every node's key is different. Vue finds no matching keys in old nodes and unmounts everything, then remounts everything

Update without key ([A, B, C] → [A, B, D]):
  Position 0: patch(A, A) → DOM reused, update content
  Position 1: patch(B, B) → DOM reused, update content
  Position 2: patch(C, D) → DOM reused, only update text content
  Total: 0 DOM destroy/create operations

Update with random keys ([A, B, C] → [A, B, D]):
  Old keys = [random1, random2, random3]
  New keys = [random4, random5, random6]
  All old nodes have no matching keys → all unmounted
  All new nodes → all mounted
  Total: 3 DOM destroys + 3 DOM creates = 6 DOM operations

Level 4 · Edge Cases and Traps (Everyone)

Trap 1: Object Reference Equality Does Not Mean Node Reusability

// Wrong assumption: same object reference means no re-render
const item = reactive({ id: 1, name: 'Apple' })
const list = ref([item, item])  // same object appears twice

// In template:
// <div v-for="x in list" :key="x.id">{{ x.name }}</div>
// Both nodes have key = 1!

// Vue will warn: Duplicate keys detected
// Behavior: the second node overwrites the first; render result is unpredictable

Trap 2: Type Mismatch in key Prevents Node Reuse

// Backend returns numeric ids
const list = [{ id: 1 }, { id: 2 }]
// Template: <div v-for="item in list" :key="item.id">

// Problem: sometimes the backend API changes and ids become strings
const list2 = [{ id: '1' }, { id: '2' }]

// isSameVNodeType check:
// Old key = 1 (number) vs new key = '1' (string)
// 1 !== '1' → Vue treats these as different nodes → destroy and recreate all!

// Solution: explicitly convert key type
// :key="String(item.id)"  or  :key="Number(item.id)"

Trap 3: The moved Optimization — Not All Lists Need LIS

// Vue 3 has an early-exit optimization:
// If newIndex never goes backwards during the traversal of old nodes,
// moved = false, and LIS computation (getSequence) is skipped entirely.

// Scenario: pure addition (appending at end)
// Old: [A, B, C]  New: [A, B, C, D, E]
// After steps 1–4, D and E are mounted directly in step 3
// Step 5 doesn't need to execute at all

// Scenario: pure deletion (removing from end)
// Old: [A, B, C, D]  New: [A, B]
// After steps 1–2, C and D are unmounted directly in step 4

// Only the "reorder" scenario reaches step 5 with moved=true
// Only then is LIS computed (O(n log n))

Trap 4: The Special Semantics of key in Transition and TransitionGroup

<template>
  <!-- Wrong: no key on route change means Transition animations may not fire -->
  <Transition name="fade">
    <RouterView />
  </Transition>

  <!-- Correct: use route path as key so every route change triggers enter/leave -->
  <Transition name="fade">
    <RouterView :key="$route.fullPath" />
  </Transition>

  <!-- In TransitionGroup, key is mandatory -->
  <TransitionGroup name="list">
    <li v-for="item in list" :key="item.id">{{ item.name }}</li>
  </TransitionGroup>
  <!-- Without key, TransitionGroup cannot determine which nodes are added or removed -->
</template>

Trap 5: Fragment Diff Type and Its Relationship to v-for keys

// v-for without key → UNKEYED_FRAGMENT → patchUnkeyedChildren (by position)
// v-for with key    → KEYED_FRAGMENT   → patchKeyedChildren   (five steps)

// Mixed case:
// <template v-for="item in list">   ← outer Fragment
//   <dt :key="item.id + '-dt'">{{ item.name }}</dt>
//   <dd :key="item.id + '-dd'">{{ item.desc }}</dd>
// </template>

// The dt/dd inside each Fragment have keys, but the Fragment itself
// is one item of v-for. You need :key="item.id" on <template> itself,
// otherwise the Fragment layer uses unkeyed diff.

Trap 6: LIS Performance and Virtual Scrolling for Very Large Lists

The LIS algorithm is O(n log n), but when n = 10,000 (huge lists), even O(n log n) takes tens of milliseconds — enough to cause frame drops.

// Misconception: Vue's diff can handle any list size
// Reality: a reorder diff of 10,000 nodes may take 50–100ms on low-end devices

// Correct approach: use virtual scrolling for very large lists
// Only render DOM nodes for the visible area (typically 20–50 nodes)
// Replace content on scroll instead of rendering everything

// Recommended libraries:
// - @tanstack/vue-virtual
// - vue-virtual-scroller

// If the list is static (content never changes), use v-once to skip diff entirely:
// <li v-for="item in staticList" :key="item.id" v-once>{{ item.name }}</li>

Chapter Summary

1. Block Tree is Vue 3's biggest diff optimization: By collecting dynamic nodes into dynamicChildren at compile time, runtime diff processes only nodes that actually change, reducing the diff cost from O(total template nodes) to O(dynamic nodes).

2. The five-step flow filters progressively: Identical prefix and suffix nodes are skipped with a linear scan; only the truly disordered middle section reaches the most complex step 5 (key mapping + LIS).

3. LIS exists to minimize the number of moves: Nodes in the LIS (whose relative order is already correct) don't need to be moved; only nodes outside the LIS need DOM move operations. In the best case, all nodes are in the LIS and zero moves are required.

4. key determines diff strategy at compile time and node reuse at runtime: v-for with key generates KEYED_FRAGMENT patchFlag, triggering the five-step flow; the runtime key-to-index map makes it possible to find reusable nodes in O(n) time.

5. index as key is a structural error: It breaks key's semantic meaning (key should express "who is who," not "what position"), causing component state to mismatch rendered content during list operations like deletion or reversal. Only purely static display lists (no stateful children) can marginally tolerate index as key.