Problem Description

This problem asks you to compare two deeply nested objects or arrays and return a new object that represents only the differences between them.

The key requirements are:

1. Compare corresponding properties: For each key that exists in both objects, compare their values
2. Return differences as arrays: When values differ, represent the change as [obj1_value, obj2_value]
3. Ignore added/removed keys: Keys that exist in only one object should not be included in the result
4. Handle nested structures: The comparison should work recursively for nested objects and arrays
5. Treat arrays like objects: Array indices are considered as keys (e.g., index 0 becomes key "0")

The function should handle several cases:

• Primitive values: If two primitive values at the same key are different, return them as [old_value, new_value]
• Identical values: If values are the same, don't include them in the result
• Type differences: If the same key has different types (e.g., object vs array), return both as [obj1_value, obj2_value]
• Nested differences: For nested objects/arrays, recursively find differences and only include keys with changes

For example:

• If obj1.a = 1 and obj2.a = 2, the result includes "a": [1, 2]
• If obj1.x = [] and obj2.x = [], nothing is included (empty arrays are equal)
• If obj1.z.a = null and obj2.z.a = 2, the result includes "z": {"a": [null, 2]}
• For arrays, if arr1[2] = 4 and arr2[2] = 3, the result includes "2": [4, 3]

The output should be a nested object where each leaf value is either a difference array [old, new] or another object containing differences. Empty objects indicate no differences were found.

Intuition

The core insight is that we need to perform a recursive comparison that handles different data types appropriately. Let's think through how to approach this step by step.

First, we need to recognize that when comparing two values, there are fundamentally three scenarios:

1. The values have different types (one is an object, the other is a primitive, or one is an array and the other is an object)
2. Both values are primitives (numbers, strings, booleans, null)
3. Both values are objects/arrays that need deeper comparison

For different types, the comparison is straightforward - they're definitely different, so we return [obj1, obj2] immediately.

For primitive values, we simply check if they're equal. If they are, we return an empty object {} (no difference), otherwise we return [obj1, obj2].

The interesting case is when both values are objects or arrays. Here, we need to:

• Find the keys that exist in both objects (intersection of keys)
• For each common key, recursively compare the values
• Only include a key in our result if its recursive comparison found differences

The key insight for handling the "ignore added/removed keys" requirement is to only iterate through keys that exist in both objects. We use Object.keys(obj1).filter(key => key in obj2) to find this intersection.

For the recursive step, we call objDiff on each pair of values for common keys. If the recursive call returns an empty object (no differences found), we don't include that key in our result. If it returns something (either a difference array or an object with differences), we include it.

The beauty of this approach is that arrays naturally work with the same logic since in JavaScript, arrays are objects where indices are keys. So [1, 2, 3] is treated like {"0": 1, "1": 2, "2": 3}.

The helper functions type() and isObject() help us cleanly determine whether we're dealing with objects/arrays that need recursive processing or primitives that can be compared directly. Using Object.prototype.toString.call() gives us a reliable way to distinguish between different types, even handling edge cases like null (which has typeof null === 'object' but isn't actually an object we can recurse into).

Solution Approach

The solution implements a recursive comparison algorithm with three helper functions working together to handle different data types and edge cases.

Main Function Structure:

The objDiff function follows this logic flow:

1. First, check if the two inputs have different types using type(obj1) !== type(obj2). If they do, immediately return [obj1, obj2] since different types are always considered a difference.

2. Next, check if we're dealing with non-objects (primitives) using !isObject(obj1). For primitives:

   • If they're equal (obj1 === obj2), return {} (no difference)
   • If they're different, return [obj1, obj2]

3. For objects/arrays, create an empty diff object to collect differences, then:

   • Find common keys: Object.keys(obj1).filter(key => key in obj2)
   • For each common key, recursively call objDiff(obj1[key], obj2[key])
   • Only add to diff if the recursive call found differences (non-empty result)

Helper Functions:

1. type(obj): Uses Object.prototype.toString.call(obj).slice(8, -1) to get the exact type. This method returns strings like "[object Array]" or "[object Object]", and we slice to extract just the type name ("Array", "Object", etc.). This is more reliable than typeof for distinguishing arrays from objects.

