List diffing for animated UI updates

Turn old and new lists into deletes, inserts, moves and reloads, in O(n log n).

Part 1 of 5

Basics

The concepts this component is built on. With these in mind, every line of the solution has a reason.

1.1Key concepts

One idea per card, in the order the solution uses them.

01Why diff at all

Replacing the whole list makes it flash and loses the scroll position. Telling the list exactly what changed lets it animate only those rows.

02Identity vs content

The id says which item a row is; the fields say what it shows. The same id with new content is a reload, not a delete plus an insert.

03Moves and the longest increasing subsequence

Among items present in both lists, the largest group still in the same relative order can stay put. Everything else counts as moved.

04Patience sorting

A way to find that longest increasing subsequence in O(n log n), using a binary search over the smallest tail of each length.

Part 2 of 5

Question

What exactly you are asked to build, what must be true when you are done, and what to ask before you start.

2.1Prompt

The question as the interviewer asks it, and the requirements to check your solution against.

Interviewer

When the feed refreshes, we reload the whole list and the UI flashes. Compute the minimal batch update between the old and new lists so the list can animate.

Requirements

  • Match items by identity
  • Report deletions by old index and insertions by new index
  • Report moves, but as few as possible
  • Report content changes as reloads

2.2Clarify first

Questions worth asking, and the answers this interviewer gives.

You askInterviewer answers
Are ids unique?Yes, within one list.
Do moves matter?Yes: moving every row looks broken. Keep the most rows still.
Part 3 of 5

Detailed answer

The design decisions, the complete Kotlin solution, and a walk through it one block at a time.

3.1Design decisions

Settle these before writing code; each one shows up in the solution.

Identity map

Old id → index makes every lookup O(1). The caller passes idOf, so any type works.

LIS keeps rows still

Among surviving items, the longest increasing run of old indices is the largest set that keeps order; everything else moved.

Patience sorting

LIS in O(n log n) with a predecessor array to rebuild the sequence.

3.2Solution

Complete, compiling Kotlin with coroutines, built with warnings as errors and covered by tests/mobile/MobileTests.kt. The Java and TypeScript tabs do the same job with each language's own tools: Java compiled and run in our tests, TypeScript run in our tests.

