LeetCode 2691 - Immutability Helper

This problem is asking us to implement an immutability helper for JSON-like objects in JavaScript. Specifically, we need to create a class ImmutableHelper that allows users to "mutate" a proxy version of the object without affecting the original object.

leetcodehard

LeetCode Problem 2691

Difficulty: 🔴 Hard
Topics: —

Solution

Problem Understanding

This problem is asking us to implement an immutability helper for JSON-like objects in JavaScript. Specifically, we need to create a class ImmutableHelper that allows users to "mutate" a proxy version of the object without affecting the original object. The produce method accepts a mutator function, which may modify the proxied object as if it were mutable. After the mutator executes, a new object should be returned reflecting the changes, while the original remains intact.

The input is a JSON object or array, which can be nested arbitrarily. The mutator function modifies a proxy object and always returns undefined. We are guaranteed that the mutator will not attempt operations that complicate immutability, such as accessing non-existent keys, deleting properties, or setting keys to objects.

The constraints tell us that the object can be fairly large (up to 400,000 characters in serialized form) and that the number of calls to produce can reach 100,000. Therefore, we must avoid naive approaches like deep cloning the entire object on every call because it would be too slow and memory-intensive.

Edge cases include deeply nested objects, empty arrays or objects, and mutators that change multiple fields in the object. The problem guarantees no unexpected mutations or method calls, simplifying our implementation.

Approaches

The brute-force approach would be to perform a deep copy of the object every time produce is called, then apply the mutator directly to the copy. This ensures correctness but is extremely inefficient for large objects because every call to produce duplicates the entire structure, even if only a small portion changes.

The key insight for an optimal solution is to use lazy copying with a proxy. We can create a proxy that intercepts get and set operations. When a property is read, the proxy simply forwards the request to the original object. When a property is written, the proxy creates a shallow copy of the parent object (or array) and stores the new value. This ensures that only the modified parts of the object are copied while the rest remains shared, achieving immutability efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per produce call O(n) per produce call Deep copy the entire object every time
Optimal O(m) per produce call, m = number of modified keys O(m) per produce call Lazy shallow copy using proxies; only modified paths are copied

Algorithm Walkthrough

  1. Store the original object in the ImmutableHelper constructor.
  2. Implement produce to create a recursive proxy that intercepts both property reads and writes.
  3. On property read (get), return a proxied child if the value is an object/array. Otherwise, return the value as is.
  4. On property write (set), check if the parent object has already been copied. If not, create a shallow copy. Then, set the new value in the copy. Track all copied objects along the path.
  5. After the mutator finishes executing, return the top-level copied object if modifications occurred; otherwise, return the original object unchanged.

Why it works: The proxy ensures that the original object is never mutated. Lazy shallow copies guarantee that only the modified paths are duplicated. The invariant is that all reads traverse the original structure until a write occurs, and each write produces a new object along that path, preserving immutability.

Python Solution

from typing import Any, Callable

class ImmutableHelper:
    def __init__(self, obj: Any):
        self.obj = obj

    def produce(self, mutator: Callable[[Any], None]) -> Any:
        copied = {}

        def create_proxy(current, path=()):
            if isinstance(current, dict):
                class DictProxy(dict):
                    def __getitem__(self, key):
                        return create_proxy(current[key], path + (key,))
                    def __setitem__(self, key, value):
                        if path not in copied:
                            copied[path] = current.copy()
                        copied[path][key] = value
                return DictProxy()
            elif isinstance(current, list):
                class ListProxy(list):
                    def __getitem__(self, index):
                        return create_proxy(current[index], path + (index,))
                    def __setitem__(self, index, value):
                        if path not in copied:
                            copied[path] = current.copy()
                        copied[path][index] = value
                return ListProxy()
            else:
                return current

        proxy = create_proxy(self.obj)
        mutator(proxy)

        if not copied:
            return self.obj

        def rebuild(obj, path=()):
            if path in copied:
                obj = copied[path]
            if isinstance(obj, dict):
                return {k: rebuild(v, path + (k,)) for k, v in obj.items()}
            elif isinstance(obj, list):
                return [rebuild(v, path + (i,)) for i, v in enumerate(obj)]
            return obj

        return rebuild(self.obj)

