Facebook Pixel

2692. Make Object Immutable 🔒

Medium
Leetcode Link

Problem Description

This problem asks you to create a function makeImmutable that takes a JavaScript object or array and returns a new version that cannot be modified. The returned object should behave exactly like the original but throw specific error messages when any modification is attempted.

The function should handle three types of modifications:

  1. Object property modification: When trying to change a property of an object (e.g., obj.x = 6), it should throw the string Error Modifying: ${key} where key is the property name being modified.

  2. Array index modification: When trying to change an element at a specific index in an array (e.g., arr[0] = 5), it should throw the string Error Modifying Index: ${index} where index is the array index being modified.

  3. Array mutating methods: When trying to call methods that modify an array in place (pop, push, shift, unshift, splice, sort, reverse), it should throw the string Error Calling Method: ${methodName} where methodName is the name of the method being called.

The immutability should apply recursively to all nested objects and arrays within the original object. This means if you have an object containing other objects or arrays, all levels should become immutable.

Important requirements:

  • The input obj is guaranteed to be a valid JSON object or array (output of JSON.parse())
  • The function should throw string literals directly, not Error objects
  • The original object structure and values should remain accessible for reading
  • Only modifications should be prevented, not access to values

For example, if you create an immutable object with {x: 5}, you can still read obj.x to get 5, but attempting obj.x = 6 would throw "Error Modifying: x".

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

To make an object immutable in JavaScript, we need to intercept and prevent any modification attempts. The natural tool for this is the Proxy object, which allows us to trap and customize operations performed on objects.

The key insight is that we need different behaviors for different types of modifications:

  • Objects need to prevent property assignments
  • Arrays need to prevent both index assignments and method calls that mutate the array
  • The immutability must work at all levels of nesting

Since we're dealing with potentially nested structures, we need to traverse the entire object tree recursively. For each level, we wrap the object or array with a Proxy that intercepts the specific operations we want to prevent.

For objects and arrays, we can use the set trap in the Proxy handler to intercept any assignment operations. When someone tries to set a property or index, we throw the appropriate error message instead of allowing the modification.

The tricky part is handling array mutating methods. These methods (pop, push, etc.) are functions that exist as properties on the array. We can't just prevent calling all functions because there are non-mutating methods like map or filter that should still work. The solution is to specifically wrap only the mutating methods with their own Proxy using the apply trap, which intercepts function calls.

The recursive approach ensures that even deeply nested objects become immutable. As we traverse the structure with DFS (depth-first search), we first process all nested objects/arrays, then wrap the current level with the appropriate Proxy handler. This bottom-up approach ensures that by the time we return from the recursion, every level has been properly protected.

The use of different handlers (arrayHandler, objectHandler, fnHandler) keeps the code organized and makes it clear which type of operation is being intercepted at each level.

Solution Approach

The solution uses JavaScript's Proxy API with a recursive depth-first search to create an immutable version of the input object. Here's how the implementation works:

1. Define Proxy Handlers

First, we create three different proxy handlers for different interception needs:

  • arrayHandler: Intercepts set operations on arrays (index modifications)

    set: (_, prop) => {
    throw `Error Modifying Index: ${String(prop)}`;
}

  • objectHandler: Intercepts set operations on objects (property modifications)

    set: (_, prop) => {
    throw `Error Modifying: ${String(prop)}`;
}

  • fnHandler: Intercepts apply operations on functions (method calls)

    apply: target => {
    throw `Error Calling Method: ${target.name}`;
}

2. Define Mutating Methods List

We maintain a list of array methods that mutate the array:

const fn = ['pop', 'push', 'shift', 'unshift', 'splice', 'sort', 'reverse'];

3. Recursive DFS Traversal

The core logic uses a depth-first search function dfs that:

  • Recursively processes nested objects: Iterates through all properties of the current object/array. If a property is an object (and not null), recursively applies dfs to make it immutable.

    for (const key in obj) {
    if (typeof obj[key] === 'object' && obj[key] !== null) {
        obj[key] = dfs(obj[key]);
    }
}

  • Handles arrays specially: If the current item is an array:

    • Wraps each mutating method with fnHandler proxy to prevent their execution
    • Returns the array wrapped in arrayHandler proxy to prevent index modifications
    if (Array.isArray(obj)) {
    fn.forEach(f => (obj[f] = new Proxy(obj[f], fnHandler)));
    return new Proxy(obj, arrayHandler);
}

  • Handles regular objects: For non-array objects, simply wraps them with objectHandler proxy

    return new Proxy(obj, objectHandler);

