2755. Deep Merge of Two Objects


Problem Description

This problem involves creating a function that can deeply merge two objects or arrays based on specific rules. A deep merge means that any nested structures within the objects or arrays will also be merged according to certain rules. Here are the rules for deep merging provided in the problem:

  • If both values are objects, the merged result should include all keys from both objects. If a key is present in both, their associated values should be deep merged. If a key is only present in one object, its value should simply be included.
  • If both values are arrays, the merged array should be as long as the longer of the two original arrays. Just like with objects, apply the same deep merge logic to each position in the arrays, treating the indices as if they were keys.
  • In any other case (e.g., values are of different types or not objects/arrays), the result should be the second value obj2.

The problem statement clarifies that the inputs obj1 and obj2 are the results of JSON.parse(), meaning they are valid JavaScript objects or arrays that have been parsed from JSON strings.

Intuition

The solution is based on recursion, a common technique for dealing with nested data structures like objects and arrays.

  • We first check if the inputs are both objects or arrays since the merging logic applies only in those cases. If either obj1 or obj2 is not an object, or they are not the same type (one is an array and the other is not), we immediately return obj2.
  • If both are objects or arrays, we iterate through the keys of obj2 and apply the deepMerge function to each key. This means we attempt to merge obj1[key] and obj2[key], recursively ensuring that any nested objects or arrays are also merged correctly.
  • We then return obj1 as it now contains merged values from obj2.

This recursive strategy neatly handles arbitrarily complex and deep object structures and directly maps onto the merging rules provided in the problem statement. The base case of the recursion is effectively whenever we reach a point where the values to be merged are not both objects or arrays.

Solution Approach

