2692. Make Object Immutable

Medium
Leetcode Link

Problem Description

The given problem requires the creation of a function that transforms any object or array into an immutable one. An "immutable" object or array is one that cannot be changed after its creation. If an attempt is made to modify it in any way, it should throw a specific error message. The instructions specify three situations where error messages should be returned:

  1. Modifying a property of an object: Attempting to change any property on the object should result in an error with the message in the format Error Modifying: ${key}, where ${key} is the property key attempted to be modified.

  2. Modifying an index of an array: Attempting to change any index on the array should result in an error with the message in the format Error Modifying Index: ${index}, where ${index} is the array index attempted to be modified.

  3. Calling a method that mutates the array: Applying any method that can alter the array (such as 'pop', 'push', 'shift', 'unshift', 'splice', 'sort', 'reverse') should result in an error with the message in the format Error Calling Method: ${methodName}, where ${methodName} is the name of the mutating method that was attempted to be called.

Moreover, the object that will be passed into our function is a regular JSON object or array, which implies that it is a structure that resulted from JSON.parse().

Intuition

To solve this task, the Proxy object in JavaScript is an ideal candidate. A Proxy object is used to define custom behavior for fundamental operations on objects (like property lookup, assignment, enumeration, function invocation, etc.). Therefore, Proxies can be used to create immutable objects by intercepting and customizing operation behaviors.

The approach is to use recursive depth-first search (DFS) to traverse through the given object or array and wrap all objects and arrays within it using Proxy. If the current value is an array, we additionally wrap each of the array's mutating methods in a Proxy.

The solution can be broken down into three main parts:

  1. Handling object property assignments: For objects, we define a Proxy handler that intercepts any attempt to set a property value and instead throws the corresponding error message.

  2. Handling array index assignments: Similarly, for arrays, we define another Proxy handler that intercepts any attempt to set a value at an array index and throws the relevant error message.

  3. Handling mutating method calls on arrays: Lastly, for arrays, we define a third Proxy handler that intercepts any call to a mutating method and throws the appropriate error message.

By wrapping each of these parts in a Proxy with the corresponding handler, we ensure that any attempts to mutate the object or array will be caught and the appropriate error will be thrown, effectively achieving immutability.

Solution Approach

The provided TypeScript solution employs a design pattern commonly known as a Proxy to wrap objects, arrays, and certain methods to intercept operations that modify them. When such operations are attempted, the Proxy intercepts them and throws a string literal representing the appropriate error message.

Here's a step-by-step breakdown of the approach:

Wrapping in Proxy using Recursive DFS

  • The dfs function is employed to perform a depth-first search on the input object (or array). This function recursively processes each property or element in the object/array.
  • If a property's value is an object or array (determined using typeof obj[key] === 'object' and obj[key] !== null), the function is recursively called for that value (nested structure).
  • This ensures that every nested object or array within the original input is processed and wrapped in a Proxy if necessary.

Handling Array Mutations

  • Once a nested structure is identified as an array, each of the specified mutating methods is wrapped in a Proxy using the fnHandler. This handler intercepts and throws an error if one of the mutating methods ('pop', 'push', 'shift', 'unshift', 'splice', 'sort', 'reverse') is called.
  • A separate Proxy, with arrayHandler as the handler, wraps the array itself. This handles any attempts to modify an array's indices directly, such as array[1] = 'new value';.

Preventing Object Mutations

  • If the nested structure is an object, the objectHandler handler is used to wrap it in a Proxy. This prevents any property assignments, such as obj.prop = 'new value';.

Error Handling and Proxy Handlers

  • The Proxy handlers (arrayHandler, objectHandler, and fnHandler) utilize the set trap (for properties and indices) and the apply trap (for function application) to catch attempted modifications or function calls.
  • When a trap is triggered, the corresponding error message is thrown. For example, if set is invoked on a property, the error Error Modifying: ${String(prop)} is thrown. For a mutating method call, Error Calling Method: ${target.name} is the error.

Finalizing and Returning the Immutable Structure

  • After wrapping the object/array elements with the appropriate Proxies, the dfs function ensures the modified structure is returned up the call stack.
  • The initial call to dfs from the makeImmutable function returns the fully processed and now immutable (through Proxies) object or array.

