LeetCode 2755 - Deep Merge of Two Objects

Difficulty: 🟡 Medium
Topics: —

Solution

Here is the complete technical solution guide for LeetCode 2755 following your requested format.

Problem Understanding

The problem asks us to deep merge two JSON values, obj1 and obj2. The merging rules depend on the type of the values at each position in the objects or arrays. Specifically, if both values are objects, we merge their keys recursively; if both are arrays, we merge each index recursively up to the length of the longer array; if the types differ or are primitive, obj2 overwrites obj1. The result is a new JSON value that respects these rules.

The input represents JSON-parsed data, meaning it could be a primitive (int, float, bool, str, None), a list, or a dict. The output must reflect a deep recursive merge.

Constraints suggest that input sizes can be significant (up to ~500,000 characters in string form). Edge cases include different types at the same position, arrays of unequal length, empty objects or arrays, and primitive value replacements. The input is guaranteed to be valid JSON, so we do not need to handle malformed structures.

Key tricky cases include deeply nested arrays within objects, type mismatches between obj1 and obj2, and empty structures.

Approaches

A brute-force approach would iterate through every key and index at each level recursively without type checking optimization. It would always create copies of subobjects and arrays, potentially doubling memory usage at each recursive step. While correct, it could be inefficient for deeply nested structures and large arrays.

The optimal approach relies on recursively merging only when types match (both are objects or both are arrays) and otherwise directly using obj2. This allows us to avoid unnecessary copies and ensures type consistency without iterating over irrelevant structures. By treating arrays as objects with integer keys during recursion, we can unify the merging logic.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n + m)	O(n + m)	Recursively copy all elements without type checks; may be memory intensive
Optimal	O(n + m)	O(d)	Recursively merge only matching types; `d` is max recursion depth (nesting)

Algorithm Walkthrough

Check type equality: At each recursive step, determine if both obj1 and obj2 are objects (dict) or arrays (list). If types differ, return obj2.
Merge objects: If both are dictionaries, iterate over the union of their keys. For each key:

If the key exists in both, recursively deep merge the values.
If it exists in only one, include that value directly in the result.

Merge arrays: If both are lists, determine the maximum length. For each index:

If both arrays have a value at that index, recursively deep merge them.
If only one array has a value, include it directly.

Primitive or mismatched types: If the values are neither both arrays nor both objects, return obj2 to overwrite obj1.
Return the merged value at each recursion level.

Why it works: The recursive function maintains the invariant that at each position in the structure, either the values are merged if types match, or obj2 replaces obj1. This guarantees that all keys/indices are handled, and that the merge is deep.

Python Solution

from typing import Any

class Solution:
    def deepMerge(self, obj1: Any, obj2: Any) -> Any:
        if isinstance(obj1, dict) and isinstance(obj2, dict):
            merged = {}
            keys = set(obj1.keys()).union(obj2.keys())
            for key in keys:
                if key in obj1 and key in obj2:
                    merged[key] = self.deepMerge(obj1[key], obj2[key])
                elif key in obj1:
                    merged[key] = obj1[key]
                else:
                    merged[key] = obj2[key]
            return merged
        elif isinstance(obj1, list) and isinstance(obj2, list):
            max_len = max(len(obj1), len(obj2))
            merged = []
            for i in range(max_len):
                if i < len(obj1) and i < len(obj2):
                    merged.append(self.deepMerge(obj1[i], obj2[i]))
                elif i < len(obj1):
                    merged.append(obj1[i])
                else:
                    merged.append(obj2[i])
            return merged
        else:
            return obj2

Explanation: The function first checks if both inputs are dictionaries. If so, it computes the union of keys and merges values recursively. For lists, it uses the maximum length and recursively merges each element, or takes the existing element if one array is shorter. For primitives or type mismatches, obj2 replaces obj1.

Go Solution

package main

func deepMerge(obj1 interface{}, obj2 interface{}) interface{} {
    map1, ok1 := obj1.(map[string]interface{})
    map2, ok2 := obj2.(map[string]interface{})
    if ok1 && ok2 {
        merged := make(map[string]interface{})
        for k, v := range map1 {
            merged[k] = v
        }
        for k, v2 := range map2 {
            if v1, exists := merged[k]; exists {
                merged[k] = deepMerge(v1, v2)
            } else {
                merged[k] = v2
            }
        }
        return merged
    }
    
    arr1, ok1 := obj1.([]interface{})
    arr2, ok2 := obj2.([]interface{})
    if ok1 && ok2 {
        maxLen := len(arr1)
        if len(arr2) > maxLen {
            maxLen = len(arr2)
        }
        merged := make([]interface{}, maxLen)
        for i := 0; i < maxLen; i++ {
            var v1, v2 interface{}
            if i < len(arr1) {
                v1 = arr1[i]
            }
            if i < len(arr2) {
                v2 = arr2[i]
            }
            if i < len(arr1) && i < len(arr2) {
                merged[i] = deepMerge(v1, v2)
            } else if i < len(arr1) {
                merged[i] = v1
            } else {
                merged[i] = v2
            }
        }
        return merged
    }
    
    return obj2
}

Go-specific notes: Type assertions are required for interface{} to map[string]interface{} or []interface{}. Nil vs empty handling is implicit since slices can be nil or have length zero.

Worked Examples

Example 1:

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

Key	obj1	obj2	Merge Result
a	1	2	2 (primitive, overwrite)
b	N/A	2	2 (added)
c	3	N/A	3 (retained)

Result: {"a": 2, "b": 2, "c": 3}

Example 2:

obj1 = [{}, 2, 3], obj2 = [[], 5]

Index	obj1	obj2	Merge Result
0	{}	[]	[] (different types, overwrite)
1	2	5	5 (primitive, overwrite)
2	3	N/A	3 (retained)

Result: [[], 5, 3]

Example 3:

obj1 = {"a": 1, "b": {"c": [1 , [2, 7], 5], "d": 2}}

obj2 = {"a": 1, "b": {"c": [6, [6], [9]], "e": 3}}

Merge b.c recursively:

Index	obj1	obj2	Merge
0	1	6	6
1	[2,7]	[6]	[6,7]
2	5	[9]	[9] (overwrite)

Merge keys in b:

d exists only in obj1 → 2
e exists only in obj2 → 3

Result: {"a":1,"b":{"c":[6,[6,7],[9]],"d":2,"e":3}}

Example 4:

obj1 = true, obj2 = null

Different types, return obj2 → null

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each element/key in `obj1` and `obj2` is visited once recursively
Space	O(d)	Recursion stack depth, where `d` is the maximum nesting depth of objects/arrays

Recursive memory usage is proportional to the depth, not the total number of elements. No additional copies are made beyond the merged result.