Skip to main content
Talentd

Immutability Helper - Solution & Explanation

HardPremiumFree on FleetCode5 min read
Practice this problem

Problem Statement

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:

  • It will always return undefined.
  • It will never access keys that don't exist.
  • It will never delete keys (delete obj.key)
  • It will never call methods on a proxied object (push, shift, etc).
  • It will never set keys to objects (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 * 105
  • mutators is an array of functions
  • total calls to produce() < 105

Approach Overview

Problem 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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Deep Copy + Apply CommandsO(n)O(n)Simple implementation when performance or memory efficiency is not critical
Recursive Structural SharingO(n) worst caseO(h)Preferred approach for immutable state updates and large nested objects
Iterative Stack TraversalO(n)O(h)Alternative to recursion when avoiding call stack limits

Video Solution

Leetcode Interviews • ThePrimeTime • 1,196,238 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Immutability Helper easy or hard?
Immutability Helper is classified as a Hard problem because it requires interpreting a command DSL and updating nested structures without mutation. The challenge lies in implementing recursive updates while preserving structural sharing.
Immutability Helper Python/Java solution
The same logic can be implemented in Python or Java by recursively processing a specification map and cloning containers when a modification occurs. Python dictionaries/lists or Java Map/List structures replace JavaScript objects and arrays.
How to solve Immutability Helper in O(n)?
Use a recursive function that interprets update commands such as $set, $merge, $push, and $apply. When descending into nested keys, create shallow copies only for modified objects or arrays. This ensures each element is processed at most once, giving O(n) worst-case complexity.
What is the best approach for Immutability Helper?
The best approach is recursive structural sharing. Traverse the specification object and only clone the branches that are updated while reusing unchanged parts of the original structure. This keeps the operation immutable while avoiding the overhead of cloning the entire object.
Is Immutability Helper asked at Google/Amazon/Meta?
Problems involving immutable updates and structural sharing appear in frontend and JavaScript-heavy interviews at companies like Meta and Google. They test understanding of state management patterns used in frameworks such as React.
What data structure is used in Immutability Helper?
The problem primarily uses JavaScript objects and arrays treated as tree-like structures. The solution relies on recursive traversal and shallow copying, similar to DFS over nested hash-map style data.
What is the time complexity of Immutability Helper?
The worst-case time complexity is O(n), where n is the size of the object or array being processed. If only a small portion of the structure is updated, the practical runtime is closer to the number of nodes along the modified path.

Ready to solve this problem?

Practice Immutability Helper with our built-in code editor and test cases.

Practice on FleetCode
Previous

Infinite Method Object

Next

Make Object Immutable