By using Proxies and this recursive strategy, the code ensures that any attempt to alter the original structure of the given object or array at any level throws an error and prevents the alteration, effectively making the structure immutable.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's go through a small example to illustrate the solution approach. Suppose we have an object like this:

let mutableObject = {
    user: {
        name: "Alice",
        age: 30
    },
    scores: [78, 95, 88]
};

Our goal is to make this object immutable using the solution approach described. We'll invoke our makeImmutable function with mutableObject as the argument. Here's what happens in the background:

  1. The dfs function is called, which starts to traverse the mutableObject.
  2. It encounters an object at mutableObject.user, which it then wraps in a Proxy with the objectHandler.
    • Now, if we try to do something like mutableObject.user.age = 31;, it will throw an error: Error Modifying: age.
  3. It then encounters an array at mutableObject.scores.
    • Each mutating array method such as push, pop, etc., is wrapped in a Proxy with the fnHandler. Any subsequent call like mutableObject.scores.push(100); will throw an error: Error Calling Method: push.
    • The array itself is also wrapped in a Proxy with the arrayHandler. An attempted index modification like mutableObject.scores[0] = 79; results in Error Modifying Index: 0.

After the process completes, any attempt to alter mutableObject will result in an error, and the structure becomes effectively immutable. For example:

// Example execution after making mutableObject immutable
const immutableObject = makeImmutable(mutableObject);

try {
    immutableObject.user.name = "Bob";
} catch (e) {
    console.log(e); // Output: Error Modifying: name
}

try {
    immutableObject.scores[1] = 100;
} catch (e) {
    console.log(e); // Output: Error Modifying Index: 1
}

try {
    immutableObject.scores.push(100);
} catch (e) {
    console.log(e); // Output: Error Calling Method: push
}

By utilizing Proxies combined with the recursive depth-first search, the example shows how the original object mutableObject is transformed into immutableObject, which preserves the original state by preventing any modifications.

Solution Implementation

