We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Differences Between Two Objects

Number: 2774

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given two deeply nested JSON objects or arrays, return a new object that represents only the differences between them. For each key that exists in both objects, if their associated values differ, the output should contain that key with a value formatted as an array: [value from obj1, value from obj2]. If the differing values are themselves objects or arrays, the comparison should be performed recursively. Note that keys that have been added to or removed from one object (i.e. keys that do not exist in both) are ignored.

Key Insights

  • Use recursion to traverse nested objects and arrays.
  • Compare only keys that exist in both objects.
  • When encountering two values of different types or unequal primitives, record the difference as [value from obj1, value from obj2].
  • When both values are objects or arrays, recursively compute their differences and include them only if the resulting nested diff is non-empty.
  • Arrays are treated like objects with indices as keys.
  • The solution requires careful type checking and handling of recursive structures.

Space and Time Complexity

Time Complexity: O(n) in average, where n is the number of keys/elements in the common parts of the structures. Space Complexity: O(n) due to recursion and storage needed for the output differences.

Solution

We solve the problem using a recursive function that compares keys present in both input objects. For each common key:

  1. If both values are objects (or both are arrays), recursively compute their differences.
  2. If the recursive call returns a non-empty object, include that key in the result.
  3. If the two values are of different types or are primitives that differ, add the key with a difference array [value from obj1, value from obj2].
  4. Ignore keys that exist only in one object. This recursive approach naturally handles the deeply nested structure while ensuring only common keys with different values are captured.

Code Solutions

def diff_objects(obj1, obj2):
    # If both values are dictionaries
    if isinstance(obj1, dict) and isinstance(obj2, dict):
        diff = {}
        # Only iterate on the keys present in both dictionaries
        for key in obj1.keys() & obj2.keys():
            sub_diff = diff_objects(obj1[key], obj2[key])
            # Only add if there is an actual difference
            if sub_diff is not None:
                diff[key] = sub_diff
        return diff if diff else None
    # If both values are lists, treat indices as keys
    elif isinstance(obj1, list) and isinstance(obj2, list):
        diff = {}
        # iterate over common indices only
        for i in range(min(len(obj1), len(obj2))):
            sub_diff = diff_objects(obj1[i], obj2[i])
            if sub_diff is not None:
                # Use string keys for consistency with object keys
                diff[str(i)] = sub_diff
        return diff if diff else None
    else:
        # If the two values are equal, there's no difference
        if obj1 == obj2:
            return None
        else:
            # If types differ or values are different, return the difference array.
            return [obj1, obj2]

# A wrapper function to ensure we always return an object (or empty dict)
def differences_between_two_objects(obj1, obj2):
    result = diff_objects(obj1, obj2)
    return result if result is not None else {}

# Example usage:
if __name__ == "__main__":
    obj1 = {"a": 5, "v": 6, "z": [1, 2, 4, [2, 5, 7]]}
    obj2 = {"a": 5, "v": 7, "z": [1, 2, 3, [1]]}
    print(differences_between_two_objects(obj1, obj2))
← Back to All Questions