LeetCode Solutions Blog

Deep Merge of Two Objects

Number: 2795

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given two JSON-parsed values, obj1 and obj2, perform a deep merge. When both values are objects, merge their keys recursively. For arrays, treat indices as keys and merge up to the length of the longer array. For all other types or mismatches, take the value from obj2.

Key Insights

Use recursion to handle nested structures.
Determine the type of the current values:
- If both are plain objects, merge each key recursively.
- If both are arrays, iterate over indices up to the longer array and merge corresponding elements.
- In all other cases (or type mismatches), return the value from obj2.
Remember to include keys or indices that exist in only one of the inputs.

Space and Time Complexity

Time Complexity: O(n) where n is the total number of keys/elements (deep traversal of both structures). Space Complexity: O(d) where d is the depth of the recursion (stack space for recursive calls).

Solution

The solution uses a recursive approach:

If both input values are objects, create a new object and iterate through the union of keys from both objects. For each key, apply the deep merge recursively.
If both values are arrays, find the length of the longer array and iterate by index. For each index, if both arrays have a value, merge them recursively; else, choose the value that exists.
For any other type or when types mismatch, simply return obj2. This ensures that nested arrays and objects are merged according to the problem rules, with obj2 taking precedence for non-composite values or mismatches.

Code Solutions

def deep_merge(obj1, obj2):
    # If both are dictionaries, merge keys recursively.
    if isinstance(obj1, dict) and isinstance(obj2, dict):
        merged = {}
        # Collect all keys from both dictionaries
        keys = set(obj1.keys()).union(obj2.keys())
        for key in keys:
            # If key exists in both, merge recursively; otherwise, take the one that exists.
            if key in obj1 and key in obj2:
                merged[key] = deep_merge(obj1[key], obj2[key])
            elif key in obj1:
                merged[key] = obj1[key]
            else:
                merged[key] = obj2[key]
        return merged
    # If both are lists, treat indices as keys and merge accordingly.
    elif isinstance(obj1, list) and isinstance(obj2, list):
        max_len = max(len(obj1), len(obj2))
        merged = []
        for i in range(max_len):
            # Get values if available; otherwise, treat missing index as undefined.
            val1 = obj1[i] if i < len(obj1) else None
            val2 = obj2[i] if i < len(obj2) else None
            # If both indices exist, merge recursively.
            if i < len(obj1) and i < len(obj2):
                merged.append(deep_merge(val1, val2))
            elif i < len(obj1):
                merged.append(val1)
            else:
                merged.append(val2)
        return merged
    # For all other cases, return obj2.
    else:
        return obj2

# Example usage:
obj1 = {"a": 1, "b": {"c": [1, [2, 7], 5], "d": 2}}
obj2 = {"a": 1, "b": {"c": [6, [6], [9]], "e": 3}}
print(deep_merge(obj1, obj2))