The solution uses a recursive function deepMerge to merge two potentially complex data structures, which could be objects or arrays. Here's how this is carried out:

  • First, we define helper functions isObj and isArr to check if a value is an object or array, respectively. These are used to ensure that we only apply merging logic to appropriate data types.

    1const isObj = (obj: any) => obj && typeof obj === 'object';
    2const isArr = (obj: any) => Array.isArray(obj);
  • We then examine the input values obj1 and obj2. If either is not an object (or if one is an array and the other isn't), we return obj2. This serves as the base case for non-object/array values or mismatched type pairs.

    1if (!isObj(obj1) || !isObj(obj2)) {
    2    return obj2;
    3}
    4
    5if (isArr(obj1) !== isArr(obj2)) {
    6    return obj2;
    7}
  • Next, the function iterates through the keys of obj2 using a for...in loop. For each key, we call deepMerge on the value at that key from both obj1 and obj2, essentially performing a merge operation on any nested structures:

    1for (const key in obj2) {
    2    obj1[key] = deepMerge(obj1[key], obj2[key]);
    3}
  • The operation obj1[key] = deepMerge(obj1[key], obj2[key]) ensures that if the same key is present in both obj1 and obj2, their values will be merged. Otherwise, if the key exists only in obj2, it gets added to obj1.

  • Finally, obj1 is returned, now containing merged data from both obj1 and obj2.

Recursion is the key algorithmic pattern that makes the implementation succinct and able to cope with objects and arrays of any depth. The deepMerge function merges obj2 into obj1 at every level of the data structure, complying with the rules laid out in the problem statement.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

To illustrate the solution approach using a small example, let's consider two objects that we wish to merge using the deepMerge function described in the solution approach:

1let obj1 = {
2  a: 1,
3  b: { c: 3, d: 4 },
4  e: [5, 6],
5};
6
7let obj2 = {
8  b: { c: 8, e: 9 },
9  e: [7],
10  f: 10,
11};

Here, we want to merge obj2 into obj1. Here's a step-by-step walkthrough of how the deep merge would function:

  1. Since both obj1 and obj2 are objects, we proceed with merging. We do not immediately return obj2 because the base case does not apply.

  2. We iterate over the keys in obj2. The keys are b, e, and f.

  3. For key b, obj1[b] and obj2[b] are both objects:

    1obj1[b]: { c: 3, d: 4 }
    2obj2[b]: { c: 8, e: 9 }

    So, we call deepMerge on these two objects:

    • Both have a key c, so we merge the values. The value from obj2 (8) takes precedence.
    • obj1[b] has a key d that is not present in obj2[b]; it remains as is.
    • obj2[b] has a key e that is not present in obj1[b]; it gets added to the result.

    The merged result for key b is: { c: 8, d: 4, e: 9 }.

  4. For key e, obj1[e] is an array and so is obj2[e]:

    1obj1[e]: [5, 6]
    2obj2[e]: [7]

    We extend obj1[e] to match the length of the longer array, but since obj2[e] is the shorter one, no change is made to the length. The deep merge logic doesn't introduce new items from the longer array unless there are corresponding items in obj2. So the merged result for key e is [7, 6].

  5. For key f, which is only present in obj2, we simply add it to obj1:

    1obj1[f]: 10

The final merged object obj1 now looks like this:

1{
2  a: 1,
3  b: { c: 8, d: 4, e: 9 },
4  e: [7, 6],
5  f: 10,
6}

This example makes it clear how each step in the solution approach actively contributes to the desired final result according to the rules of deep merging. Recursion ensures that objects and arrays nested at any level are merged correctly and the rules are followed.

Solution Implementation

1def deep_merge(first_object, second_object):
2    """
3    Function to deeply merge two objects, combining their properties and
4    sub-properties.
5  
6    :param first_object: The first dictionary or object to merge.
7    :param second_object: The second dictionary or object to merge.
8    :return: A dictionary with properties from both first_object and second_object merged.
9    """
10
11    # Helper function to check if a value is a dictionary (object).
12    def is_object(item):
13        return isinstance(item, dict)
14
15    # Helper function to check if a value is a list (array).
16    def is_array(item):
17        return isinstance(item, list)
18
19    # If either argument is not a dictionary (object), return the second_object.
20    if not is_object(first_object) or not is_object(second_object):
21        return second_object
22
23    # If the types of container for both objects differ (one is a list and one is a dictionary), return second_object.
24    if is_array(first_object) != is_array(second_object):
25        return second_object
26
27    # Iterate over each property of the second_object.
28    for key in second_object:
29        # If the property key is in the dictionary's own properties (not inherited).
30        if key in second_object:
31            # Recursively merge properties from both objects.
32            first_object[key] = deep_merge(first_object.get(key), second_object[key])
33
34    # Return the merged first_object, which now contains properties from both objects.
35    return first_object
36
37# Example usage:
38# obj1 = {"a": 1, "c": 3}
39# obj2 = {"a": 2, "b": 2}
40# merged_object = deep_merge(obj1, obj2)
41# Should print: {"a": 2, "c": 3, "b": 2}
42
1import java.util.HashMap;
2import java.util.Map;
3import java.util.Set;
4
5public class DeepMergeExample {
6
7    // Method to check if an object is a Map (used to simulate an 'object' in Java).
8    private static boolean isMap(Object item) {
9        return item instanceof Map;
10    }
11
12    // Deeply merge two Maps and return the result.
13    @SuppressWarnings("unchecked")
14    public static Map<String, Object> deepMerge(Map<String, Object> firstMap, Map<String, Object> secondMap) {
15        for (String key : secondMap.keySet()) {
16            Object firstValue = firstMap.get(key);
17            Object secondValue = secondMap.get(key);
18
19            // If the current key is present in both maps and both values are also maps, then merge them recursively.
20            if (isMap(firstValue) && isMap(secondValue)) {
21                Map<String, Object> firstMapValue = (Map<String, Object>) firstValue;
22                Map<String, Object> secondMapValue = (Map<String, Object>) secondValue;
23                firstMap.put(key, deepMerge(firstMapValue, secondMapValue));
24            } else {
25                // If the second map has a key that's not in the first or the values are not maps, put it in the first map.
26                firstMap.put(key, secondValue);
27            }
28        }
29
30        // Return the merged Map object.
31        return firstMap;
32    }
33
34    // Example usage:
35    public static void main(String[] args) {
36        Map<String, Object> map1 = new HashMap<>();
37        map1.put("a", 1);
38        map1.put("c", 3);
39
40        Map<String, Object> map2 = new HashMap<>();
41        map2.put("a", 2);
42        map2.put("b", 2);
43
44        Map<String, Object> mergedMap = deepMerge(map1, map2);
45      
46        // Should display: {a=2, b=2, c=3}
47        System.out.println(mergedMap);
48    }
49}
50
1#include <unordered_map>
2#include <vector>
3#include <string>
4#include <any>
5
6// Function to check if a std::any value is an object (i.e., std::unordered_map).
7bool isObject(const std::any &item) {
8    if (item.type() == typeid(std::unordered_map<std::string, std::any>)) {
9        return true;
10    }
11    return false;
12}
13
14// Function to check if a std::any value is an array (i.e., std::vector).
15bool isArray(const std::any &item) {
16    if (item.type() == typeid(std::vector<std::any>)) {
17        return true;
18    }
19    return false;
20}
21
22// Function to deeply merge two objects, combining their properties and sub-properties.
23std::any deepMerge(std::any &firstObject, std::any &secondObject) {
24    if (!isObject(firstObject) || !isObject(secondObject)) {
25        return secondObject;
26    }
27
28    if (isArray(firstObject) != isArray(secondObject)) {
29        return secondObject;
30    }
31
32    std::unordered_map<std::string, std::any>& firstMap = 
33        std::any_cast<std::unordered_map<std::string, std::any>&>(firstObject);
34    std::unordered_map<std::string, std::any>& secondMap = 
35        std::any_cast<std::unordered_map<std::string, std::any>&>(secondObject);
36  
37    for (auto &pair : secondMap) {
38        const std::string &key = pair.first;
39        if (firstMap.find(key) == firstMap.end()) {
40            firstMap[key] = pair.second;
41        } else {
42            firstMap[key] = deepMerge(firstMap[key], pair.second);
43        }
44    }
45    return firstObject;
46}
47
48// Example usage:
49// std::unordered_map<std::string, std::any> obj1 = {{"a", 1}, {"c", 3}};
50// std::unordered_map<std::string, std::any> obj2 = {{"a", 2}, {"b", 2}};
51// auto result = deepMerge(obj1, obj2);
52// The resulting 'obj1' will be deep-merged with 'obj2'.
53
1// Function to deeply merge two objects, combining their properties and sub-properties.
2function deepMerge(firstObject: any, secondObject: any): any {
3    // Helper function to check if a value is an object.
4    const isObject = (item: any): boolean => item && typeof item === 'object' && !Array.isArray(item);
5
6    // Helper function to check if a value is an array.
7    const isArray = (item: any): boolean => Array.isArray(item);
8
9    // If either argument is not an object or array, return the secondObject.
10    if (!isObject(firstObject) || !isObject(secondObject)) {
11        return secondObject;
12    }
13
14    // If the types of container for both objects differ (one is array and one is object), return secondObject.
15    if (isArray(firstObject) !== isArray(secondObject)) {
16        return secondObject;
17    }
18
19    // Iterate over each property of the secondObject.
20    for (const key in secondObject) {
21        // If the property key is from the object's own properties (not inherited).
22        if (secondObject.hasOwnProperty(key)) {
23            // Recursively merge properties from both objects.
24            firstObject[key] = deepMerge(firstObject[key], secondObject[key]);
25        }
26    }
27  
28    // Return the merged firstObject, which now contains properties from both objects.
29    return firstObject;
30}
31
32// Example usage:
33// let obj1 = {"a": 1, "c": 3}, obj2 = {"a": 2, "b": 2};
34// deepMerge(obj1, obj2); // Should log: {"a": 2, "c": 3, "b": 2}
35

Time and Space Complexity

Time Complexity

The time complexity of the deepMerge function is a bit tricky to calculate due to its recursive nature. It depends on the structure and size of the two input objects, obj1 and obj2. For each key in obj2, it recursively merges the corresponding values. If n is the total number of keys in both obj1 and obj2 at all levels, and assuming the worst case where each value is a nested object requiring a recursive merge, the time complexity would be O(n). It's important to note, though, that each merge itself takes time proportional to the number of keys in the object being merged, which could imply more than just a simple O(n) complexity, but for each merge operation, we consider a constant time assuming that objects/arrays being merged at the same depth are relatively small.

Note: The recursion depth also depends on the depth of the object structure, which might impact the time complexity if we account for the cost of function calls; however, this is often disregarded in favor of analyzing the operation's complexity on the data set rather than the call stack.

Space Complexity

The space complexity is affected by two factors: the depth of the recursion (call stack) and the creation of new objects/arrays during the merge process.

  1. Recursion Depth (Call Stack): If we consider d to be the maximum depth of recursion (which is the deepest level of nested objects/arrays), the space complexity in terms of the call stack would be O(d).

  2. Object Creation: Since the function modifies obj1 directly without creating new objects for each merge operation, the space complexity due to object creation would be O(1) – constant space.

Taking both points into account, the overall space complexity of deepMerge would be O(d), assuming that we only consider the additional space required by the recursion stack and not the space taken by the input objects, which would remain the same throughout the execution of the function.


Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