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.

function objDiff(obj1: any, obj2: any): any {
    if (type(obj1) !== type(obj2)) return [obj1, obj2]; // Direct type difference
    if (!isObject(obj1)) return obj1 === obj2 ? {} : [obj1, obj2]; // Direct value difference
    const diff: Record<string, unknown> = {};
    const sameKeys = Object.keys(obj1).filter(key => key in obj2); // Shared keys
    sameKeys.forEach(key => {
        const subDiff = objDiff(obj1[key], obj2[key]); // Recursive comparison
        if (Object.keys(subDiff).length) diff[key] = subDiff; // Accumulate differences
    });
    return diff;
}

function type(obj: unknown): string {
    return Object.prototype.toString.call(obj).slice(8, -1); // Precise type
}

function isObject(obj: unknown): obj is Record<string, unknown> {
    return typeof obj === 'object' && obj !== null; // Object check excluding null
}

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.

Example Walkthrough

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

let obj1 = {
    name: "Alice",
    age: 25,
    contact: {
        email: "[email protected]",
        phone: "1234567890"
    },
    hobbies: ["reading", "traveling", "sports"]
};

let obj2 = {
    name: "Alice",
    age: 27,
    contact: {
        email: "[email protected]",
        phone: "1234567890"
    },
    hobbies: ["reading", "sports"],
    languages: ["English", "Spanish"]
};

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:

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

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

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.