Watch 10 video solutions for Immutability Helper, a hard level problem. This walkthrough by ThePrimeTime has 1,196,238 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Creating clones of immutable objects with minor alterations can be a tedious process. Write a class ImmutableHelper that serves as a tool to help with this requirement. The constructor accepts an immutable object obj which will be a JSON object or array.
The class has a single method produce which accepts a function mutator. The function returns a new object which is similar to the original except it has those mutations applied.
mutator accepts a proxied version of obj. A user of this function can (appear to) mutate this object, but the original object obj should not actually be effected.
For example, a user could write code like this:
const originalObj = {"x": 5};
const helper = new ImmutableHelper(originalObj);
const newObj = helper.produce((proxy) => {
proxy.x = proxy.x + 1;
});
console.log(originalObj); // {"x": 5}
console.log(newObj); // {"x": 6}
Properties of the mutator function:
undefined.delete obj.key)push, shift, etc).proxy.x = {})Note on how the solution will be tested: the solution validator will only analyze differences between what was returned and the original obj. Doing a full comparison would be too computationally expensive. Also, any mutations to the original object will result in a wrong answer.
Example 1:
Input:
obj = {"val": 10},
mutators = [
proxy => { proxy.val += 1; },
proxy => { proxy.val -= 1; }
]
Output:
[
{"val": 11},
{"val": 9}
]
Explanation:
const helper = new ImmutableHelper({val: 10});
helper.produce(proxy => { proxy.val += 1; }); // { "val": 11 }
helper.produce(proxy => { proxy.val -= 1; }); // { "val": 9 }
Example 2:
Input:
obj = {"arr": [1, 2, 3]}
mutators = [
proxy => {
proxy.arr[0] = 5;
proxy.newVal = proxy.arr[0] + proxy.arr[1];
}
]
Output:
[
{"arr": [5, 2, 3], "newVal": 7 }
]
Explanation: Two edits were made to the original array. The first element in the array was to set 5. Then a new key was added with a value of 7.
Example 3:
Input:
obj = {"obj": {"val": {"x": 10, "y": 20}}}
mutators = [
proxy => {
let data = proxy.obj.val;
let temp = data.x;
data.x = data.y;
data.y = temp;
}
]
Output:
[
{"obj": {"val": {"x": 20, "y": 10}}}
]
Explanation: The values of "x" and "y" were swapped.
Constraints:
2 <= JSON.stringify(obj).length <= 4 * 105mutators is an array of functionstotal calls to produce() < 105Problem Overview: You receive an object (or array) and a specification object describing updates such as $set, $merge, $push, and $apply. The task is to return a new structure reflecting those updates without mutating the original. Only the modified branches should be copied while unchanged parts remain shared.
Approach 1: Deep Copy Then Apply Commands (O(n) time, O(n) space)
The most straightforward idea is to fully clone the original structure first and then interpret the spec to apply operations. A deep copy ensures the original object stays untouched. After cloning, iterate through the spec keys and execute commands such as replacing values for $set, merging properties for $merge, pushing items for $push, or running a function for $apply. This works but wastes memory because even unchanged branches are duplicated. Time complexity is O(n) for cloning the entire structure, and space complexity is also O(n).
Approach 2: Recursive Spec Traversal with Structural Sharing (O(n) time, O(h) space)
The optimal solution walks the spec and only clones the parts of the data that actually change. Use a recursive function that receives the current value and the corresponding spec node. If the spec contains a command like $set, return the provided value immediately. For container updates, create a shallow copy of the current object or array, then recursively process the relevant child keys. This pattern preserves immutability because each modified level creates a new reference while untouched branches are reused.
Operations behave as follows: $merge performs a shallow object merge, $push appends items to a copied array, and $apply executes a function on the current value. Nested keys indicate deeper updates, so the recursion continues until a command node is encountered. This mirrors problems that require recursive traversal such as recursion and DFS over object trees.
Because only modified paths are copied, the runtime is proportional to the number of nodes visited in the update path. In the worst case it becomes O(n), but typical updates touch far fewer nodes. The recursion depth equals the nesting depth h, giving O(h) auxiliary space.
Recommended for interviews: The recursive structural sharing approach. Interviewers expect you to preserve immutability without cloning the entire structure. Starting with the deep-copy idea shows understanding of immutability, but the recursive solution demonstrates mastery of nested object traversal and controlled copying, which is a common pattern in state management libraries and problems involving hash table-like object structures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Deep Copy + Apply Commands | O(n) | O(n) | Simple implementation when performance or memory efficiency is not critical |
| Recursive Structural Sharing | O(n) worst case | O(h) | Preferred approach for immutable state updates and large nested objects |
| Iterative Stack Traversal | O(n) | O(h) | Alternative to recursion when avoiding call stack limits |