Problem Description

This problem asks you to implement a deep merge function that combines two values obj1 and obj2 according to specific rules.

The deep merge operation works as follows:

For Objects: When both values are objects (non-array), create a result that contains all keys from both objects. If a key exists in both objects, recursively deep merge the values associated with that key. If a key exists in only one object, include it directly in the result.

For Arrays: When both values are arrays, create a result array with length equal to the longer of the two arrays. Treat array indices like object keys - if an index exists in both arrays, deep merge the values at that index. If an index exists in only one array, use that value.

For Mismatched Types: If the values are not both objects, or if one is an array and the other is a plain object, simply return obj2.

For Primitives: When either value is a primitive (not an object), return obj2.

Example:

• Merging {"a": 1, "c": 3} with {"a": 2, "b": 2} produces {"a": 2, "c": 3, "b": 2}
• The key "a" exists in both, so its value becomes 2 (from obj2)
• The key "c" only exists in obj1, so it remains 3
• The key "b" only exists in obj2, so it's added with value 2

The function should handle nested structures recursively, applying the same rules at each level of nesting.

Intuition

The key insight for solving this problem is recognizing that deep merge is inherently a recursive operation. When we encounter nested structures, we need to apply the same merging logic at each level of depth.

We start by identifying what type of values we're dealing with. The fundamental question at each step is: "Are both values objects that we can merge, or should we just return obj2?"

First, we need helper functions to distinguish between different types:

• isObj() checks if a value is an object (including arrays)
• isArr() specifically checks if a value is an array

The core logic follows this pattern:

1. Base Case: If either value isn't an object, we can't merge them, so we return obj2. This handles primitives like numbers, strings, null, etc.

2. Type Mismatch: If one value is an array and the other is a plain object, they're incompatible for merging, so we return obj2.

3. Recursive Case: When both values are compatible (both arrays or both objects), we iterate through all keys/indices in obj2 and recursively merge each property. The beauty of this approach is that JavaScript treats array indices the same as object keys when using for...in loop.

The solution modifies obj1 in place by iterating through obj2's properties and either:

• Directly assigning the value if the key doesn't exist in obj1
• Recursively merging if the key exists in both

This approach naturally handles the array length requirement - when iterating through a longer array's indices, we automatically extend the shorter array by setting values at higher indices.

The recursion naturally terminates when we reach primitive values or incompatible types, at which point we simply use the value from obj2.

Solution Approach

The implementation uses a recursive approach with type checking to handle different data structures appropriately.

Helper Functions:

const isObj = (obj: any) => obj && typeof obj === 'object';
const isArr = (obj: any) => Array.isArray(obj);

• isObj() returns true for any object (including arrays), but false for null and primitives
• isArr() specifically identifies arrays

Main Algorithm Flow:

1. Type Validation:

   if (!isObj(obj1) || !isObj(obj2)) {
       return obj2;
   }

   If either value is not an object (primitive, null, or undefined), return obj2 directly.

2. Type Compatibility Check:

   if (isArr(obj1) !== isArr(obj2)) {
       return obj2;
   }

   If one is an array and the other is a plain object, they can't be merged, so return obj2.

3. Recursive Merging:

   for (const key in obj2) {
       obj1[key] = deepMerge(obj1[key], obj2[key]);
   }
   return obj1;

   • Iterate through all properties/indices in obj2
   • For each key, recursively call deepMerge with the corresponding values from both objects
   • The result is assigned back to obj1[key], modifying obj1 in place
   • Return the modified obj1

Key Implementation Details:

• The for...in loop works seamlessly for both objects and arrays since array indices are treated as string keys
• When obj2 has a key that doesn't exist in obj1, obj1[key] is undefined, causing the recursive call to return obj2[key] directly
• For arrays with different lengths, the loop automatically handles extending the shorter array by setting values at higher indices
• The in-place modification of obj1 is efficient as it avoids creating unnecessary intermediate objects

Time Complexity: O(n) where n is the total number of properties across all nested levels in both objects.

Space Complexity: O(d) where d is the maximum depth of nesting, due to the recursive call stack.

Example Walkthrough

Let's walk through merging two simple nested objects to see how the recursive solution works:

Input:

• obj1 = {a: 1, b: {x: 10}}
• obj2 = {a: 2, b: {y: 20}, c: 3}

Step-by-step execution:

1. Initial call: deepMerge(obj1, obj2)

   • Both are objects (not arrays) ✓
   • Both have same type (object) ✓
   • Start iterating through obj2's keys: "a", "b", "c"

2. Processing key "a":

   • Call deepMerge(obj1["a"], obj2["a"]) → deepMerge(1, 2)
   • 1 is not an object, so return 2
   • Set obj1["a"] = 2
   • Current obj1: {a: 2, b: {x: 10}}

3. Processing key "b":

   • Call deepMerge(obj1["b"], obj2["b"]) → deepMerge({x: 10}, {y: 20})
   • Both are objects (not arrays) ✓
   • Start iterating through {y: 20}'s keys: "y"

   3.1. Processing nested key "y":

   • Call deepMerge(obj1["b"]["y"], obj2["b"]["y"]) → deepMerge(undefined, 20)

   • undefined is not an object, so return 20

   • Set obj1["b"]["y"] = 20

   • obj1["b"] becomes {x: 10, y: 20}

   • Return {x: 10, y: 20} from nested call

   • Set obj1["b"] = {x: 10, y: 20}

   • Current obj1: {a: 2, b: {x: 10, y: 20}}

