2700. Differences Between Two Objects


Problem Description

Write a function that compares two deeply nested objects or arrays and identifies the differences. If a key exists in both objects with different values, these values should be represented as an array [value from obj1, value from obj2]. The results should be a deeply nested object mirroring the structure of the inputs, where each leaf node is an array expressing the difference between the two inputs. New keys or removed keys should not be included in the result; only keys with modified values are part of the comparison.

The assumption is that the objects or arrays are the result of JSON.parse, meaning they are valid JSON objects or arrays. For arrays, use the indices as keys when comparing their elements. If an object's properties or an array's elements haven't changed, don't include them in the output difference object.

Here's the function's essence:

  • If keys exist in one object but not the other, ignore them.
  • If a key exists in both with different values, add this to the resulting object with the values as an array.
  • If the values are objects or arrays, compare their keys or indices recursively.
  • If a value changed type between the two objects (e.g., from an array to an object), include this in the differences as an array with both values.
  • Ignore any unchanged properties or elements.

This function can be useful for understanding how objects change over time or across different states, such as in state management in programming applications.

Intuition

To solve this problem, we take a recursive approach. We start by comparing the types of the two items. If they are different, that's an immediate difference, and we return them as a pair. If they are both objects (or arrays, since in JavaScript arrays are a type of object), we need to compare each key-value pair (or index-value pair for arrays).

Here's the step-by-step intuition behind recursively determining object differences:

  • Define a helper function objDiff(obj1, obj2) to handle the recursive comparison.
  • Prevent comparing a property that changed types by immediately returning them as a difference.
  • If they're not both objects (or arrays), compare them directly and return the difference if any.
  • If they are objects, recursively compare each same key in both objects. If a difference is found, add it to the diff object.
  • Avoid including any keys that didn't change in the result.
  • Use the isObject utility function to determine if the value is an object (taking into consideration that null is technically an object in JavaScript).
  • Use the type utility function to get a reliable string representation of the object's type, which avoids issues with values like null or arrays, which are typeof 'object' in JavaScript.

When invoking the objDiff function, you can expect an object that mirrors the input structure, where each leaf value represents a changed property and consists of an array with the format [value from obj1, value from obj2]. By doing so, the solution characterizes the evolution or modifications between obj1 and obj2.

Solution Approach