4. Order of Operations

The algorithm processes the structure bottom-up:

  1. First, it goes deep into nested structures
  2. Makes nested objects/arrays immutable
  3. Then wraps the current level with appropriate proxy handlers
  4. This ensures complete immutability from the deepest level to the root

This approach ensures that any attempt to modify the object at any level will be intercepted and throw the appropriate error message, while still allowing read access to all properties and non-mutating operations.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate how the solution works:

Initial Object:

const obj = {
    x: 5,
    nested: {
        y: 10
    },
    arr: [1, 2, 3]
};

Step 1: DFS starts at root level

  • The function begins with dfs(obj)
  • It iterates through each property: x, nested, and arr

Step 2: Process x: 5

  • x is a primitive value (number), so no recursion needed
  • It remains as is

Step 3: Process nested: {y: 10}

  • nested is an object, so we recursively call dfs({y: 10})
  • Inside this recursive call:
    • y is primitive, so it stays unchanged
    • The object {y: 10} gets wrapped with objectHandler proxy
    • Returns a proxied version of {y: 10}
  • Back at root level, obj.nested now points to the immutable nested object

Step 4: Process arr: [1, 2, 3]

  • arr is an array (which is also an object), so we recursively call dfs([1, 2, 3])
  • Inside this recursive call:
    • Elements 1, 2, 3 are primitives, so they stay unchanged
    • Since it's an array:
      • Each mutating method (pop, push, etc.) gets wrapped with fnHandler proxy
      • The entire array gets wrapped with arrayHandler proxy
    • Returns a proxied array
  • Back at root level, obj.arr now points to the immutable array

Step 5: Wrap root object

  • After processing all properties, the root object itself gets wrapped with objectHandler proxy
  • Returns the fully immutable object

Result - Testing the immutable object:

const immutableObj = makeImmutable(obj);

// Reading works fine:
console.log(immutableObj.x);           // 5
console.log(immutableObj.nested.y);    // 10
console.log(immutableObj.arr[0]);      // 1

// Modifications throw errors:
immutableObj.x = 6;                    // Throws: "Error Modifying: x"
immutableObj.nested.y = 20;            // Throws: "Error Modifying: y"
immutableObj.arr[0] = 99;              // Throws: "Error Modifying Index: 0"
immutableObj.arr.push(4);              // Throws: "Error Calling Method: push"

The key insight is that the DFS processes the structure bottom-up, ensuring every level is protected before returning to the parent level. This creates a complete chain of proxies that intercept any modification attempt at any depth.

Solution Implementation

