Implement deepCloneII(value) — a deep clone that walks nested objects and arrays and correctly handles circular references and shared substructure. The medium version of this problem assumed a tree-shaped input; this one assumes a graph. A node can reference any other node, including itself, and any two pointers to the same node must remain a single shared node in the output.
The new dimension here is the visited map. Every time the recursion enters an object or array, it records that original together with the fresh clone it just allocated. The next time the same original shows up — whether from a cycle back to an ancestor, or from two siblings both pointing at the same node — the recursion returns the existing clone instead of allocating a new one. Cycles and DAGs fall out of the same line of code.
// Returns a deep copy that mirrors the input's reference graph: cycles
// in the input become cycles in the output, shared nodes in the input
// stay shared in the output. The result shares no object references
// with the input.
function deepCloneII<T>(value: T): T;// A self-cycle is preserved within the clone, not back to the original.
const a = {};
a.self = a;
const c = deepCloneII(a);
c !== a; // true — top-level reference is new
c.self === c; // true — cycle preserved within the clone graph
c.self === a; // false — never points back at the source// Shared substructure (DAG) — both keys point to the SAME inner node.
// The clone preserves that sharing: one clone of x, referenced twice.
const x = { n: 1 };
const obj = { a: x, b: x };
const c = deepCloneII(obj);
c.a === c.b; // true — sharing preserved
c.a !== x; // true — but it's a fresh clone, not the source// A cycle one level deep: child loops back to grandparent.
const root = { name: 'root' };
const child = { name: 'child' };
root.child = child;
child.parent = root;
const c = deepCloneII(root);
c.child.parent === c; // true — child loops back to the clone of root
c.child.parent !== root; // true — and never to the originalDate, RegExp, Map, Set, TypedArray, class instances with custom prototypes, and symbol-keyed properties are out of scope — see the solution's "Going further" for how each would extend.JSON.stringify does), which is not the goal here.Object.keys — don't walk the prototype chain, don't copy inherited properties, don't copy symbol keys.JSON.parse(JSON.stringify(...)). It throws on cycles, drops undefined, mangles Date, and loses functions. The whole point of this question is handling cases that defeat that one-liner.You'll extend a tree-walking deep clone into a graph-walking one — same recursion, plus a small Map that remembers every object the walk has already cloned. That one map is what makes both cycles and shared substructure work.
The medium version of this question handled trees: every container had exactly one parent, every leaf was a primitive, and the recursion never met the same node twice. Real data isn't always a tree. Two parents can hold the same child (a directed acyclic graph). A child can hold a reference back to its parent or grandparent (a cycle). A node can reference itself (a.self = a). The recursion from the medium walks all of these inputs forever, because every time it follows a back-edge it ends up re-visiting an ancestor and starting the whole walk again.
The fix is one data structure. As we walk the input, we keep a Map from each original object to the clone we just allocated for it. Every recursive call starts by asking the map: "have I cloned this exact object before?" If yes, return the existing clone — don't allocate a new one, don't recurse into it. If no, allocate the clone, record it in the map, then recurse. That single check terminates cycles AND preserves sharing.
Three concepts. The first one is unchanged from the medium; we won't re-derive it here. The second and third are the whole new dimension.
One: recursive descent over the structure. Same as the medium. Primitives are the base case; arrays and plain objects allocate fresh containers and recurse on each child.
Two: a visited map keyed by source identity. A Map (or WeakMap) from each original object to its clone. Two ways the map gets queried: (a) the recursion follows a cycle back to an ancestor, finds the ancestor already in the map, and returns the cached clone — that's the cycle break; (b) the recursion meets a node a sibling already cloned, finds it in the map, and returns the cached clone — that's DAG sharing preserved. Same lookup; both behaviors fall out of the same line of code.
Three: record on entry, not on exit. This is the load-bearing detail. When we enter a container, we allocate the empty clone shell first, then immediately put (source -> shell) into the map — before we recurse into the children. Only after that registration do we walk the keys and fill the shell in. If a child reaches back to this node, the map already has the entry, and the recursion terminates. If we recorded after recursing, the recursion into a self-cycle would never finish — the seen.set line at the bottom of the function is unreachable when the recursion above it loops.
Two attempts are reflex answers at the whiteboard. Both fail on the new inputs in different, concrete ways.
JSON.parse(JSON.stringify(value))This is the standard "I need a deep copy" one-liner. For a tree of strings and numbers it works fine. It also has zero hope of handling a cycle:
const a = {};
a.self = a;
JSON.parse(JSON.stringify(a));
// TypeError: Converting circular structure to JSON
// --> starting at object with constructor 'Object'
// --- property 'self' closes the circleJSON.stringify traverses the input with its own internal map of in-progress containers and explicitly throws the moment it meets one twice. That's cycle detection, not cycle preservation — the spec made a deliberate choice that the only sensible string representation of a cyclic object is an exception. There is no flag to recover from this; JSON.stringify and cycles are incompatible by design.
It also loses other things — undefined evaporates, NaN and Infinity become null, Date becomes a string, functions disappear, symbol keys vanish — but the headline failure for this question is that it crashes on the first cyclic input you hand it.
If you carry the medium's recursive clone straight in:
function deepCloneNoMap(value) {
if (value === null || typeof value !== 'object') return value;
const clone = Array.isArray(value) ? [] : {};
for (const key of Object.keys(value)) {
clone[key] = deepCloneNoMap(value[key]);
}
return clone;
}The same self-cycle input does this:
const a = {};
a.self = a;
deepCloneNoMap(a);
// RangeError: Maximum call stack size exceededThe recursion enters a, allocates clone = {}, iterates keys, hits 'self', recurses on a.self — which is a — and we're right back where we started. Every recursive frame stacks another one on top of it, no frame ever returns, and the JS engine kills the program when the call stack runs out of space.
The shared-substructure input fails differently — it doesn't crash, but it silently breaks identity. Given const x = {n:1}; deepCloneNoMap({a: x, b: x}), the recursion clones x twice — once for the a key, once for the b key. The output's c.a and c.b are no longer the same object. If the caller's code relied on aliasing (mutating through one and expecting the other to see it), that contract is gone.
Both failures come from the same missing piece: a memory of which originals have already been cloned. Add that memory, and both inputs work.
function deepCloneIi(value, seen = new Map()) {
// Primitives (including null) pass through. typeof null === 'object', so
// the explicit null check has to come before the typeof check.
if (value === null || typeof value !== 'object') return value;
// Already seen — return the existing clone. This is the cycle-break AND
// the DAG-sharing handler, both in one lookup.
if (seen.has(value)) return seen.get(value);
// Allocate the clone shell BEFORE recursing into children, and record it
// in the map RIGHT AWAY. This is the load-bearing line: if we recorded
// after recursing, a child's recursion back to this node would not find
// it in the map and the recursion would loop forever.
let clone;
if (Array.isArray(value)) {
clone = [];
seen.set(value, clone);
for (let i = 0; i < value.length; i++) {
clone[i] = deepCloneIi(value[i], seen);
}
} else {
clone = {};
seen.set(value, clone);
for (const key of Object.keys(value)) {
clone[key] = deepCloneIi(value[key], seen);
}
}
return clone;
}
module.exports = { deepCloneIi };Why each non-obvious choice is the way it is — most of these are the same questions a junior dev asks reading this code cold.
Why the explicit value === null before typeof. typeof null === 'object' is a 40-year-old JavaScript bug we have to work around. If we wrote only if (typeof value !== 'object') return value;, the function would treat null as an object, fall through to the recursion branch, and crash on Object.keys(null). The null check has to come first.
Why seen is a default argument. The top-level call constructs a fresh map (new Map()); every recursive call inside the function passes the same map through (deepCloneIi(value[i], seen)). The default value is just how we get a fresh map on the first call without making the caller pass one. If you ever need two independent clones in the same scope, you call deepCloneIi(x) and deepCloneIi(y) — each gets its own map.
Why we check seen.has(value) before allocating the new clone. Two reasons. First, correctness for cycles: the lookup is what stops the recursion when we re-enter a node. Second, correctness for DAGs: if two siblings point at the same node, the second sibling must reuse the first sibling's clone, not allocate a fresh one. If we allocated first and checked later, we'd waste an allocation AND break sharing — the new object would replace the one the first sibling already linked to.
Why we call seen.set(value, clone) before the loop. This is the rule the diagram above hammers on. The clone shell has to exist in the map before recursion descends, because the recursion is what reaches back up. A cycle from a back to a works only when seen.has(a) is true at the moment the recursion meets a for the second time. Move the seen.set line below the loop and the cycle test in the test file blows the stack.
Why Map and not WeakMap. Both work. Map is the simpler choice and slightly easier to reason about (has, get, set on any key). WeakMap lets the keys be garbage-collected if the only thing holding them is the map itself, which is a minor advantage if the clone call lives inside a long-lived scope. For one-shot clone calls the map dies with the function, so the difference doesn't matter. We use Map here because it accepts any key shape — if you wanted to extend the function to handle primitive-like wrappers (new Number(1)), WeakMap would refuse them; Map wouldn't.
Why Array.isArray(value) is checked before the plain-object branch. Arrays are typeof 'object', and Object.keys on an array returns the numeric indices as strings — so the plain-object branch would actually work on arrays, sort of, except the resulting clone would be { '0': ..., '1': ... } instead of an array. Array.isArray(cloned) on that would return false, and cloned.length would be undefined. Splitting the two branches keeps arrays as arrays.
Why Object.keys (not for...in, not Reflect.ownKeys). Object.keys walks own enumerable string keys only. for...in walks inherited keys too, which copies the prototype chain into the clone — wrong, since the clone now has properties the source doesn't have when you check with hasOwnProperty. Reflect.ownKeys includes symbol-keyed and non-enumerable properties, which is more thorough but a different design choice; we've scoped this implementation to JSON-shaped objects and documented symbols as out of scope.
The two shifts from the medium are: (a) we record (source -> clone) in a map on entry, before recursing, and (b) we look the source up in the map at the top of every call and short-circuit if it's there. Two lines of code, and cycles plus sharing both work.
Two traces. The first shows the cycle behavior the medium couldn't handle. The second shows the DAG-sharing case the medium also got wrong, with the same fix.
a.self = aconst a = {};
a.self = a;
const c = deepCloneIi(a);value = a, seen = new Map(). a is not null, typeof a === 'object', so we don't short-circuit. seen.has(a) is false. Array.isArray(a) is false. Allocate clone = {}. Call seen.set(a, clone). Map now holds { a -> clone }.Object.keys(a) → ['self']. Recurse: deepCloneIi(a.self, seen). a.self === a, so the recursive call is deepCloneIi(a, seen).seen.has(a) is true — we set that in step 1. Return seen.get(a), which is clone itself.clone['self'] = clone. The clone's self property now points at the clone, not at a. Return clone.After the call:
c !== a; // true — top-level reference is new
c.self === c; // true — cycle preserved inside the clone
c.self === a; // false — never references the sourceThe map ends up with one entry. The recursion descended exactly two levels — one for the entry into a, one for the cache hit — and returned.
obj = { a: x, b: x }const x = { n: 1 };
const obj = { a: x, b: x };
const c = deepCloneIi(obj);value = obj. Not seen. Allocate clone = {}. seen.set(obj, clone). Loop Object.keys(obj) → ['a', 'b'].'a'. Recurse: deepCloneIi(x, seen). seen.has(x) is false. Allocate xClone = {}. seen.set(x, xClone). Loop Object.keys(x) → ['n']. Recurse on n: 1 — primitive, returns 1. Assign xClone.n = 1. Return xClone. Back outside: clone.a = xClone. Map now holds { obj -> clone, x -> xClone }.'b'. Recurse: deepCloneIi(x, seen). seen.has(x) is true — we set that in step 2. Return seen.get(x), which is xClone — the same object we just used for 'a'.clone.b = xClone. Return clone.After the call:
c.a === c.b; // true — the same clone, referenced twice
c.a !== x; // true — but it's a clone, not the original
c.a.n = 99;
c.b.n; // 99 — sharing in the output mirrors sharing in the input
x.n; // 1 — the original is untouchedThe recursion allocated clone and xClone — two new objects for two unique nodes in the source. The DAG's sharing was rebuilt in the output because the second visit to x short-circuited.
typeof null === 'object'. Without an explicit null check before the typeof gate, the function falls into the recursion branch on null, hits Object.keys(null), and throws TypeError: Cannot convert undefined or null to object. Always handle null first.seen.set(value, clone) to after the loop, the cycle guard does nothing. The first time a child cycles back to value, seen.has(value) is still false, the recursion descends again, repeats, and you stack-overflow before the seen.set line is ever reached. The set has to happen before recursion descends — that's why the clone shell is allocated empty and filled in afterwards.JSON.parse(JSON.stringify(x)) throws on cycles AND silently drops data. Even if you don't care about cycles, the JSON round-trip loses undefined, mangles NaN and Infinity to null, turns Date into a string, deletes functions and symbol-keyed properties. The "throws on cycles" failure is the load-bearing one for this question, but the silent data loss is the reason to avoid the one-liner even on tree-shaped inputs.Map vs WeakMap for seen. Both work. WeakMap allows the original keys to be garbage-collected while the clone is in progress, which matters slightly if the function lives inside a long-lived scope; Map is simpler and accepts any key. For a one-shot clone call, the map dies with the function either way. The tradeoff is small; pick one and document it.Object.create-derived objects with custom prototypes. Writing clone = {} allocates an object with Object.prototype as its prototype. If the source was Object.create(someProto), the clone has lost someProto. To preserve the prototype, allocate clone = Object.create(Object.getPrototypeOf(value)) instead. The trade-off is that the clone is no longer a "plain object" — it now carries inherited behavior. For most input shapes the {} version is the right call; document that prototypes are not preserved.Object.keys skips them. If a caller does Object.defineProperty(obj, 'hidden', { value: 1, enumerable: false }), the property is silently absent from the clone. Use Object.getOwnPropertyNames to include them, paired with Object.defineProperty on the clone side so the non-enumerable flag survives the copy. We've scoped the question to enumerable string keys, but the limitation is worth knowing.Object.keys returns only string keys. Symbol-keyed entries (obj[Symbol.for('id')] = 1) are invisible to the loop. Reflect.ownKeys returns strings AND symbols; use it if your domain leans on symbols. Same scope note applies.value instanceof Date → new Date(+value) (the unary + calls valueOf). value instanceof RegExp → new RegExp(value.source, value.flags). value instanceof Map → allocate new Map(), register it in seen before iterating, then loop value.entries() and recurse on both keys and values (Map keys can be objects, which is where cycle-safety re-enters the picture). Same pattern for Set over value.values(). The dispatch is a chain of instanceof checks before the plain-object branch; the register-before-iterate rule from the main solution carries through to every typed branch.Uint8Array, Float32Array, and friends are array-like but Array.isArray returns false. The clone of a typed array is value.constructor.from(value) or value.slice() — the latter returns a same-typed copy in one call. ArrayBuffer itself uses value.slice(0). Both contain only bytes, never references, so they don't participate in the cycle/sharing machinery; the seen map can ignore them, though registering them is cheap insurance.clone = {} with clone = Object.create(Object.getPrototypeOf(value)). The clone now carries the source's prototype chain — including class instances, since class X {} creates instances whose [[Prototype]] is X.prototype. Combined with Reflect.ownKeys for the key loop and Object.defineProperty for the assignment, you have something close to a full structural clone of arbitrary objects.structuredClone. Modern runtimes (Node 17+, all current browsers) ship structuredClone(value). It handles cycles, Date, RegExp, Map, Set, TypedArray, ArrayBuffer, Blob, and more. It throws on functions, DOM nodes, and class-instance methods. The hand-rolled function is the interview answer; structuredClone is the production answer when you can use it.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
Implement deepCloneII(value) — a deep clone that walks nested objects and arrays and correctly handles circular references and shared substructure. The medium version of this problem assumed a tree-shaped input; this one assumes a graph. A node can reference any other node, including itself, and any two pointers to the same node must remain a single shared node in the output.
The new dimension here is the visited map. Every time the recursion enters an object or array, it records that original together with the fresh clone it just allocated. The next time the same original shows up — whether from a cycle back to an ancestor, or from two siblings both pointing at the same node — the recursion returns the existing clone instead of allocating a new one. Cycles and DAGs fall out of the same line of code.
// Returns a deep copy that mirrors the input's reference graph: cycles
// in the input become cycles in the output, shared nodes in the input
// stay shared in the output. The result shares no object references
// with the input.
function deepCloneII<T>(value: T): T;// A self-cycle is preserved within the clone, not back to the original.
const a = {};
a.self = a;
const c = deepCloneII(a);
c !== a; // true — top-level reference is new
c.self === c; // true — cycle preserved within the clone graph
c.self === a; // false — never points back at the source// Shared substructure (DAG) — both keys point to the SAME inner node.
// The clone preserves that sharing: one clone of x, referenced twice.
const x = { n: 1 };
const obj = { a: x, b: x };
const c = deepCloneII(obj);
c.a === c.b; // true — sharing preserved
c.a !== x; // true — but it's a fresh clone, not the source// A cycle one level deep: child loops back to grandparent.
const root = { name: 'root' };
const child = { name: 'child' };
root.child = child;
child.parent = root;
const c = deepCloneII(root);
c.child.parent === c; // true — child loops back to the clone of root
c.child.parent !== root; // true — and never to the originalDate, RegExp, Map, Set, TypedArray, class instances with custom prototypes, and symbol-keyed properties are out of scope — see the solution's "Going further" for how each would extend.JSON.stringify does), which is not the goal here.Object.keys — don't walk the prototype chain, don't copy inherited properties, don't copy symbol keys.JSON.parse(JSON.stringify(...)). It throws on cycles, drops undefined, mangles Date, and loses functions. The whole point of this question is handling cases that defeat that one-liner.You'll extend a tree-walking deep clone into a graph-walking one — same recursion, plus a small Map that remembers every object the walk has already cloned. That one map is what makes both cycles and shared substructure work.
The medium version of this question handled trees: every container had exactly one parent, every leaf was a primitive, and the recursion never met the same node twice. Real data isn't always a tree. Two parents can hold the same child (a directed acyclic graph). A child can hold a reference back to its parent or grandparent (a cycle). A node can reference itself (a.self = a). The recursion from the medium walks all of these inputs forever, because every time it follows a back-edge it ends up re-visiting an ancestor and starting the whole walk again.
The fix is one data structure. As we walk the input, we keep a Map from each original object to the clone we just allocated for it. Every recursive call starts by asking the map: "have I cloned this exact object before?" If yes, return the existing clone — don't allocate a new one, don't recurse into it. If no, allocate the clone, record it in the map, then recurse. That single check terminates cycles AND preserves sharing.
Three concepts. The first one is unchanged from the medium; we won't re-derive it here. The second and third are the whole new dimension.
One: recursive descent over the structure. Same as the medium. Primitives are the base case; arrays and plain objects allocate fresh containers and recurse on each child.
Two: a visited map keyed by source identity. A Map (or WeakMap) from each original object to its clone. Two ways the map gets queried: (a) the recursion follows a cycle back to an ancestor, finds the ancestor already in the map, and returns the cached clone — that's the cycle break; (b) the recursion meets a node a sibling already cloned, finds it in the map, and returns the cached clone — that's DAG sharing preserved. Same lookup; both behaviors fall out of the same line of code.
Three: record on entry, not on exit. This is the load-bearing detail. When we enter a container, we allocate the empty clone shell first, then immediately put (source -> shell) into the map — before we recurse into the children. Only after that registration do we walk the keys and fill the shell in. If a child reaches back to this node, the map already has the entry, and the recursion terminates. If we recorded after recursing, the recursion into a self-cycle would never finish — the seen.set line at the bottom of the function is unreachable when the recursion above it loops.
Two attempts are reflex answers at the whiteboard. Both fail on the new inputs in different, concrete ways.
JSON.parse(JSON.stringify(value))This is the standard "I need a deep copy" one-liner. For a tree of strings and numbers it works fine. It also has zero hope of handling a cycle:
const a = {};
a.self = a;
JSON.parse(JSON.stringify(a));
// TypeError: Converting circular structure to JSON
// --> starting at object with constructor 'Object'
// --- property 'self' closes the circleJSON.stringify traverses the input with its own internal map of in-progress containers and explicitly throws the moment it meets one twice. That's cycle detection, not cycle preservation — the spec made a deliberate choice that the only sensible string representation of a cyclic object is an exception. There is no flag to recover from this; JSON.stringify and cycles are incompatible by design.
It also loses other things — undefined evaporates, NaN and Infinity become null, Date becomes a string, functions disappear, symbol keys vanish — but the headline failure for this question is that it crashes on the first cyclic input you hand it.
If you carry the medium's recursive clone straight in:
function deepCloneNoMap(value) {
if (value === null || typeof value !== 'object') return value;
const clone = Array.isArray(value) ? [] : {};
for (const key of Object.keys(value)) {
clone[key] = deepCloneNoMap(value[key]);
}
return clone;
}The same self-cycle input does this:
const a = {};
a.self = a;
deepCloneNoMap(a);
// RangeError: Maximum call stack size exceededThe recursion enters a, allocates clone = {}, iterates keys, hits 'self', recurses on a.self — which is a — and we're right back where we started. Every recursive frame stacks another one on top of it, no frame ever returns, and the JS engine kills the program when the call stack runs out of space.
The shared-substructure input fails differently — it doesn't crash, but it silently breaks identity. Given const x = {n:1}; deepCloneNoMap({a: x, b: x}), the recursion clones x twice — once for the a key, once for the b key. The output's c.a and c.b are no longer the same object. If the caller's code relied on aliasing (mutating through one and expecting the other to see it), that contract is gone.
Both failures come from the same missing piece: a memory of which originals have already been cloned. Add that memory, and both inputs work.
function deepCloneIi(value, seen = new Map()) {
// Primitives (including null) pass through. typeof null === 'object', so
// the explicit null check has to come before the typeof check.
if (value === null || typeof value !== 'object') return value;
// Already seen — return the existing clone. This is the cycle-break AND
// the DAG-sharing handler, both in one lookup.
if (seen.has(value)) return seen.get(value);
// Allocate the clone shell BEFORE recursing into children, and record it
// in the map RIGHT AWAY. This is the load-bearing line: if we recorded
// after recursing, a child's recursion back to this node would not find
// it in the map and the recursion would loop forever.
let clone;
if (Array.isArray(value)) {
clone = [];
seen.set(value, clone);
for (let i = 0; i < value.length; i++) {
clone[i] = deepCloneIi(value[i], seen);
}
} else {
clone = {};
seen.set(value, clone);
for (const key of Object.keys(value)) {
clone[key] = deepCloneIi(value[key], seen);
}
}
return clone;
}
module.exports = { deepCloneIi };Why each non-obvious choice is the way it is — most of these are the same questions a junior dev asks reading this code cold.
Why the explicit value === null before typeof. typeof null === 'object' is a 40-year-old JavaScript bug we have to work around. If we wrote only if (typeof value !== 'object') return value;, the function would treat null as an object, fall through to the recursion branch, and crash on Object.keys(null). The null check has to come first.
Why seen is a default argument. The top-level call constructs a fresh map (new Map()); every recursive call inside the function passes the same map through (deepCloneIi(value[i], seen)). The default value is just how we get a fresh map on the first call without making the caller pass one. If you ever need two independent clones in the same scope, you call deepCloneIi(x) and deepCloneIi(y) — each gets its own map.
Why we check seen.has(value) before allocating the new clone. Two reasons. First, correctness for cycles: the lookup is what stops the recursion when we re-enter a node. Second, correctness for DAGs: if two siblings point at the same node, the second sibling must reuse the first sibling's clone, not allocate a fresh one. If we allocated first and checked later, we'd waste an allocation AND break sharing — the new object would replace the one the first sibling already linked to.
Why we call seen.set(value, clone) before the loop. This is the rule the diagram above hammers on. The clone shell has to exist in the map before recursion descends, because the recursion is what reaches back up. A cycle from a back to a works only when seen.has(a) is true at the moment the recursion meets a for the second time. Move the seen.set line below the loop and the cycle test in the test file blows the stack.
Why Map and not WeakMap. Both work. Map is the simpler choice and slightly easier to reason about (has, get, set on any key). WeakMap lets the keys be garbage-collected if the only thing holding them is the map itself, which is a minor advantage if the clone call lives inside a long-lived scope. For one-shot clone calls the map dies with the function, so the difference doesn't matter. We use Map here because it accepts any key shape — if you wanted to extend the function to handle primitive-like wrappers (new Number(1)), WeakMap would refuse them; Map wouldn't.
Why Array.isArray(value) is checked before the plain-object branch. Arrays are typeof 'object', and Object.keys on an array returns the numeric indices as strings — so the plain-object branch would actually work on arrays, sort of, except the resulting clone would be { '0': ..., '1': ... } instead of an array. Array.isArray(cloned) on that would return false, and cloned.length would be undefined. Splitting the two branches keeps arrays as arrays.
Why Object.keys (not for...in, not Reflect.ownKeys). Object.keys walks own enumerable string keys only. for...in walks inherited keys too, which copies the prototype chain into the clone — wrong, since the clone now has properties the source doesn't have when you check with hasOwnProperty. Reflect.ownKeys includes symbol-keyed and non-enumerable properties, which is more thorough but a different design choice; we've scoped this implementation to JSON-shaped objects and documented symbols as out of scope.
The two shifts from the medium are: (a) we record (source -> clone) in a map on entry, before recursing, and (b) we look the source up in the map at the top of every call and short-circuit if it's there. Two lines of code, and cycles plus sharing both work.
Two traces. The first shows the cycle behavior the medium couldn't handle. The second shows the DAG-sharing case the medium also got wrong, with the same fix.
a.self = aconst a = {};
a.self = a;
const c = deepCloneIi(a);value = a, seen = new Map(). a is not null, typeof a === 'object', so we don't short-circuit. seen.has(a) is false. Array.isArray(a) is false. Allocate clone = {}. Call seen.set(a, clone). Map now holds { a -> clone }.Object.keys(a) → ['self']. Recurse: deepCloneIi(a.self, seen). a.self === a, so the recursive call is deepCloneIi(a, seen).seen.has(a) is true — we set that in step 1. Return seen.get(a), which is clone itself.clone['self'] = clone. The clone's self property now points at the clone, not at a. Return clone.After the call:
c !== a; // true — top-level reference is new
c.self === c; // true — cycle preserved inside the clone
c.self === a; // false — never references the sourceThe map ends up with one entry. The recursion descended exactly two levels — one for the entry into a, one for the cache hit — and returned.
obj = { a: x, b: x }const x = { n: 1 };
const obj = { a: x, b: x };
const c = deepCloneIi(obj);value = obj. Not seen. Allocate clone = {}. seen.set(obj, clone). Loop Object.keys(obj) → ['a', 'b'].'a'. Recurse: deepCloneIi(x, seen). seen.has(x) is false. Allocate xClone = {}. seen.set(x, xClone). Loop Object.keys(x) → ['n']. Recurse on n: 1 — primitive, returns 1. Assign xClone.n = 1. Return xClone. Back outside: clone.a = xClone. Map now holds { obj -> clone, x -> xClone }.'b'. Recurse: deepCloneIi(x, seen). seen.has(x) is true — we set that in step 2. Return seen.get(x), which is xClone — the same object we just used for 'a'.clone.b = xClone. Return clone.After the call:
c.a === c.b; // true — the same clone, referenced twice
c.a !== x; // true — but it's a clone, not the original
c.a.n = 99;
c.b.n; // 99 — sharing in the output mirrors sharing in the input
x.n; // 1 — the original is untouchedThe recursion allocated clone and xClone — two new objects for two unique nodes in the source. The DAG's sharing was rebuilt in the output because the second visit to x short-circuited.
typeof null === 'object'. Without an explicit null check before the typeof gate, the function falls into the recursion branch on null, hits Object.keys(null), and throws TypeError: Cannot convert undefined or null to object. Always handle null first.seen.set(value, clone) to after the loop, the cycle guard does nothing. The first time a child cycles back to value, seen.has(value) is still false, the recursion descends again, repeats, and you stack-overflow before the seen.set line is ever reached. The set has to happen before recursion descends — that's why the clone shell is allocated empty and filled in afterwards.JSON.parse(JSON.stringify(x)) throws on cycles AND silently drops data. Even if you don't care about cycles, the JSON round-trip loses undefined, mangles NaN and Infinity to null, turns Date into a string, deletes functions and symbol-keyed properties. The "throws on cycles" failure is the load-bearing one for this question, but the silent data loss is the reason to avoid the one-liner even on tree-shaped inputs.Map vs WeakMap for seen. Both work. WeakMap allows the original keys to be garbage-collected while the clone is in progress, which matters slightly if the function lives inside a long-lived scope; Map is simpler and accepts any key. For a one-shot clone call, the map dies with the function either way. The tradeoff is small; pick one and document it.Object.create-derived objects with custom prototypes. Writing clone = {} allocates an object with Object.prototype as its prototype. If the source was Object.create(someProto), the clone has lost someProto. To preserve the prototype, allocate clone = Object.create(Object.getPrototypeOf(value)) instead. The trade-off is that the clone is no longer a "plain object" — it now carries inherited behavior. For most input shapes the {} version is the right call; document that prototypes are not preserved.Object.keys skips them. If a caller does Object.defineProperty(obj, 'hidden', { value: 1, enumerable: false }), the property is silently absent from the clone. Use Object.getOwnPropertyNames to include them, paired with Object.defineProperty on the clone side so the non-enumerable flag survives the copy. We've scoped the question to enumerable string keys, but the limitation is worth knowing.Object.keys returns only string keys. Symbol-keyed entries (obj[Symbol.for('id')] = 1) are invisible to the loop. Reflect.ownKeys returns strings AND symbols; use it if your domain leans on symbols. Same scope note applies.value instanceof Date → new Date(+value) (the unary + calls valueOf). value instanceof RegExp → new RegExp(value.source, value.flags). value instanceof Map → allocate new Map(), register it in seen before iterating, then loop value.entries() and recurse on both keys and values (Map keys can be objects, which is where cycle-safety re-enters the picture). Same pattern for Set over value.values(). The dispatch is a chain of instanceof checks before the plain-object branch; the register-before-iterate rule from the main solution carries through to every typed branch.Uint8Array, Float32Array, and friends are array-like but Array.isArray returns false. The clone of a typed array is value.constructor.from(value) or value.slice() — the latter returns a same-typed copy in one call. ArrayBuffer itself uses value.slice(0). Both contain only bytes, never references, so they don't participate in the cycle/sharing machinery; the seen map can ignore them, though registering them is cheap insurance.clone = {} with clone = Object.create(Object.getPrototypeOf(value)). The clone now carries the source's prototype chain — including class instances, since class X {} creates instances whose [[Prototype]] is X.prototype. Combined with Reflect.ownKeys for the key loop and Object.defineProperty for the assignment, you have something close to a full structural clone of arbitrary objects.structuredClone. Modern runtimes (Node 17+, all current browsers) ship structuredClone(value). It handles cycles, Date, RegExp, Map, Set, TypedArray, ArrayBuffer, Blob, and more. It throws on functions, DOM nodes, and class-instance methods. The hand-rolled function is the interview answer; structuredClone is the production answer when you can use it.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.