1from types import FunctionType
2from collections.abc import MutableMapping, MutableSequence
3
4# Define a type for objects that can be either lists or dictionaries.
5ImmutableObject = MutableSequence | MutableMapping
6
7# This function takes an object and returns an immutable version of it.
8# Any attempt to modify the object will raise a runtime error.
9def make_immutable(obj: ImmutableObject) -> ImmutableObject:
10  
11    # Function to raise an error for an attempted property modification.
12    def error_modifier(property_name):
13        raise AttributeError(f"Error Modifying Property: {property_name}")
14
15    # Function to raise an error for an attempted method call.
16    def error_calling_method(method_name):
17        raise AttributeError(f"Error Calling Method: {method_name}")
18
19    # Wrapper that prevents attribute setting and method calls on objects.
20    class FrozenObject:
21        def __init__(self, obj):
22            object.__setattr__(self, '_obj', obj)
23      
24        def __setattr__(self, key, value):
25            error_modifier(key)
26
27        def __getitem__(self, key):
28            return object.__getitem__(self._obj, key)
29
30        def __setitem__(self, key, value):
31            error_modifier(key)
32
33        def __getattr__(self, item):
34            attr = getattr(self._obj, item)
35            if isinstance(attr, FunctionType):
36                if item in modifying_methods:
37                    return lambda *args, **kwargs: error_calling_method(item)
38                else:
39                    return attr
40            else:
41                return attr
42
43    # List of method names that modify the list. These will be disabled.
44    modifying_methods = ['pop', 'push', 'append', 'extend', 'insert', 'remove', 'sort', 'reverse', 'clear']
45
46    # Recursive function to convert all nested objects and lists into immutable versions.
47    def deep_freeze(current_obj: ImmutableObject) -> ImmutableObject:
48        if isinstance(current_obj, dict):
49            for key, value in current_obj.items():
50                if isinstance(value, (dict, list)):
51                    current_obj[key] = deep_freeze(value)
52        elif isinstance(current_obj, list):
53            for index in range(len(current_obj)):
54                if isinstance(current_obj[index], (dict, list)):
55                    current_obj[index] = deep_freeze(current_obj[index])
56      
57        return FrozenObject(current_obj)
58
59    # Start the deep freeze process from the root object.
60    return deep_freeze(obj)
61
62# Usage example:
63# my_immutable_obj = make_immutable({'x': 5})
64# my_immutable_obj.x = 6  # Raises "AttributeError: Error Modifying Property: x"
65
1import java.lang.reflect.Array;
2import java.lang.reflect.Proxy;
3import java.util.HashMap;
4import java.util.Map;
5import java.util.List;
6
7public class ImmutableObjectHelper {
8  
9    // This interface defines a type that can be either a List or a Map.
10    public interface ImmutableObject {}
11
12    // This function takes an object and returns an immutable version of it.
13    // Any attempt to modify the object will result in a runtime error.
14    public static ImmutableObject makeImmutable(ImmutableObject obj) {
15        // Begin the process of deep freezing the given object.
16        return deepFreeze(obj);
17    }
18
19    // Proxy handler for Lists to prevent modification operations.
20    private static InvocationHandler listHandler = (proxy, method, args) -> {
21        throw new UnsupportedOperationException("Error Modifying Method: " + method.getName());
22    };
23
24    // Proxy handler for Maps to prevent modification operations.
25    private static InvocationHandler mapHandler = (proxy, method, args) -> {
26        throw new UnsupportedOperationException("Error Modifying Property: " + method.getName());
27    };
28
29    // Recursive function to convert all nested Maps and Lists into immutable versions.
30    private static ImmutableObject deepFreeze(ImmutableObject currentObj) {
31        // Proxy Maps (similar to records or plain objects in TypeScript) with a handler to block modifications.
32        if (currentObj instanceof Map) {
33            Map<?, ?> currentMap = (Map<?, ?>) currentObj;
34            Map<Object, Object> newMap = new HashMap<>();
35            currentMap.forEach((k, v) -> {
36                if (v instanceof ImmutableObject) {
37                    newMap.put(k, deepFreeze((ImmutableObject) v));
38                } else {
39                    newMap.put(k, v);
40                }
41            });
42            return (ImmutableObject) Proxy.newProxyInstance(
43                ImmutableObject.class.getClassLoader(),
44                new Class[]{Map.class}, 
45                mapHandler
46            );
47        }
48      
49        // Proxy Lists (equivalent to Arrays in TypeScript) with a handler to block modifications.
50        if (currentObj instanceof List) {
51            return (ImmutableObject) Proxy.newProxyInstance(
52                ImmutableObject.class.getClassLoader(),
53                new Class[]{List.class},
54                listHandler
55            );
56        }
57      
58        return currentObj;
59    }
60  
61    // Usage example:
62    public static void main(String[] args) {
63        Map<String, Object> mutableObj = new HashMap<>();
64        mutableObj.put("x", 5);
65        ImmutableObject myImmutableObj = makeImmutable(mutableObj);
66        // The next line would throw an exception:
67        // ((Map)myImmutableObj).put("x", 6);
68    }
69}
70
1#include <iostream>
2#include <vector>
3#include <map>
4#include <functional>
5#include <stdexcept>
6
7// Define a variant type for objects that can be either vectors or maps.
8using ImmutableObject = std::variant<std::vector<any>, std::map<any, any>>;
9
10// This function takes an object and returns an immutable version of it.
11// Any attempt to modify the object will result in a runtime error.
12ImmutableObject MakeImmutable(const ImmutableObject& obj) {
13    // Visitor that handles the respective types of objects (vectors or maps).
14    class : public std::visitor<ImmutableObject> {
15    public:
16        // Handle vector type (immutable array in the JavaScript equivalent)
17        ImmutableObject operator()(const std::vector<any>& vec) const {
18            std::vector<any> immutableVec(vec);  // Make a copy to ensure the original is not modified.
19
20            // Disable methods that would modify the vector.
21            // Note: C++ does not directly allow the proxying of individual functions as JavaScript does.
22            // This would need to be handled by providing a custom vector implementation or another method.
23            // For this example, assume we've disabled them by an unspecified mechanism.
24            // DisableModifyingMethods(immutableVec);
25
26            return immutableVec;
27        }
28
29        // Handle map type (immutable object in the JavaScript equivalent)
30        ImmutableObject operator()(const std::map<any, any>& map) const {
31            std::map<any, any> immutableMap(map);  // Make a copy to ensure the original is not modified.
32          
33            // Create a proxy object that would throw an exception upon modification.
34            // Note: C++ does not have a built-in Proxy equivalent as JavaScript does.
35            // Proxying would need to be handled by providing custom methods or another approach.
36            // For this example, assume we've proxied it by an unspecified mechanism.
37            // ProxyModifyingOperations(immutableMap);
38
39            return immutableMap;
40        }
41    } visitor;
42
43    // Apply the visitor to the object to make it immutable.
44    return std::visit(visitor, obj);
45}
46
47// In C++, we can't simply emulate the JavaScript behavior of making objects immutable at runtime due to
48// language constraints. Proxying would require a different approach, like using custom classes to prevent
49// modifications, using const wherever possible, and/or making use of C++'s strong type system to limit
50// access to modification methods. However, neither proxies nor runtime type mutation are idiomatic C++.
51
52// Usage example:
53// std::map<any, any> myMap = {{std::string("x"), 5}};
54// auto myImmutableObj = MakeImmutable(myMap);
55// myImmutableObj["x"] = 6; // This operation would throw an error, if we had a proxy mechanism in place.
56
57int main() {
58    // Usage demonstration goes here.
59    return 0;
60}
61
1// Define a type for objects that can be either arrays or plain objects.
2type ImmutableObject = Array<any> | Record<any, any>;
3
4// This function takes an object and returns an immutable version of it.
5// Any attempt to modify the object will result in a runtime error.
6function makeImmutable(obj: ImmutableObject): ImmutableObject {
7    // Proxy handler for arrays to prevent modification operations.
8    const arrayHandler: ProxyHandler<Array<any>> = {
9        set: (_, property) => {
10            throw new Error(`Error Modifying Index: ${String(property)}`);
11        },
12    };
13
14    // Proxy handler for objects to prevent modification operations.
15    const objectHandler: ProxyHandler<Record<any, any>> = {
16        set: (_, property) => {
17            throw new Error(`Error Modifying Property: ${String(property)}`);
18        },
19    };
20
21    // Proxy handler for functions to prevent them from being called.
22    // This is specifically used to disable array-modifying methods.
23    const functionHandler: ProxyHandler<Function> = {
24        apply: target => {
25            throw new Error(`Error Calling Method: ${target.name}`);
26        },
27    };
28
29    // Array of method names that modify the array. These will be disabled.
30    const modifyingMethods = ['pop', 'push', 'shift', 'unshift', 'splice', 'sort', 'reverse'];
31
32    // Recursive function to convert all nested objects and arrays into immutable versions.
33    const deepFreeze = (currentObj: ImmutableObject): ImmutableObject => {
34        for (const key in currentObj) {
35            if (typeof currentObj[key] === 'object' && currentObj[key] !== null) {
36                currentObj[key] = deepFreeze(currentObj[key]);
37            }
38        }
39
40        // Proxy arrays with a handler to block modifications.
41        if (Array.isArray(currentObj)) {
42            modifyingMethods.forEach(method => {
43                currentObj[method] = new Proxy(currentObj[method], functionHandler);
44            });
45            return new Proxy(currentObj, arrayHandler);
46        }
47
48        // Proxy objects with a handler to block modifications.
49        return new Proxy(currentObj, objectHandler);
50    };
51
52    // Start the deep freeze process from the root object.
53    return deepFreeze(obj);
54}
55
56// Usage example:
57// const myImmutableObj = makeImmutable({ x: 5 });
58// myImmutableObj.x = 6; // Throws "Error Modifying Property: x"
59

Time and Space Complexity

The time complexity of the makeImmutable function is O(n), where n is the total number of properties (including nested properties) in the obj. This is because the function uses depth-first search (DFS) to traverse all properties of the object (and any nested objects or arrays), applying a Proxy to each property. Each property is visited exactly once.

The space complexity of the makeImmutable function is also O(n), due to the creation of a new Proxy object for each property in the original object. Additionally, if an array contains mutating methods like 'pop', 'push', etc., it wraps those in Proxies as well, although it doesn't create more than one proxy per method. The space is used for storing the Proxies and the call stack during the recursive DFS traversal.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

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

LeetCode 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 we

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 algomonster s3 us east 2 amazonaws com recursion jpg You first

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