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.

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

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.