1from typing import Any, Union, List, Dict, Callable
2
3# Type definition for objects that can be made immutable
4Obj = Union[List[Any], Dict[Any, Any]]
5
6def make_immutable(obj: Obj) -> Obj:
7    """
8    Makes an object deeply immutable by creating a custom proxy class to intercept modifications
9  
10    Args:
11        obj: The object or list to make immutable
12      
13    Returns:
14        A deeply immutable version of the input object
15    """
16  
17    # List of array mutating methods to intercept
18    mutating_methods = ['pop', 'append', 'extend', 'insert', 'remove', 'clear', 'sort', 'reverse']
19  
20    class ImmutableList(list):
21        """Proxy class for immutable lists"""
22      
23        def __setitem__(self, key, value):
24            """Intercept item assignment"""
25            raise Exception(f"Error Modifying Index: {key}")
26      
27        def __delitem__(self, key):
28            """Intercept item deletion"""
29            raise Exception(f"Error Modifying Index: {key}")
30      
31        def _create_blocked_method(self, method_name):
32            """Create a blocked version of a mutating method"""
33            def blocked_method(*args, **kwargs):
34                raise Exception(f"Error Calling Method: {method_name}")
35            return blocked_method
36  
37    class ImmutableDict(dict):
38        """Proxy class for immutable dictionaries"""
39      
40        def __setitem__(self, key, value):
41            """Intercept item assignment"""
42            raise Exception(f"Error Modifying: {key}")
43      
44        def __delitem__(self, key):
45            """Intercept item deletion"""
46            raise Exception(f"Error Modifying: {key}")
47      
48        def pop(self, *args, **kwargs):
49            """Block pop method"""
50            raise Exception("Error Calling Method: pop")
51      
52        def popitem(self):
53            """Block popitem method"""
54            raise Exception("Error Calling Method: popitem")
55      
56        def clear(self):
57            """Block clear method"""
58            raise Exception("Error Calling Method: clear")
59      
60        def update(self, *args, **kwargs):
61            """Block update method"""
62            raise Exception("Error Calling Method: update")
63      
64        def setdefault(self, *args, **kwargs):
65            """Block setdefault method"""
66            raise Exception("Error Calling Method: setdefault")
67  
68    def deep_freeze(current_obj: Obj) -> Obj:
69        """
70        Recursively traverses and creates immutable versions of nested objects
71      
72        Args:
73            current_obj: The current object being processed
74          
75        Returns:
76            An immutable version of the object with immutability enforced
77        """
78      
79        # Handle lists: create immutable list and process nested objects
80        if isinstance(current_obj, list):
81            # Create new immutable list with processed elements
82            immutable_list = ImmutableList()
83            for item in current_obj:
84                if isinstance(item, (list, dict)) and item is not None:
85                    immutable_list.append(deep_freeze(item))
86                else:
87                    immutable_list.append(item)
88          
89            # Override mutating methods with blocked versions
90            for method_name in mutating_methods:
91                if hasattr(immutable_list, method_name):
92                    # Handle 'append' -> 'append', 'extend' -> 'extend', etc.
93                    if method_name in ['append', 'extend', 'insert', 'remove', 'clear']:
94                        setattr(immutable_list, method_name, 
95                               immutable_list._create_blocked_method(method_name))
96                    elif method_name == 'pop':
97                        setattr(immutable_list, method_name, 
98                               immutable_list._create_blocked_method('pop'))
99                    elif method_name == 'sort':
100                        setattr(immutable_list, method_name, 
101                               immutable_list._create_blocked_method('sort'))
102                    elif method_name == 'reverse':
103                        setattr(immutable_list, method_name, 
104                               immutable_list._create_blocked_method('reverse'))
105          
106            return immutable_list
107      
108        # Handle dictionaries: create immutable dict and process nested objects
109        elif isinstance(current_obj, dict):
110            # Create new immutable dict with processed values
111            immutable_dict = ImmutableDict()
112            for key, value in current_obj.items():
113                if isinstance(value, (list, dict)) and value is not None:
114                    immutable_dict[key] = deep_freeze(value)
115                else:
116                    immutable_dict[key] = value
117          
118            return immutable_dict
119      
120        # Return non-container objects as-is
121        return current_obj
122  
123    return deep_freeze(obj)
124
125
126# Example usage:
127# obj = make_immutable({'x': 5})
128# obj['x'] = 6  # raises "Error Modifying: x"
129# 
130# arr = make_immutable([1, 2, 3])
131# arr[0] = 4  # raises "Error Modifying Index: 0"
132# arr.append(4)  # raises "Error Calling Method: append"
133
1import java.lang.reflect.InvocationHandler;
2import java.lang.reflect.Method;
3import java.lang.reflect.Proxy;
4import java.util.*;
5
6/**
7 * Utility class for creating deeply immutable objects and arrays
8 */
9public class ImmutableObjectFactory {
10  
11    /**
12     * List of array mutating methods to intercept
13     */
14    private static final Set<String> MUTATING_METHODS = new HashSet<>(Arrays.asList(
15        "add", "remove", "clear", "set", "addAll", "removeAll", 
16        "retainAll", "sort", "replaceAll"
17    ));
18  
19    /**
20     * Makes an object deeply immutable by using Proxy to intercept modifications
21     * @param obj The object or list to make immutable
22     * @return A deeply immutable version of the input object
23     */
24    @SuppressWarnings("unchecked")
25    public static Object makeImmutable(Object obj) {
26        if (obj == null) {
27            return null;
28        }
29      
30        return deepFreeze(obj);
31    }
32  
33    /**
34     * Recursively traverses and proxies nested objects
35     * @param currentObj The current object being processed
36     * @return A proxied version of the object with immutability enforced
37     */
38    private static Object deepFreeze(Object currentObj) {
39        // Handle primitive types and null
40        if (currentObj == null || isPrimitive(currentObj)) {
41            return currentObj;
42        }
43      
44        // Process List objects
45        if (currentObj instanceof List) {
46            List<?> list = (List<?>) currentObj;
47            // Recursively process all nested objects in the list
48            List<Object> processedList = new ArrayList<>();
49            for (Object item : list) {
50                if (item != null && !isPrimitive(item)) {
51                    processedList.add(deepFreeze(item));
52                } else {
53                    processedList.add(item);
54                }
55            }
56          
57            // Create proxy for the list with array handler
58            return createListProxy(processedList);
59        }
60      
61        // Process Map objects (similar to JavaScript objects)
62        if (currentObj instanceof Map) {
63            Map<?, ?> map = (Map<?, ?>) currentObj;
64            // Recursively process all nested objects in the map
65            Map<Object, Object> processedMap = new HashMap<>();
66            for (Map.Entry<?, ?> entry : map.entrySet()) {
67                Object value = entry.getValue();
68                if (value != null && !isPrimitive(value)) {
69                    processedMap.put(entry.getKey(), deepFreeze(value));
70                } else {
71                    processedMap.put(entry.getKey(), value);
72                }
73            }
74          
75            // Create proxy for the map with object handler
76            return createMapProxy(processedMap);
77        }
78      
79        // For other objects, create a general immutable proxy
80        return createObjectProxy(currentObj);
81    }
82  
83    /**
84     * Creates a proxy for List objects to prevent modifications
85     * @param list The list to proxy
86     * @return A proxied immutable list
87     */
88    @SuppressWarnings("unchecked")
89    private static <T> List<T> createListProxy(List<T> list) {
90        return (List<T>) Proxy.newProxyInstance(
91            list.getClass().getClassLoader(),
92            new Class[]{List.class},
93            new ListInvocationHandler(list)
94        );
95    }
96  
97    /**
98     * Creates a proxy for Map objects to prevent modifications
99     * @param map The map to proxy
100     * @return A proxied immutable map
101     */
102    @SuppressWarnings("unchecked")
103    private static <K, V> Map<K, V> createMapProxy(Map<K, V> map) {
104        return (Map<K, V>) Proxy.newProxyInstance(
105            map.getClass().getClassLoader(),
106            new Class[]{Map.class},
107            new MapInvocationHandler(map)
108        );
109    }
110  
111    /**
112     * Creates a general proxy for objects to prevent modifications
113     * @param obj The object to proxy
114     * @return A proxied immutable object
115     */
116    private static Object createObjectProxy(Object obj) {
117        Class<?>[] interfaces = obj.getClass().getInterfaces();
118        if (interfaces.length == 0) {
119            // If no interfaces, return the object as-is (cannot proxy)
120            return obj;
121        }
122      
123        return Proxy.newProxyInstance(
124            obj.getClass().getClassLoader(),
125            interfaces,
126            new ObjectInvocationHandler(obj)
127        );
128    }
129  
130    /**
131     * Checks if an object is a primitive type or wrapper
132     * @param obj The object to check
133     * @return true if the object is primitive or primitive wrapper
134     */
135    private static boolean isPrimitive(Object obj) {
136        return obj instanceof String ||
137               obj instanceof Number ||
138               obj instanceof Boolean ||
139               obj instanceof Character;
140    }
141  
142    /**
143     * InvocationHandler for List objects (equivalent to array handler)
144     */
145    private static class ListInvocationHandler implements InvocationHandler {
146        private final List<?> target;
147      
148        public ListInvocationHandler(List<?> target) {
149            this.target = target;
150        }
151      
152        @Override
153        public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
154            String methodName = method.getName();
155          
156            // Check for mutating methods
157            if (MUTATING_METHODS.contains(methodName)) {
158                throw new UnsupportedOperationException("Error Calling Method: " + methodName);
159            }
160          
161            // Check for index-based modifications
162            if ("set".equals(methodName) && args != null && args.length > 0) {
163                throw new UnsupportedOperationException("Error Modifying Index: " + args[0]);
164            }
165          
166            // Allow read-only operations
167            if ("get".equals(methodName) || "size".equals(methodName) || 
168                "isEmpty".equals(methodName) || "contains".equals(methodName) ||
169                "iterator".equals(methodName) || "toArray".equals(methodName)) {
170                return method.invoke(target, args);
171            }
172          
173            // Block all other operations
174            throw new UnsupportedOperationException("Error Calling Method: " + methodName);
175        }
176    }
177  
178    /**
179     * InvocationHandler for Map objects (equivalent to object handler)
180     */
181    private static class MapInvocationHandler implements InvocationHandler {
182        private final Map<?, ?> target;
183      
184        public MapInvocationHandler(Map<?, ?> target) {
185            this.target = target;
186        }
187      
188        @Override
189        public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
190            String methodName = method.getName();
191          
192            // Check for property modifications
193            if ("put".equals(methodName) || "putAll".equals(methodName)) {
194                String property = args != null && args.length > 0 ? String.valueOf(args[0]) : "unknown";
195                throw new UnsupportedOperationException("Error Modifying: " + property);
196            }
197          
198            // Block removing operations
199            if ("remove".equals(methodName) || "clear".equals(methodName)) {
200                throw new UnsupportedOperationException("Error Modifying: " + 
201                    (args != null && args.length > 0 ? String.valueOf(args[0]) : "property"));
202            }
203          
204            // Allow read-only operations
205            if ("get".equals(methodName) || "size".equals(methodName) || 
206                "isEmpty".equals(methodName) || "containsKey".equals(methodName) ||
207                "containsValue".equals(methodName) || "keySet".equals(methodName) ||
208                "values".equals(methodName) || "entrySet".equals(methodName)) {
209                return method.invoke(target, args);
210            }
211          
212            // Block all other operations
213            throw new UnsupportedOperationException("Error Calling Method: " + methodName);
214        }
215    }
216  
217    /**
218     * General InvocationHandler for objects
219     */
220    private static class ObjectInvocationHandler implements InvocationHandler {
221        private final Object target;
222      
223        public ObjectInvocationHandler(Object target) {
224            this.target = target;
225        }
226      
227        @Override
228        public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
229            String methodName = method.getName();
230          
231            // Block setter methods
232            if (methodName.startsWith("set")) {
233                String property = methodName.substring(3);
234                throw new UnsupportedOperationException("Error Modifying: " + property);
235            }
236          
237            // Allow getter methods and other read operations
238            if (methodName.startsWith("get") || methodName.startsWith("is") || 
239                "toString".equals(methodName) || "hashCode".equals(methodName) ||
240                "equals".equals(methodName)) {
241                return method.invoke(target, args);
242            }
243          
244            // Block all other operations
245            throw new UnsupportedOperationException("Error Calling Method: " + methodName);
246        }
247    }
248  
249    /**
250     * Example usage:
251     * Map<String, Object> obj = new HashMap<>();
252     * obj.put("x", 5);
253     * Map<String, Object> immutableObj = (Map<String, Object>) makeImmutable(obj);
254     * immutableObj.put("x", 6); // throws "Error Modifying: x"
255     * 
256     * List<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 3));
257     * List<Integer> immutableArr = (List<Integer>) makeImmutable(arr);
258     * immutableArr.set(0, 4); // throws "Error Modifying Index: 0"
259     * immutableArr.add(4); // throws "Error Calling Method: add"
260     */
261}
262
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <any>
5#include <string>
6#include <memory>
7#include <functional>
8#include <stdexcept>
9#include <variant>
10
11// Type definition for objects that can be made immutable
12// Using variant to represent either vector or map types
13using Obj = std::variant<std::vector<std::any>, std::unordered_map<std::string, std::any>>;
14
15/**
16 * Template class to create immutable wrappers for containers
17 * Intercepts and blocks all modification attempts
18 */
19template<typename T>
20class ImmutableWrapper {
21private:
22    T data_;
23  
24public:
25    explicit ImmutableWrapper(const T& data) : data_(data) {}
26  
27    // Getter for read-only access
28    const T& getData() const { return data_; }
29};
30
31/**
32 * Immutable vector class that prevents modifications
33 */
34class ImmutableVector {
35private:
36    std::vector<std::any> data_;
37  
38public:
39    explicit ImmutableVector(const std::vector<std::any>& vec) : data_(vec) {
40        // Recursively make nested objects immutable
41        makeNestedImmutable();
42    }
43  
44    // Read-only access by index
45    const std::any& operator[](size_t index) const {
46        return data_[index];
47    }
48  
49    // Block set operations - throw error when trying to modify
50    void set(size_t index, const std::any& value) {
51        throw std::runtime_error("Error Modifying Index: " + std::to_string(index));
52    }
53  
54    // Block mutating methods
55    void pop() {
56        throw std::runtime_error("Error Calling Method: pop");
57    }
58  
59    void push(const std::any& value) {
60        throw std::runtime_error("Error Calling Method: push");
61    }
62  
63    void shift() {
64        throw std::runtime_error("Error Calling Method: shift");
65    }
66  
67    void unshift(const std::any& value) {
68        throw std::runtime_error("Error Calling Method: unshift");
69    }
70  
71    void splice(size_t start, size_t deleteCount) {
72        throw std::runtime_error("Error Calling Method: splice");
73    }
74  
75    void sort() {
76        throw std::runtime_error("Error Calling Method: sort");
77    }
78  
79    void reverse() {
80        throw std::runtime_error("Error Calling Method: reverse");
81    }
82  
83    size_t size() const { return data_.size(); }
84  
85private:
86    void makeNestedImmutable();
87};
88
89/**
90 * Immutable map class that prevents modifications
91 */
92class ImmutableMap {
93private:
94    std::unordered_map<std::string, std::any> data_;
95  
96public:
97    explicit ImmutableMap(const std::unordered_map<std::string, std::any>& map) : data_(map) {
98        // Recursively make nested objects immutable
99        makeNestedImmutable();
100    }
101  
102    // Read-only access by key
103    const std::any& get(const std::string& key) const {
104        auto it = data_.find(key);
105        if (it != data_.end()) {
106            return it->second;
107        }
108        throw std::runtime_error("Key not found: " + key);
109    }
110  
111    // Block set operations - throw error when trying to modify
112    void set(const std::string& key, const std::any& value) {
113        throw std::runtime_error("Error Modifying: " + key);
114    }
115  
116    bool hasKey(const std::string& key) const {
117        return data_.find(key) != data_.end();
118    }
119  
120private:
121    void makeNestedImmutable();
122};
123
124// Forward declaration for recursive calls
125std::any makeImmutable(const std::any& obj);
126
127/**
128 * Implementation of makeNestedImmutable for ImmutableVector
129 * Recursively processes nested objects within the vector
130 */
131void ImmutableVector::makeNestedImmutable() {
132    for (auto& item : data_) {
133        // Check if the item is an object that needs to be made immutable
134        if (item.type() == typeid(std::vector<std::any>) || 
135            item.type() == typeid(std::unordered_map<std::string, std::any>)) {
136            item = makeImmutable(item);
137        }
138    }
139}
140
141/**
142 * Implementation of makeNestedImmutable for ImmutableMap
143 * Recursively processes nested objects within the map
144 */
145void ImmutableMap::makeNestedImmutable() {
146    for (auto& [key, value] : data_) {
147        // Check if the value is an object that needs to be made immutable
148        if (value.type() == typeid(std::vector<std::any>) || 
149            value.type() == typeid(std::unordered_map<std::string, std::any>)) {
150            value = makeImmutable(value);
151        }
152    }
153}
154
155/**
156 * Makes an object deeply immutable by creating immutable wrapper classes
157 * @param obj - The object (vector or map) to make immutable
158 * @returns A deeply immutable version of the input object wrapped in std::any
159 */
160std::any makeImmutable(const std::any& obj) {
161    // Handle vector type
162    if (obj.type() == typeid(std::vector<std::any>)) {
163        const auto& vec = std::any_cast<const std::vector<std::any>&>(obj);
164        return std::make_shared<ImmutableVector>(vec);
165    }
166  
167    // Handle map type
168    if (obj.type() == typeid(std::unordered_map<std::string, std::any>)) {
169        const auto& map = std::any_cast<const std::unordered_map<std::string, std::any>&>(obj);
170        return std::make_shared<ImmutableMap>(map);
171    }
172  
173    // Return as-is for non-object types
174    return obj;
175}
176
177/**
178 * Example usage:
179 * auto obj = makeImmutable(std::unordered_map<std::string, std::any>{{"x", 5}});
180 * // Attempting to modify will throw "Error Modifying: x"
181 * 
182 * auto arr = makeImmutable(std::vector<std::any>{1, 2, 3});
183 * // Attempting to modify index will throw "Error Modifying Index: 0"
184 * // Attempting to call push will throw "Error Calling Method: push"
185 */
186
1// Type definition for objects that can be made immutable
2type Obj = Array<any> | Record<any, any>;
3
4/**
5 * Makes an object deeply immutable by using Proxy to intercept modifications
6 * @param obj - The object or array to make immutable
7 * @returns A deeply immutable version of the input object
8 */
9function makeImmutable(obj: Obj): Obj {
10    // Handler for array property modifications
11    const arrayHandler: ProxyHandler<Array<any>> = {
12        set: (_, property) => {
13            throw `Error Modifying Index: ${String(property)}`;
14        },
15    };
16
17    // Handler for object property modifications
18    const objectHandler: ProxyHandler<Record<any, any>> = {
19        set: (_, property) => {
20            throw `Error Modifying: ${String(property)}`;
21        },
22    };
23
24    // Handler for intercepting method calls
25    const methodHandler: ProxyHandler<Function> = {
26        apply: (target) => {
27            throw `Error Calling Method: ${target.name}`;
28        },
29    };
30
31    // List of array mutating methods to intercept
32    const mutatingMethods = ['pop', 'push', 'shift', 'unshift', 'splice', 'sort', 'reverse'];
33
34    /**
35     * Recursively traverses and proxies nested objects
36     * @param currentObj - The current object being processed
37     * @returns A proxied version of the object with immutability enforced
38     */
39    const deepFreeze = (currentObj: Obj): Obj => {
40        // Recursively process all nested objects
41        for (const key in currentObj) {
42            if (typeof currentObj[key] === 'object' && currentObj[key] !== null) {
43                currentObj[key] = deepFreeze(currentObj[key]);
44            }
45        }
46
47        // Handle arrays: proxy mutating methods and the array itself
48        if (Array.isArray(currentObj)) {
49            mutatingMethods.forEach(methodName => {
50                currentObj[methodName] = new Proxy(currentObj[methodName], methodHandler);
51            });
52            return new Proxy(currentObj, arrayHandler);
53        }
54
55        // Handle regular objects
56        return new Proxy(currentObj, objectHandler);
57    };
58
59    return deepFreeze(obj);
60}
61
62/**
63 * Example usage:
64 * const obj = makeImmutable({x: 5});
65 * obj.x = 6; // throws "Error Modifying: x"
66 * 
67 * const arr = makeImmutable([1, 2, 3]);
68 * arr[0] = 4; // throws "Error Modifying Index: 0"
69 * arr.push(4); // throws "Error Calling Method: push"
70 */
71

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses a depth-first search (DFS) to traverse all properties in the object structure. Each property is visited exactly once during the traversal. For objects with n total properties (including nested properties), the time complexity breaks down as follows:

  • The DFS traversal visits each property once: O(n)
  • For each array encountered, we iterate through the mutating methods list (constant 7 methods) and create proxies: O(7) = O(1) per array
  • Creating a Proxy for each object/array is O(1) operation

