Join Two Arrays by ID

Problem Statement

In this task, you need to merge two arrays of objects, arr1 and arr2, based on a unique id field present in every object of both arrays. The result should be a new array called joinedArray. The merging process involves the following:

• The joinedArray should only contain unique id values; if an id is present in both arrays, the properties from arr2 should override similar properties from arr1.
• Any id present in one array and missing in the other should have its object included in joinedArray without alteration.
• All objects in joinedArray should be arranged in an ascending order based on their id.

The goal is to ensure that joinedArray effectively represents a combination of both input arrays while respecting the uniqueness and precedence rules outlined above.

Examples

Example 1

Input:

arr1 = [
  {"id": 1, "x": 1},
  {"id": 2, "x": 9}
],
arr2 = [
{"id": 3, "x": 5}
]

Output:

[
  {"id": 1, "x": 1},
  {"id": 2, "x": 9},
{"id": 3, "x": 5}
]

Explanation:

There are no duplicate ids so arr1 is simply concatenated with arr2.

Example 2

Input:

arr1 = [
{"id": 1, "x": 2, "y": 3},
{"id": 2, "x": 3, "y": 6}
],
arr2 = [
{"id": 2, "x": 10, "y": 20},
{"id": 3, "x": 0, "y": 0}
]

Output:

[
{"id": 1, "x": 2, "y": 3},
{"id": 2, "x": 10, "y": 20},
  {"id": 3, "x": 0, "y": 0}
]

Explanation:

The two objects with id=1 and id=3 are included in the result array without modifiction. The two objects with id=2 are merged together. The keys from arr2 override the values in arr1.

Example 3

Input:

arr1 = [
{"id": 1, "b": {"b": 94},"v": [4, 3], "y": 48}
]
arr2 = [
{"id": 1, "b": {"c": 84}, "v": [1, 3]}
]

Output:

[
{"id": 1, "b": {"c": 84}, "v": [1, 3], "y": 48}
]

Explanation:

The two objects with id=1 are merged together. For the keys "b" and "v" the values from arr2 are used. Since the key "y" only exists in arr1, that value is taken form arr1.

Constraints

• arr1 and arr2 are valid JSON arrays
• Each object in arr1 and arr2 has a unique integer id key
• 2 <= JSON.stringify(arr1).length <= 106
• 2 <= JSON.stringify(arr2).length <= 106

Approach and Intuition

Understanding the approach involves following the merging logic supplemented by examples:

1. Firstly, identify the structure of merging based on the id key in each object:

   • Objects with the same id must be merged.
   • Unique id objects (not existing in both arrays) should typically just be added to joinedArray.

2. The merging priorities need to be clear:

   • For any specific id, properties from objects in arr2 should replace those from arr1.
   • If a property exists only in arr1, it should be retained in the merged object.

3. Consider data structure tools that make this merge efficient:

   • A hashmap (dictionary/associative array), keyed by the id, would allow merging and accessing elements in average constant time.

4. Steps to implement, with reasons drawn from example inputs:

   • Load all entries from arr1 into a hashmap.
   • Traverse through arr2, merging properties into existing hashmap entries where ids match, or adding new entries where they don’t.
   • Convert the hashmap back to an array, ensuring the output is sorted by id as required.

5. In Examples provided:

   • Example 1: Showcases basic concatenation as there are no shared ids.
   • Example 2: Demonstrates the necessity to override values when ids match across arr1 and arr2.
   • Example 3: Highlights property and nested object merging, suggesting handling for more complex data structures.

Applying these insights ensures that all constraints and requirements, such as handling large JSON object lengths and merging object properties correctly, are met properly.

Solutions

var mergeArrays = function(array1, array2) {
    array1.sort((x, y) => x.id - y.id)
    array2.sort((x, y) => x.id - y.id)
    let index1 = 0
    let index2 = 0
    
    const mergedList = []
    
    while(index1 < array1.length && index2 < array2.length) {
    
        if(array1[index1].id === array2[index2].id) {
            mergedList.push({...array1[index1], ...array2[index2]})
            index1++
            index2++
            continue
        }
    
        if(array1[index1].id < array2[index2].id) {
            mergedList.push({...array1[index1]})
            index1++
            continue
        }
    
        mergedList.push({...array2[index2]})
        index2++
    }
    
    while(index1 < array1.length) {
        mergedList.push({...array1[index1]})
        index1++
    }
    
    while(index2 < array2.length) {
        mergedList.push({...array2[index2]})
        index2++
    }
    
    return mergedList
}