4. Processing key "c":

   • Call deepMerge(obj1["c"], obj2["c"]) → deepMerge(undefined, 3)
   • undefined is not an object, so return 3
   • Set obj1["c"] = 3
   • Current obj1: {a: 2, b: {x: 10, y: 20}, c: 3}

5. Final result: Return modified obj1 = {a: 2, b: {x: 10, y: 20}, c: 3}

Notice how:

• Existing primitive values get replaced (a: 1 → a: 2)
• Nested objects get merged recursively (b: {x: 10} merges with b: {y: 20})
• New keys get added (c: 3 added from obj2)
• The original nested value x: 10 is preserved in the merged object

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the total number of properties across all nested levels in both objects.

The algorithm performs a depth-first traversal through all properties in obj2. For each property in obj2, it either:

• Returns immediately if one or both values are non-objects (constant time)
• Returns immediately if there's a type mismatch between array and object (constant time)
• Recursively processes nested objects/arrays

Each property is visited exactly once, and the operations performed at each property (type checking, assignment) are O(1). Therefore, the overall time complexity is linear with respect to the total number of properties.

Space Complexity: O(d) where d is the maximum depth of nesting in the objects.

The space complexity comes from two sources:

1. Recursion Call Stack: The recursive calls create a call stack with maximum depth equal to the deepest nesting level in the objects. Each recursive call adds a frame to the stack, resulting in O(d) space for the call stack.

2. In-place Modification: The algorithm modifies obj1 in place rather than creating a new object, so no additional space is needed for storing the merged result beyond what already exists in obj1.

The dominant factor is the recursion depth, making the overall space complexity O(d).

Common Pitfalls

1. Mutating the Original Object

The Problem: The current implementation modifies obj1 in place, which can lead to unexpected side effects when the original object is used elsewhere in the code.

original = {"a": 1, "b": {"c": 2}}
source = {"b": {"d": 3}}
result = deepMerge(original, source)
# original is now modified: {"a": 1, "b": {"c": 2, "d": 3}}
# This might break other code that expects original to remain unchanged

Solution: Create a deep copy of obj1 before merging to preserve the original:

import copy

def deepMerge(obj1, obj2):
    def is_object(value):
        return value is not None and isinstance(value, (dict, list))
  
    def is_array(value):
        return isinstance(value, list)
  
    if not is_object(obj1) or not is_object(obj2):
        return obj2
  
    if is_array(obj1) != is_array(obj2):
        return obj2
  
    # Create a deep copy to avoid mutating the original
    result = copy.deepcopy(obj1)
  
    if is_array(result) and is_array(obj2):
        for i in range(len(obj2)):
            if i < len(result):
                result[i] = deepMerge(result[i], obj2[i])
            else:
                result.append(obj2[i])
    else:
        for key in obj2:
            result[key] = deepMerge(result.get(key), obj2[key])
  
    return result

2. Circular References Causing Stack Overflow

The Problem: If either object contains circular references, the recursive function will enter an infinite loop and cause a stack overflow:

obj1 = {"a": 1}
obj1["self"] = obj1  # Circular reference
obj2 = {"b": 2}
# deepMerge(obj1, obj2) would cause RecursionError

Solution: Track visited objects to detect and handle circular references:

def deepMerge(obj1, obj2, visited=None):
    if visited is None:
        visited = set()
  
    def is_object(value):
        return value is not None and isinstance(value, (dict, list))
  
    def is_array(value):
        return isinstance(value, list)
  
    if not is_object(obj1) or not is_object(obj2):
        return obj2
  
    if is_array(obj1) != is_array(obj2):
        return obj2
  
    # Check for circular references
    obj1_id = id(obj1)
    obj2_id = id(obj2)
  
    if obj1_id in visited or obj2_id in visited:
        return obj2  # Or handle as needed
  
    visited.add(obj1_id)
    visited.add(obj2_id)
  
    result = copy.deepcopy(obj1)
  
    if is_array(result) and is_array(obj2):
        for i in range(len(obj2)):
            if i < len(result):
                result[i] = deepMerge(result[i], obj2[i], visited.copy())
            else:
                result.append(obj2[i])
    else:
        for key in obj2:
            result[key] = deepMerge(result.get(key), obj2[key], visited.copy())
  
    return result

3. Incorrect Handling of Special Object Types

The Problem: The current is_object check treats all non-primitive types as mergeable objects, including dates, sets, or custom classes, which may not behave correctly:

from datetime import datetime
obj1 = {"date": datetime.now()}
obj2 = {"date": {"year": 2024}}
# This would attempt to merge a datetime with a dict, causing errors

Solution: Be more specific about what types should be merged:

def is_mergeable_object(value):
    """Check if value is a plain dict or list that should be merged"""
    return isinstance(value, (dict, list)) and \
           not isinstance(value, (datetime, set, frozenset, bytes, bytearray))

def deepMerge(obj1, obj2):
    if not is_mergeable_object(obj1) or not is_mergeable_object(obj2):
        return obj2
    # ... rest of the implementation