The solution implements a recursive function objDiff that takes two parameters, obj1 and obj2, which represent the objects or arrays to be compared. This function follows the steps outlined in the intuition section to identify differences between deeply nested objects or arrays. Here's how it works:

  • First, the function checks whether the items have the same type using the type function. If the types are different, the function returns a pair immediately since this is considered a difference. The type function uses Object.prototype.toString.call(obj) to get a precise string representation of the object's type.

  • If the items are of the same type but are not objects (i.e., they're primitives like numbers, strings, or booleans), the function compares them directly. If they are equal, it returns an empty object indicating no difference; otherwise, it returns an array with the two different values.

  • If the items are of the same type and are objects (including arrays), the function proceeds to compare their properties or elements. It initializes an empty object diff to accumulate differences found in key-value pairs.

  • The function then filters the keys of obj1 to find those that also exist in obj2, ensuring only shared keys are compared.

  • For each shared key, the objDiff function is called recursively to compare the key's associated values from both obj1 and obj2. The result of this recursive call represents the nested differences.

  • If the recursive call returns an object with keys, meaning a difference has been found, this difference is stored in the diff object under the current key.

  • Once all shared keys are processed, the diff object is returned. If there were no differences, this object will be empty; otherwise, it will have a structure matching that of the input objects, but only including keys with differences.

  • The solution also includes two utility functions: isObject, which determines whether a value is an object (and not null), and type, which accurately determines the type of the value.

  • No additional data structures or patterns are needed beyond the basic use of recursion and objects for mapping the differences.

The algorithm complexity is largely determined by the number and depth of the nested structures since the function must traverse both obj1 and obj2 completely.

1function objDiff(obj1: any, obj2: any): any {
2    if (type(obj1) !== type(obj2)) return [obj1, obj2]; // Direct type difference
3    if (!isObject(obj1)) return obj1 === obj2 ? {} : [obj1, obj2]; // Direct value difference
4    const diff: Record<string, unknown> = {};
5    const sameKeys = Object.keys(obj1).filter(key => key in obj2); // Shared keys
6    sameKeys.forEach(key => {
7        const subDiff = objDiff(obj1[key], obj2[key]); // Recursive comparison
8        if (Object.keys(subDiff).length) diff[key] = subDiff; // Accumulate differences
9    });
10    return diff;
11}
12
13function type(obj: unknown): string {
14    return Object.prototype.toString.call(obj).slice(8, -1); // Precise type
15}
16
17function isObject(obj: unknown): obj is Record<string, unknown> {
18    return typeof obj === 'object' && obj !== null; // Object check excluding null
19}

This approach ensures that the structure of the original objects is preserved in the output, and only genuine value changes are recorded, making it a robust solution for detecting changes in structured data.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Example Walkthrough

Let's consider two objects, obj1 and obj2, to illustrate the solution approach.

1let obj1 = {
2    name: "Alice",
3    age: 25,
4    contact: {
5        email: "[email protected]",
6        phone: "1234567890"
7    },
8    hobbies: ["reading", "traveling", "sports"]
9};
10
11let obj2 = {
12    name: "Alice",
13    age: 27,
14    contact: {
15        email: "[email protected]",
16        phone: "1234567890"
17    },
18    hobbies: ["reading", "sports"],
19    languages: ["English", "Spanish"]
20};

In this example, we have two objects representing a person's information. We will use the objDiff function to identify the differences between obj1 and obj2.

Here's how objDiff will work on this example:

  1. It starts by comparing the types of obj1 and obj2 using the type function, which will return 'Object' for both, meaning the types are the same.

  2. Since obj1 and obj2 are both objects, it initializes an empty diff object.

  3. It examines the keys of obj1: ['name', 'age', 'contact', 'hobbies'] and then filters these keys by those keys that also exist in obj2.

  4. It determines that both name and phone keys in the contact object are unchanged, so they won't appear in the final difference object.

  5. The function compares the value for the age key in both objects using a direct comparison because it's a primitive (number). They're different, so it adds them to the diff as age: [25, 27].

  6. Next, the contact key is an object with differing values for the email key, so a recursive call to the contact object is made. This will result in adding contact: {email: ["[email protected]", "[email protected]"]} to the diff object, since the phone numbers are the same and are not included.

  7. For the hobbies key, an array comparison is needed because it's a type of object. The comparison will identify differences using their indices as keys. The result will be hobbies: {2: ['sports', undefined]}, meaning in obj2, the index 2 ("sports") stayed the same, but "traveling" was removed, so it's not included.

  8. Finally, since languages does not exist in obj1, it is ignored in the output diff.

Following this process, the objDiff function's output will be:

1{
2    age: [25, 27],
3    contact: { email: ["[email protected]", "[email protected]"]},
4    hobbies: {2: ["traveling", undefined]}
5}

This resulting object indicates that there's been a change in the age, contact.email, and that the hobbies array at index 2 in obj1 compared to obj2 has changed. This approach ensures that only keys that had changes and existed in both objects are included in the output.

Solution Implementation

1def get_type(obj):
2    """
3    Determines the type of the given object in string format. 
4    """
5    return type(obj).__name__
6
7def is_object(obj):
8    """
9    Checks if the given object is an instance of dict (which is the closest 
10    counterpart to objects in JavaScript) and not None.
11    """
12    return isinstance(obj, dict)
13
14def obj_diff(obj1, obj2):
15    """
16    Calculates the difference between two given objects and returns an object representing the difference. 
17    """
18    # If the types of both objects do not match, return a list containing both objects.
19    if get_type(obj1) != get_type(obj2):
20        return [obj1, obj2]
21
22    # If the objects are not of dict type, directly compare their values, returning an empty
23    # dict if they are the same, or a list with both values if they are different.
24    if not is_object(obj1):
25        return {} if obj1 == obj2 else [obj1, obj2]
26
27    # Initialize an empty dict to hold any differences found.
28    diff = {}
29
30    # Retrieve and iterate over the keys present in both objects.
31    same_keys = [key for key in obj1 if key in obj2]
32    for key in same_keys:
33        # Recursively call obj_diff to check for nested differences.
34        sub_diff = obj_diff(obj1[key], obj2[key])
35
36        # If there are any differences found in the nested objects,
37        # add them to the diff dictionary with the corresponding key.
38        if isinstance(sub_diff, dict) and sub_diff:
39            diff[key] = sub_diff
40        elif isinstance(sub_diff, list):
41            diff[key] = sub_diff
42
43    # Check for keys that are only in one object and not the other
44    unique_keys_1 = set(obj1.keys()) - set(obj2.keys())
45    unique_keys_2 = set(obj2.keys()) - set(obj1.keys())
46  
47    for key in unique_keys_1:
48        diff[key] = obj1[key]
49      
50    for key in unique_keys_2:
51        diff[key] = obj2[key]
52  
53    # Return the diff dictionary containing all differences between obj1 and obj2.
54    return diff
55
1import java.util.*;
2
3public class ObjectDiffer {
4
5    // Determines the type of the given object in string format.
6    public static String getType(Object obj) {
7        // Using getClass().getSimpleName() to get the simple name of the class of obj
8        return obj.getClass().getSimpleName();
9    }
10
11    // Checks if the given object is an instance of Map (used for object comparison)
12    public static boolean isObject(Object obj) {
13        // Checks if obj is an instance of Map (which is similar to an object in JavaScript)
14        return obj instanceof Map;
15    }
16
17    // Calculates the difference between two given objects and returns an object representing the difference.
18    public static Object objDiff(Object obj1, Object obj2) {
19        // If the types of both objects do not match, return a List containing both objects.
20        if (!getType(obj1).equals(getType(obj2))) return Arrays.asList(obj1, obj2);
21
22        // If one of the objects is not a Map (i.e., is not 'object' type), compare them directly
23        if (!isObject(obj1)) return Objects.equals(obj1, obj2) ? new HashMap<>() : Arrays.asList(obj1, obj2);
24
25        // Initialize an empty Map to hold any differences found.
26        Map<String, Object> diff = new HashMap<>();
27
28        // Retrieve and iterate over the keys present in both objects, assuming obj1 and obj2 are Maps
29        Map<?, ?> map1 = (Map<?, ?>) obj1;
30        Map<?, ?> map2 = (Map<?, ?>) obj2;
31
32        // Getting keys present in both maps
33        Set<?> commonKeys = new HashSet<>(map1.keySet());
34        commonKeys.retainAll(map2.keySet());
35
36        for (Object key : commonKeys) {
37            Object subDiff = objDiff(map1.get(key), map2.get(key));
38            // If subDiff is a Map and not empty, add to the diff Map
39            if (subDiff instanceof Map && !((Map<?, ?>) subDiff).isEmpty()) {
40                diff.put((String) key, subDiff);
41            // If subDiff is a List indicating the values are different, add to diff
42            } else if (subDiff instanceof List) {
43                diff.put((String) key, subDiff);
44            }
45        }
46
47        // Return the diff Map containing all differences between obj1 and obj2.
48        return diff;
49    }
50
51    // Example usage
52    public static void main(String[] args) {
53        Map<String, Object> obj1 = new HashMap<>();
54        obj1.put("name", "Alice");
55        Map<String, Object> obj2 = new HashMap<>();
56        obj2.put("name", "Alice");
57        obj2.put("age", 30);
58
59        Object differences = objDiff(obj1, obj2);
60        System.out.println(differences);
61    }
62}
63
1#include <iostream>
2#include <map>
3#include <typeinfo>
4#include <string>
5#include <any>
6
7// Function for demangling the type information to human-readable form (platform specific)
8#include <cxxabi.h>
9
10std::string demangle(const char* mangled_name) {
11    int status = -1;
12    char* demangled_name = abi::__cxa_demangle(mangled_name, NULL, NULL, &status);
13    std::string result(demangled_name);
14    std::free(demangled_name);
15    return result;
16}
17
18// Determines the type of the given object in string format.
19template<typename T>
20std::string getType(const T& obj) {
21    // typeid().name() might return mangled name based on the compiler and platform.
22    // Demangling is done to convert it into a readable string.
23    return demangle(typeid(obj).name());
24}
25
26// Checks if the given object is an object (and not null).
27template<typename T>
28bool isObject(const T& obj) {
29    // Here we directly return false, as C++ is strictly typed and there's no equivalent to
30    // JavaScript's 'typeof' operator for runtime type checking for null or object type.
31    return false;
32}
33
34// Specialization for std::map, which is often used as an object in C++
35template<typename Key, typename T>
36bool isObject(const std::map<Key, T>& obj) {
37    return true;
38}
39
40// Calculates the difference between two given objects and returns an object representing the difference.
41template<typename T>
42std::any objDiff(const T& obj1, const T& obj2) {
43    auto& obj1Type = getType(obj1);
44    auto& obj2Type = getType(obj2);
45
46    // If the types of both objects do not match, return a pair containing both objects.
47    if (obj1Type != obj2Type) return std::make_pair(obj1, obj2);
48
49    // For non-map types, directly compare the values.
50    if (!isObject(obj1)) return obj1 == obj2 ? std::make_any<std::map<std::string, std::any>>() : std::make_any<std::pair<T, T>>(obj1, obj2);
51
52    // Initialize an empty map to hold any differences found.
53    std::map<std::string, std::any> diff;
54
55    // Since C++ does not allow generic access to object properties like JavaScript,
56    // we must specialize this function for specific types, such as std::map.
57    // Here we provide an example for std::map type objects.
58
59    return diff; // Return empty diff for now, since specialization is required.
60}
61
62// Specialization of objDiff for std::map types
63template<typename Key, typename T>
64std::any objDiff(const std::map<Key, T>& obj1, const std::map<Key, T>& obj2) {
65    std::map<Key, std::any> diff;
66
67    // Iterate over the keys present in both maps.
68    for (const auto& [key, value] : obj1) {
69        if (obj2.count(key)) {
70            // Recursively call objDiff to check for nested differences.
71            std::any subDiff = objDiff(value, obj2.at(key));
72
73            // Check if there is any difference found in the nested objects.
74            if (subDiff.type() == typeid(std::map<Key, std::any>)) {
75                auto& subMap = std::any_cast<std::map<Key, std::any>&>(subDiff);
76                if (subMap.size() > 0) {
77                    diff[key] = subDiff; // Add differences to the diff map.
78                }
79            } else {
80                diff[key] = subDiff; // Add non-map differences to the diff map.
81            }
82        }
83    }
84
85    return diff; // Return the diff map, containing all differences.
86}
87
88// Note: This code is a basic structure, and in C++, one would need to provide explicit specializations
89// for `isObject` and `objDiff` for each type to be compared. C++ is statically typed and does not provide
90// reflection at runtime in the same way JavaScript does. Thus, a direct translation isn't straightforward.
91
1// Determines the type of the given object in string format.
2function getType(obj: unknown): string {
3    return Object.prototype.toString.call(obj).slice(8, -1);
4}
5
6// Checks if the given object is an object (and not null).
7function isObject(obj: unknown): obj is Record<string, unknown> {
8    return typeof obj === 'object' && obj !== null;
9}
10
11// Calculates the difference between two given objects and returns an object representing the difference.
12function objDiff(obj1: any, obj2: any): any {
13    // If the types of both objects do not match, return an array containing both objects.
14    if (getType(obj1) !== getType(obj2)) return [obj1, obj2];
15
16    // If the objects are not of type 'object', directly compare their values, returning an empty
17    // object if they are the same, or an array with both values if they are different.
18    if (!isObject(obj1)) return obj1 === obj2 ? {} : [obj1, obj2];
19  
20    // Initialize an empty object to hold any differences found.
21    const diff: Record<string, unknown> = {};
22
23    // Retrieve and iterate over the keys present in both objects.
24    const sameKeys = Object.keys(obj1).filter(key => key in obj2);
25    sameKeys.forEach(key => {
26        // Recursively call objDiff to check for nested differences.
27        const subDiff = objDiff(obj1[key], obj2[key]);
28      
29        // If there are any differences found in the nested objects,
30        // add them to the diff object with the corresponding key.
31        if (Object.keys(subDiff).length) diff[key] = subDiff;
32    });
33  
34    // Return the diff object containing all differences between obj1 and obj2.
35    return diff;
36}
37

Time and Space Complexity

Time Complexity

The time complexity of the objDiff function hinges on several operations:

  1. Comparing Types: The type function is called twice which is O(1) since it deals with fixed-size operations regardless of input size.
  2. Equality Check: The direct comparison obj1 === obj2 is O(1).
  3. Object Key Operations: The Object.keys(obj1) operation is O(N) where N is the number of keys in obj1. Filtering (filter) these keys against obj2 is also O(N) assuming both objects have a comparable number of keys on average.
  4. Recursion: The objDiff function is recursively called on each key that exists in both obj1 and obj2. If M is the maximum depth of the objects and K is the average number of keys at each level, the total number of operations can be approximately represented as O(K^M).

Combining these components, assuming maximum recursion depth (which is generally the main driver of complexity here), gives the function an overall time complexity of O(K^M).

Space Complexity

The space complexity is also driven by the recursion and the storage of the diff object:

  1. Recursion Stack: The recursive calls will consume space proportional to the maximum depth of recursion. In worst case, this is O(M) where M is the maximum depth.
  2. Difference Object: The diff object size is at most O(N*M) where N is the number of differing keys and M is the depth of those keys. However, because diff object only grows on differences found, in the best case, it could be O(1) (if objects are identical or if there is only a flat structure with no nested differences).

In the worst case (where all keys at all levels are different), the space complexity would be O(N*M). However, this can vary significantly based on the actual data.


Fast Track Your Learning with Our Quick Skills Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