2. isObject(obj): Checks if something is an object or array that we can recurse into. Returns true for objects and arrays, but false for null (which technically has typeof null === 'object' but can't be traversed).

Key Algorithm Details:

The recursive traversal pattern ensures we:

• Only process keys present in both objects (intersection)
• Build the result object incrementally, adding only changed properties
• Handle nested structures by recursively applying the same logic

For arrays, since JavaScript treats array indices as object keys, the same logic applies. An array [1, 2, 3] is processed like {"0": 1, "1": 2, "2": 3}.

Example Walkthrough:

For obj1 = {"a": 1, "b": {"c": 2}} and obj2 = {"a": 1, "b": {"c": 3}}:

1. Compare types - both are objects, continue
2. Find common keys: ["a", "b"]
3. Process "a": objDiff(1, 1) returns {} (no difference)
4. Process "b": objDiff({"c": 2}, {"c": 3}) recursively:
   • Both are objects, find common keys: ["c"]
   • Process "c": objDiff(2, 3) returns [2, 3]
   • Return {"c": [2, 3]}
5. Final result: {"b": {"c": [2, 3]}}

The Object.keys(subDiff).length check ensures we only include keys where actual differences were found, filtering out unchanged properties automatically.

Example Walkthrough

Let's walk through a concrete example to see how the algorithm works:

Given:

obj1 = {
  "x": 5,
  "y": {
    "a": 1,
    "b": 2
  },
  "z": [1, 2, 3]
}

obj2 = {
  "x": 5,
  "y": {
    "a": 1,
    "b": 3
  },
  "z": [1, 2, 4]
}

Step-by-step execution:

1. Initial call: objDiff(obj1, obj2)

   • Both are objects (same type) → continue to recursive comparison
   • Common keys: ["x", "y", "z"]

2. Process key "x": objDiff(5, 5)

   • Both are primitives and equal
   • Return {} (no difference)
   • Don't add to result

3. Process key "y": objDiff({a: 1, b: 2}, {a: 1, b: 3})

   • Both are objects → recurse deeper
   • Common keys: ["a", "b"]

   a. Process "a": objDiff(1, 1)

   • Primitives and equal → return {}

   b. Process "b": objDiff(2, 3)

   • Primitives but different → return [2, 3]

   • Build result for "y": {b: [2, 3]}

   • Add to main result

4. Process key "z": objDiff([1, 2, 3], [1, 2, 4])

   • Both are arrays (treated as objects with indices as keys)
   • Common keys: ["0", "1", "2"]

   a. Process "0": objDiff(1, 1) → {}

   b. Process "1": objDiff(2, 2) → {}

   c. Process "2": objDiff(3, 4) → [3, 4]

   • Build result for "z": {"2": [3, 4]}
   • Add to main result

Final Output:

{
  "y": {
    "b": [2, 3]
  },
  "z": {
    "2": [3, 4]
  }
}

Notice how:

• Equal values (like x: 5) don't appear in the output
• Nested differences are preserved in the structure
• Array differences show the index as a string key
• Only the actual changed values appear as [old, new] pairs

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the total number of nodes (keys and values) in both objects combined.

The algorithm performs a depth-first traversal through the object structure:

• For each key that exists in both objects, we make a recursive call to compare the values
• The filter operation to find common keys takes O(k) where k is the number of keys in obj1
• The forEach loop iterates through all common keys
• Each node (primitive value or object) is visited exactly once during the traversal
• The type() function and equality checks are O(1) operations

Therefore, the overall time complexity is linear with respect to the total number of nodes in the input objects.

Space Complexity: O(d + m) where d is the maximum depth of the object tree and m is the size of the output difference object.

The space complexity consists of two components:

• Call stack space: O(d) - The recursive calls can go as deep as the maximum nesting level of the objects
• Output space: O(m) - The space needed to store the difference object, which in the worst case (when all values differ) could be O(n)

In the best case where objects are identical, the output space would be O(1) (empty object), and in the worst case where all values differ, it would approach O(n). The auxiliary space used for the sameKeys array is O(k) where k is the number of keys, which is bounded by O(n).

Common Pitfalls

1. Incorrect Handling of Arrays as Objects

The Python implementation has a critical flaw: it doesn't handle arrays (lists) properly. The problem states that arrays should be treated like objects with indices as keys, but the current is_object() function only checks for dictionaries, causing arrays to be compared as primitives.

Problem Example:

arr1 = [1, 2, 3]
arr2 = [1, 2, 4]
# Current code returns [arr1, arr2] instead of {"2": [3, 4]}

Solution:

def is_object(obj):
    """Check if a value is a dict or list (container types)"""
    return isinstance(obj, (dict, list))

def objDiff(obj1, obj2):
    # ... existing type check code ...
  
    if not is_object(obj1):
        return {} if obj1 == obj2 else [obj1, obj2]
  
    diff = {}
  
    # Handle both dicts and lists
    if isinstance(obj1, dict):
        same_keys = [key for key in obj1.keys() if key in obj2]
    else:  # Both are lists
        # Find common indices
        min_len = min(len(obj1), len(obj2))
        same_keys = list(range(min_len))
  
    for key in same_keys:
        sub_diff = objDiff(obj1[key], obj2[key])
        if (isinstance(sub_diff, dict) and len(sub_diff) > 0) or isinstance(sub_diff, list):
            diff[str(key) if isinstance(obj1, list) else key] = sub_diff
  
    return diff

2. Type Comparison Issues with None/null Values

The get_type() function might not handle None correctly when comparing with other falsy values, leading to unexpected behavior.

Problem Example:

obj1 = {"a": None}
obj2 = {"a": 0}
# Both might be treated similarly in some comparisons

Solution:

def get_type(obj):
    """Gets the precise type of an object, handling None specially"""
    if obj is None:
        return 'NoneType'
    return type(obj).__name__

3. Deep Equality Check for Complex Objects

Using == for equality checking can fail for complex nested structures or objects with circular references.

Problem Example:

import numpy as np
arr1 = np.array([1, 2, 3])
arr2 = np.array([1, 2, 3])
# arr1 == arr2 returns an array, not a boolean

Solution:

def safe_equals(obj1, obj2):
    """Safely compare two objects for equality"""
    try:
        # For numpy arrays or similar
        if hasattr(obj1, '__array__'):
            return np.array_equal(obj1, obj2)
        return obj1 == obj2
    except (ValueError, TypeError):
        # Fallback for objects that can't be compared directly
        return False

# Then in objDiff:
if not is_object(obj1):
    return {} if safe_equals(obj1, obj2) else [obj1, obj2]

4. Mixed Type Keys in Result

When handling arrays, the code should ensure that array indices are converted to strings in the result to maintain consistency with JavaScript behavior.

Problem Example:

# Current code might mix integer and string keys
result = {0: [1, 2], "a": [3, 4]}  # Inconsistent key types

Solution: Always convert array indices to strings when adding to the diff object (as shown in the first solution above with str(key)).