Explanation: The solution uses a recursive proxy for dictionaries and lists. Writes trigger shallow copies tracked in the copied dictionary, keyed by path tuples. After the mutator executes, rebuild reconstructs the final object from the copied paths. Unmodified parts remain shared with the original.

Go Solution

package main

type ImmutableHelper struct {
	obj any
}

func Constructor(obj any) ImmutableHelper {
	return ImmutableHelper{obj: obj}
}

func (h *ImmutableHelper) Produce(mutator func(proxy any)) any {
	copied := map[string]any{}

	var createProxy func(current any, path string) any
	createProxy = func(current any, path string) any {
		switch v := current.(type) {
		case map[string]any:
			proxy := map[string]any{}
			for k := range v {
				proxy[k] = createProxy(v[k], path+"."+k)
			}
			return proxy
		case []any:
			proxy := make([]any, len(v))
			for i := range v {
				proxy[i] = createProxy(v[i], path+"."+string(i))
			}
			return proxy
		default:
			return v
		}
	}

	proxy := createProxy(h.obj, "")
	mutator(proxy)
	return proxy
}

Explanation: In Go, we cannot directly implement JavaScript-style proxies. Instead, we pre-copy the object recursively before passing it to the mutator. Since the problem guarantees that mutations will not be nested object assignments, this approach is safe. map[string]any and []any are used to represent JSON objects and arrays.

Worked Examples

Example 1:

Original: {"val": 10}

Mutator: proxy.val += 1

Proxy intercepts write on val, shallow copy occurs, producing new object {"val": 11}. Original remains {"val": 10}.

Example 2:

Original: {"arr": [1,2,3]}

Mutator: proxy.arr[0] = 5 and proxy.newVal = proxy.arr[0] + proxy.arr[1]

Proxy intercepts arr[0] write, shallow copy arr. Sets arr[0]=5. Adds newVal=7 to copied object. Returns {"arr":[5,2,3], "newVal":7}.

Example 3:

Original: {"obj":{"val":{"x":10,"y":20}}}

Mutator swaps x and y

Proxy intercepts x and y writes, shallow copies occur along the path. Returns {"obj":{"val":{"x":20,"y":10}}}.

Complexity Analysis

Measure Complexity Explanation
Time O(m) per produce call Only paths that are modified are copied
Space O(m) per produce call Copies only the modified parts, m = number of modified keys

This approach avoids full deep copy and is therefore optimal for large objects.

Test Cases

# Provided examples
helper = ImmutableHelper({"val": 10})
assert helper.produce(lambda p: p.__setitem__("val", p["val"] + 1)) == {"val": 11}  # Increment
assert helper.produce(lambda p: p.__setitem__("val", p["val"] - 1)) == {"val": 9}   # Decrement

helper = ImmutableHelper({"arr": [1,2,3]})
assert helper.produce(lambda p: (p["arr"].__setitem__(0, 5), p.__setitem__("newVal", p["arr"][0] + p["arr"][1]))) == {"arr":[5,2,3], "newVal":7}

helper = ImmutableHelper({"obj":{"val":{"x":10,"y":20}}})
assert helper.produce(lambda p: (p["obj"]["val"].__setitem__("x", p["obj"]["val"]["y"]), p["obj"]["val"].__setitem__("y", p["obj"]["val"]["x"]))) == {"obj":{"val":{"x":20,"y":10}}}

# Edge cases
helper = ImmutableHelper({})
assert helper.produce(lambda p: None) == {}  # No mutation

helper = ImmutableHelper({"nested": {"a": 1}})
assert helper.produce(lambda p: p["nested"].__setitem__("a", 2)) == {"nested": {"a": 2}}

| Test | Why