Therefore, the overall time complexity is O(n) where n is the total number of properties in the object tree.

Space Complexity: O(n + d)

The space complexity consists of:

  • Proxy wrappers: A new Proxy is created for each object and array in the structure, requiring O(n) space where n is the number of objects/arrays
  • Method proxies: For each array, we create proxies for 7 mutating methods, which adds O(7 * m) = O(m) space where m is the number of arrays
  • Recursion stack: The DFS recursion depth equals the maximum nesting level d of the object structure, requiring O(d) stack space
  • The original object structure is modified in-place (references are replaced with proxies), so no additional space for copying the structure

The total space complexity is O(n + d), where n is the number of objects/arrays in the structure and d is the maximum depth of nesting. In the worst case where the object is deeply nested (like a linked list structure), d could be O(n), making the space complexity O(n).

Common Pitfalls

1. Shallow Copy vs Deep Immutability

One of the most common mistakes is creating only a shallow immutable wrapper without handling nested structures properly. Developers often forget that making an object immutable at the top level doesn't prevent modifications to nested objects.

Pitfall Example:

// Incorrect: Only shallow immutability
function makeImmutableWrong(obj) {
    return new Proxy(obj, {
        set: (_, prop) => {
            throw `Error Modifying: ${prop}`;
        }
    });
}