KotlinJavaTypeScript
ListDiff.ktKotlinCopy
1/**2 * The changes a list needs to animate from old to new: deletions (old indices),3 * insertions (new indices), moves and in-place reloads.4 */5data class ListDiff(6  val deletes: List<Int> = emptyList(),7  val inserts: List<Int> = emptyList(),8  val moves: List<Move> = emptyList(),9  val reloads: List<Int> = emptyList(),                // new indices whose content changed10) {11  data class Move(val from: Int, val to: Int)12 13  val isEmpty: Boolean get() = deletes.isEmpty() && inserts.isEmpty() && moves.isEmpty() && reloads.isEmpty()14}15 16/**17 * O(n log n) diff keyed by identity. Items that keep their relative order stay put18 * (the longest increasing subsequence); only the others are reported as moves.19 */20fun <T, ID> diff(old: List<T>, new: List<T>, idOf: (T) -> ID): ListDiff {21  val oldIndex = HashMap<ID, Int>()22  old.forEachIndexed { i, item -> oldIndex[idOf(item)] = i }23  val newIds = new.mapTo(HashSet(), idOf)24  val deletes = old.indices.filter { idOf(old[it]) !in newIds }25 26  val inserts = mutableListOf<Int>()27  val reloads = mutableListOf<Int>()28  val survivors = mutableListOf<Pair<Int, Int>>()      // (old index, new index) in new order29  new.forEachIndexed { j, item ->30    val i = oldIndex[idOf(item)]31    if (i == null) {32      inserts += j33    } else {34      survivors += i to j35      if (old[i] != item) reloads += j36    }37  }38 39  val stay = longestIncreasingSubsequence(survivors.map { it.first }).toHashSet()40  val moves = survivors.filterIndexed { k, _ -> k !in stay }.map { (from, to) -> ListDiff.Move(from, to) }41  return ListDiff(deletes, inserts, moves, reloads)42}43 44/** Indices (into [values]) of one longest strictly increasing subsequence. Patience sorting. */45fun longestIncreasingSubsequence(values: List<Int>): List<Int> {46  val tails = mutableListOf<Int>()                     // index of the smallest tail for each length47  val previous = IntArray(values.size) { -1 }48  values.forEachIndexed { i, v ->49    var lo = 050    var hi = tails.size51    while (lo < hi) {                                  // first tail >= v52      val mid = (lo + hi) ushr 153      if (values[tails[mid]] < v) lo = mid + 1 else hi = mid54    }55    if (lo > 0) previous[i] = tails[lo - 1]56    if (lo == tails.size) tails += i else tails[lo] = i57  }58  val out = ArrayDeque<Int>()59  var k = tails.lastOrNull() ?: -160  while (k >= 0) {61    out.addFirst(k)62    k = previous[k]63  }64  return out65}
65 linesUTF-8Kotlin
ListDiff.javaJavaCopy
1import java.util.ArrayDeque;2import java.util.ArrayList;3import java.util.Deque;4import java.util.HashMap;5import java.util.HashSet;6import java.util.List;7import java.util.Map;8import java.util.Set;9import java.util.function.Function;10 11/**12 * The changes a list needs to animate from old to new: deletions (old indices),13 * insertions (new indices), moves and in-place reloads.14 */15public record ListDiff(List<Integer> deletes, List<Integer> inserts, List<Move> moves, List<Integer> reloads) {16  public record Move(int from, int to) {}17 18  public boolean isEmpty() {19    return deletes.isEmpty() && inserts.isEmpty() && moves.isEmpty() && reloads.isEmpty();20  }21 22  /**23   * O(n log n) diff keyed by identity. Items that keep their relative order stay put24   * (the longest increasing subsequence); only the others are reported as moves.25   */26  public static <T, ID> ListDiff diff(List<T> old, List<T> next, Function<T, ID> idOf) {27    Map<ID, Integer> oldIndex = new HashMap<>();28    for (int i = 0; i < old.size(); i++) oldIndex.put(idOf.apply(old.get(i)), i);29    Set<ID> newIds = new HashSet<>();30    for (T item : next) newIds.add(idOf.apply(item));31    List<Integer> deletes = new ArrayList<>();32    for (int i = 0; i < old.size(); i++) if (!newIds.contains(idOf.apply(old.get(i)))) deletes.add(i);33 34    List<Integer> inserts = new ArrayList<>();35    List<Integer> reloads = new ArrayList<>();36    List<int[]> survivors = new ArrayList<>();         // {old index, new index} in new order37    for (int j = 0; j < next.size(); j++) {38      T item = next.get(j);39      Integer i = oldIndex.get(idOf.apply(item));40      if (i == null) {41        inserts.add(j);42      } else {43        survivors.add(new int[] {i, j});44        if (!old.get(i).equals(item)) reloads.add(j);45      }46    }47 48    List<Integer> oldIndices = new ArrayList<>();49    for (int[] s : survivors) oldIndices.add(s[0]);50    Set<Integer> stay = new HashSet<>(longestIncreasingSubsequence(oldIndices));51    List<Move> moves = new ArrayList<>();52    for (int k = 0; k < survivors.size(); k++) {53      if (!stay.contains(k)) moves.add(new Move(survivors.get(k)[0], survivors.get(k)[1]));54    }55    return new ListDiff(deletes, inserts, moves, reloads);56  }57 58  /** Indices (into [values]) of one longest strictly increasing subsequence. Patience sorting. */59  public static List<Integer> longestIncreasingSubsequence(List<Integer> values) {60    List<Integer> tails = new ArrayList<>();           // index of the smallest tail for each length61    int[] previous = new int[values.size()];62    java.util.Arrays.fill(previous, -1);63    for (int i = 0; i < values.size(); i++) {64      int v = values.get(i);65      int lo = 0, hi = tails.size();66      while (lo < hi) {                                // first tail >= v67        int mid = (lo + hi) >>> 1;68        if (values.get(tails.get(mid)) < v) lo = mid + 1;69        else hi = mid;70      }71      if (lo > 0) previous[i] = tails.get(lo - 1);72      if (lo == tails.size()) tails.add(i);73      else tails.set(lo, i);74    }75    Deque<Integer> out = new ArrayDeque<>();76    int k = tails.isEmpty() ? -1 : tails.get(tails.size() - 1);77    while (k >= 0) {78      out.addFirst(k);79      k = previous[k];80    }81    return new ArrayList<>(out);82  }83}
83 linesUTF-8Java
ListDiff.tsTypeScriptCopy
1export interface Move {2  from: number;3  to: number;4}5 6/**7 * The changes a list needs to animate from old to new: deletions (old indices),8 * insertions (new indices), moves and in-place reloads.9 */10export interface ListDiff {11  deletes: number[];12  inserts: number[];13  moves: Move[];14  reloads: number[];                                   // new indices whose content changed15}16 17export const isEmpty = (d: ListDiff) => !d.deletes.length && !d.inserts.length && !d.moves.length && !d.reloads.length;18 19/**20 * O(n log n) diff keyed by identity. Items that keep their relative order stay put21 * (the longest increasing subsequence); only the others are reported as moves.22 */23export function diff<T, ID>(old: T[], next: T[], idOf: (t: T) => ID, same: (a: T, b: T) => boolean = (a, b) => JSON.stringify(a) === JSON.stringify(b)): ListDiff {24  const oldIndex = new Map<ID, number>();25  old.forEach((item, i) => oldIndex.set(idOf(item), i));26  const newIds = new Set(next.map(idOf));27  const deletes = old.map((_, i) => i).filter((i) => !newIds.has(idOf(old[i])));28 29  const inserts: number[] = [];30  const reloads: number[] = [];31  const survivors: [number, number][] = [];            // (old index, new index) in new order32  next.forEach((item, j) => {33    const i = oldIndex.get(idOf(item));34    if (i === undefined) {35      inserts.push(j);36    } else {37      survivors.push([i, j]);38      if (!same(old[i], item)) reloads.push(j);39    }40  });41 42  const stay = new Set(longestIncreasingSubsequence(survivors.map((s) => s[0])));43  const moves = survivors.filter((_, k) => !stay.has(k)).map(([from, to]) => ({ from, to }));44  return { deletes, inserts, moves, reloads };45}46 47/** Indices (into [values]) of one longest strictly increasing subsequence. Patience sorting. */48export function longestIncreasingSubsequence(values: number[]): number[] {49  const tails: number[] = [];                          // index of the smallest tail for each length50  const previous = new Array<number>(values.length).fill(-1);51  values.forEach((v, i) => {52    let lo = 0;53    let hi = tails.length;54    while (lo < hi) {                                  // first tail >= v55      const mid = (lo + hi) >>> 1;56      if (values[tails[mid]] < v) lo = mid + 1;57      else hi = mid;58    }59    if (lo > 0) previous[i] = tails[lo - 1];60    if (lo === tails.length) tails.push(i);61    else tails[lo] = i;62  });63  const out: number[] = [];64  let k = tails.length ? tails[tails.length - 1] : -1;65  while (k >= 0) {66    out.unshift(k);67    k = previous[k];68  }69  return out;70}
70 linesUTF-8TypeScript

3.3Line-by-line walkthrough

The same code in the order you would explain it in the room. The line numbers follow the Kotlin file; the Java and TypeScript tabs above have the same steps in the same order.

1

Index the old list

Map old ids to positions; anything whose id is not in the new list is a delete.

ListDiff.ktKotlinCopy
21  val oldIndex = HashMap<ID, Int>()22  old.forEachIndexed { i, item -> oldIndex[idOf(item)] = i }23  val newIds = new.mapTo(HashSet(), idOf)24  val deletes = old.indices.filter { idOf(old[it]) !in newIds }
lines 21–24UTF-8Kotlin
2

Walk the new list

Unknown ids are inserts; known ids are survivors, and changed content (data class equality) means a reload.

ListDiff.ktKotlinCopy
26  val inserts = mutableListOf<Int>()27  val reloads = mutableListOf<Int>()28  val survivors = mutableListOf<Pair<Int, Int>>()      // (old index, new index) in new order29  new.forEachIndexed { j, item ->30    val i = oldIndex[idOf(item)]31    if (i == null) {32      inserts += j33    } else {34      survivors += i to j35      if (old[i] != item) reloads += j36    }37  }
lines 26–37UTF-8Kotlin
3

Moves are what LIS leaves out

Survivors on the longest increasing run of old indices stay; the rest are moves.

ListDiff.ktKotlinCopy
39  val stay = longestIncreasingSubsequence(survivors.map { it.first }).toHashSet()40  val moves = survivors.filterIndexed { k, _ -> k !in stay }.map { (from, to) -> ListDiff.Move(from, to) }41  return ListDiff(deletes, inserts, moves, reloads)
lines 39–41UTF-8Kotlin
4

Patience sorting

Binary search the first tail ≥ value; track predecessors to rebuild the sequence.

ListDiff.ktKotlinCopy
46  val tails = mutableListOf<Int>()                     // index of the smallest tail for each length47  val previous = IntArray(values.size) { -1 }48  values.forEachIndexed { i, v ->49    var lo = 050    var hi = tails.size51    while (lo < hi) {                                  // first tail >= v52      val mid = (lo + hi) ushr 153      if (values[tails[mid]] < v) lo = mid + 1 else hi = mid54    }55    if (lo > 0) previous[i] = tails[lo - 1]56    if (lo == tails.size) tails += i else tails[lo] = i57  }
lines 46–57UTF-8Kotlin
5

Rebuild the sequence

Follow predecessors back from the last tail, adding to the front of an ArrayDeque.

ListDiff.ktKotlinCopy
58  val out = ArrayDeque<Int>()59  var k = tails.lastOrNull() ?: -160  while (k >= 0) {61    out.addFirst(k)62    k = previous[k]63  }64  return out
lines 58–64UTF-8Kotlin

Complexity: O(n log n) time, O(n) space

Part 4 of 5

Q&A

The questions interviewers ask after the code works. Answer out loud, then open.

4.1Follow-up questions

Why not Myers' diff?
Myers minimises edits for sequences without identity; with stable ids, the map plus LIS is simpler and faster. DiffUtil uses Myers plus move detection.
What does the platform give you?
DiffUtil / ListAdapter on Android and diffable data sources on iOS do this for you; this is how they work underneath.
Part 5 of 5

Extra depth

The cases that break naive solutions, how the same design looks on iOS, and what to practise next.

5.1Edge cases

Say these before the interviewer does.

Show detailsHide details
  • Identical lists produce an empty diff
  • Everything replaced
  • Pure reorder
  • Duplicate ids (reject or dedupe first)

5.2On iOS

The same design in Swift and Apple's frameworks.

Show detailsHide details
ApproachSwift / iOS
Diffable data sourcesApply an NSDiffableDataSourceSnapshot of item identifiers; reconfigureItems for content changes.
SwiftUIForEach over Identifiable items animates inserts, deletes and moves by id.