Implement deepEqual: Structural Equality Done Right

The problem

Implement deepEqual(a, b): true when two values have the same structure and the same leaf values — regardless of reference identity.

The naive recursive version is ten lines, and interviewers love this question because the naive version confidently returns wrong answers on four specific inputs. Know the four and the question is yours:

naiveDeepEqual(new Date(0), new Date(999999));  // true ❌ — any two Dates "equal"
naiveDeepEqual(/a/g, /b/i);                     // true ❌ — any two RegExps "equal"
naiveDeepEqual([1, 2], { 0: 1, 1: 2 });         // true ❌ — array ≡ object?!
naiveDeepEqual(NaN, NaN);                       // false ❌ — should be true structurally

The first two happen because Date and RegExp carry their data in internal slots, not enumerable keys — so key-based comparison sees two empty objects. The third: identical key sets, no type check. The fourth: === short-circuit fails for NaN and nothing rescues it.

Implementation

function deepEqual(a, b, seen = new WeakMap()) {
  // Object.is: === plus NaN≡NaN (and the -0 distinction) — SameValue semantics
  if (Object.is(a, b)) return true;
 
  // past here, at least one differs by identity — both must be objects to continue
  if (a === null || b === null || typeof a !== "object" || typeof b !== "object") {
    return false;
  }
 
  // types must MATCH before structures are compared
  if (Object.getPrototypeOf(a) !== Object.getPrototypeOf(b)) return false;
 
  // internal-slot types: compare their DATA, not their (empty) keys
  if (a instanceof Date) return a.getTime() === b.getTime();
  if (a instanceof RegExp) return a.source === b.source && a.flags === b.flags;
 
  // cycles: if we're already comparing this pair higher up the tree,
  // assume equal — the outer comparison will settle it
  if (seen.get(a) === b) return true;
  seen.set(a, b);
 
  if (Array.isArray(a)) {
    if (a.length !== b.length) return false;
    return a.every((item, i) => deepEqual(item, b[i], seen));
  }
 
  const keysA = Object.keys(a);
  const keysB = Object.keys(b);
  if (keysA.length !== keysB.length) return false;
 
  return keysA.every(
    (key) =>
      Object.prototype.hasOwnProperty.call(b, key) && // O(1), and safe on null-proto objects
      deepEqual(a[key], b[key], seen)
  );
}

Verified behavior

deepEqual({ a: 1, b: { c: [1, 2] } }, { b: { c: [1, 2] }, a: 1 }); // true — key order irrelevant
deepEqual(new Date(0), new Date(0));       // true
deepEqual(new Date(0), new Date(1));       // false ✓ (naive says true)
deepEqual([1, 2], { 0: 1, 1: 2 });         // false ✓ — prototype check catches it
deepEqual({ x: NaN }, { x: NaN });         // true ✓ — Object.is at the leaves
deepEqual({ a: 1 }, { a: 1, b: undefined }); // false — different key COUNTS…
 
const a = { v: 1 }; a.self = a;
const b = { v: 1 }; b.self = b;
deepEqual(a, b);                            // true — cycles terminate

That { a: 1 } vs { a: 1, b: undefined } line is a policy worth pausing on: key-based comparison says unequal (an own key exists), while a "same observable values" philosophy says equal. Lodash's isEqual says unequal; some libraries differ. Knowing it's a decision — and which one you made — is the level this question is played at.

Why each guard exists

• Object.is up front — one check buys identity fast-path and NaN correctness (the equality-algorithms story). Using === here plus a leaf-level NaN patch is the common clumsy alternative.
• Prototype comparison — the cheapest honest "same type" check: kills array-vs-object, class-A-vs-class-B, and null-proto-vs-literal confusions in one line, without an instanceof ladder (why tag/proto beats instanceof chains).
• The seen pair-map — cycles would recurse forever. Mapping a → b says "this comparison is already in progress; treat as equal and let the rest of the structure decide." Same visited-before-recurse discipline as deep clone, adapted from cloning to pairing.
• hasOwnProperty.call — O(1) versus the keys2.includes(key) O(n²) everyone writes first; borrowed because b might be Object.create(null) (method borrowing).

Where you see it in production

Test assertions (expect(x).toEqual(y) — Jest's equals is exactly this function with more branches), React's dependency debates (deep comparison is what useEffect deps don't do — shallow Object.is only), config drift detection, and cache-key validation. The performance framing that shows judgment: deep equality is O(total size) every call — which is precisely why React chose reference equality + immutable updates instead of deep comparison per render.

Edge cases interviewers probe

• The four planted inputs (top of article) — they're the question.
• Map/Set — key-based walk sees empty objects again (same internal-slot story as Date). Set equality is genuinely hard (order-independent matching = bipartite matching in the general case); say it's hard and handle size + element-wise for the common cases if pressed.
• Symbol keys — Object.keys skips them; whether to include (Reflect.ownKeys) is a stated policy, same as clone's fidelity levels.
• -0 vs 0 — Object.is(-0, 0) is false, so this implementation distinguishes them; lodash's does not (SameValueZero-ish). Another named policy fork.
• Sparse arrays — [ ,1 ] vs [undefined, 1]: every skips holes (accidentally treating them as equal); an index loop distinguishes. Deep trivia; knowing holes behave weirdly everywhere (reduce, clone, here) is the pattern.

Common mistakes

• The four confident wrong answers of the naive version.
• keys2.includes — quadratic on wide objects.
• Comparing JSON.stringify(a) === JSON.stringify(b) — inherits key-order sensitivity, drops undefined, explodes on cycles: every stringify limitation reborn as an equality bug.
• No cycle handling — stack overflow on the first self-referencing pair.
• Checking typeof a === typeof b and believing it's a type check (both "object" covers arrays, dates, null-protos, everything).

Follow-up questions

• "Make it O(1)-ish for React-style use." — you can't; that's the argument for immutability + reference checks (memoizeLast is the machinery). Recognizing "don't optimize deepEqual, avoid needing it" is the senior answer.
• "Add Map/Set support." — Maps: size + per-key lookup with deep-equal values (object keys make it hairy — say so); Sets: the matching problem above.
• "Diff, not just boolean?" — return the path of the first difference (b.c[1]) — the test-framework feature; threading a path array through the recursion is a clean extension exercise.
• "How does Jest's toEqual differ from toStrictEqual?" — undefined-valued keys ignored vs honored, class prototypes checked vs not — the exact policy forks named above, shipped as two matchers. Great "this stuff is real" close.
• "Iterative version?" — explicit stack of pairs; same transformation as clone and JSON.parse — the recursion-to-stack move is one skill asked three ways.