const obj = makeImmutableWrong({a: {b: 5}});
obj.a = 10;        // ✓ Throws error correctly
obj.a.b = 10;      // ✗ Modifies successfully (should throw error!)

Solution: Always recursively traverse the entire object structure and apply immutability at every level:

function makeImmutable(obj) {
    // First, recursively make all nested objects immutable
    for (const key in obj) {
        if (typeof obj[key] === 'object' && obj[key] !== null) {
            obj[key] = makeImmutable(obj[key]);  // Recursive call
        }
    }
    // Then wrap the current level
    return new Proxy(obj, handler);
}

2. Not Handling Array Methods Properly

Another frequent issue is forgetting that arrays have special mutating methods that need to be intercepted separately from index assignments. Simply wrapping an array with a set trap won't prevent methods like push() or pop() from modifying it.

Pitfall Example:

// Incorrect: Only blocks index assignment
const arrayHandler = {
    set: (_, prop) => {
        throw `Error Modifying Index: ${prop}`;
    }
};

const arr = new Proxy([1, 2, 3], arrayHandler);
arr[0] = 5;        // ✓ Throws error correctly
arr.push(4);       // ✗ Modifies successfully (should throw error!)

Solution: Explicitly wrap each mutating method with a proxy that intercepts the function call:

const mutatingMethods = ['pop', 'push', 'shift', 'unshift', 'splice', 'sort', 'reverse'];

