How does React's reconciliation (diffing) algorithm decide what to update? Why is it O(n) instead of O(n³), and what role do keys play?
The two heuristics behind diffing and why element type and keys determine reuse-vs-remount.
A general tree-diff (find the minimal set of edits between two trees) is O(n³) — far too slow for a UI. React makes it O(n) with two heuristics that trade theoretical minimality for speed. HEURISTIC 1 — element TYPE: React compares elements at the same position. If the type differs (a <div> became a <span>, or ComponentA became ComponentB), React does NOT try to diff their subtrees — it unmounts the old tree entirely (destroying its DOM and state) and builds the new one from scratch. If the type is the SAME, React keeps the DOM node, patches only the changed attributes/props, and recurses into children. This is why a conditional that swaps component type resets all state below it, and why deliberately CHANGING a key (or type) is the idiomatic way to force a remount/reset. HEURISTIC 2 — KEYS for lists: within a set of siblings, React needs to know which child is which across renders. Without keys it matches by index, so inserting or reordering makes every position 'change type-compatibly' and React patches the wrong nodes — state and DOM attach to the wrong item, causing the classic 'input value stuck on the wrong row' bug. A stable, unique key (a data id, not the array index) lets React match a child to its previous instance regardless of position, so it moves DOM nodes instead of rebuilding them. Index-as-key is only safe for a static list that never reorders, inserts, or deletes. Note keys must be unique among siblings, not globally. Fiber (React's architecture) splits this work into interruptible units so long renders don't block the main thread, but the MATCHING rules above are unchanged — Fiber changes WHEN the work happens, not WHAT counts as a match.
Explaining why state resets on a type/key change, why index keys corrupt reorderable lists, and how to force a remount with key.
General tree diff is O(n³); React's two heuristics make reconciliation O(n).
// (1) TYPE change => unmount + rebuild subtree (state below is lost).
{editing ? <input defaultValue={name} /> : <span>{name}</span>}
// (2) Keys identify list children across renders.
todos.map(t => <Row key={t.id} todo={t} />); // ✅ stable id: correct moves
todos.map((t, i) => <Row key={i} todo={t} />); // ❌ index: breaks on reorder/insert
// (3) A changing key is the deliberate way to RESET a component.
<Profile key={userId} userId={userId} />; // new userId => fresh state