if (Array.isArray(obj)) {
    // Wrap each mutating method
    mutatingMethods.forEach(methodName => {
        obj[methodName] = new Proxy(obj[methodName], {
            apply: () => {
                throw `Error Calling Method: ${methodName}`;
            }
        });
    });
    return new Proxy(obj, arrayHandler);
}

3. Incorrect Error Message Format

The problem requires throwing string literals with specific formats, not Error objects. A common mistake is throwing Error instances or using incorrect string formatting.

Pitfall Example:

// Incorrect: Throwing Error objects
set: (_, prop) => {
    throw new Error(`Error Modifying: ${prop}`);  // Wrong! Should be string
}

// Incorrect: Wrong message format
set: (_, prop) => {
    throw `Cannot modify ${prop}`;  // Wrong format!
}

Solution: Always throw string literals with exact formatting:

// For objects
throw `Error Modifying: ${String(prop)}`;

// For array indices
throw `Error Modifying Index: ${String(prop)}`;

// For methods
throw `Error Calling Method: ${methodName}`;

4. Performance Issues with Large Objects

Creating proxies for every nested object can lead to performance overhead, especially with deeply nested or large objects. Each property access goes through the proxy trap, which adds overhead.

Pitfall: Processing extremely large objects without considering performance implications.

Solution: Consider these optimizations:

  • Cache immutable versions if the same objects are made immutable multiple times
  • Use lazy evaluation for nested objects (only create proxies when accessed)
  • For production use, consider using specialized immutability libraries like Immutable.js that are optimized for performance

5. Forgetting to Check for null

Since typeof null === 'object' in JavaScript, failing to check for null values can cause errors when trying to recursively process them.

Pitfall Example:

// Incorrect: Will try to iterate over null
if (typeof obj[key] === 'object') {
    obj[key] = dfs(obj[key]);  // Error if obj[key] is null!
}

Solution: Always check for null explicitly:

if (typeof obj[key] === 'object' && obj[key] !== null) {
    obj[key] = dfs(obj[key]);
}
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More