2722. Join Two Arrays by ID

Problem Description

The problem provides two arrays, arr1 and arr2, each containing objects that have an id field with an integer value. The goal is to merge these arrays into a single array joinedArray in such a way that joinedArray has the combined contents of both arr1 and arr2, with each object having a unique id. If an id exists in only one array, the corresponding object is included in joinedArray without changes. If the same id appears in both arrays, then the resultant object in joinedArray should have its properties merged; if a property exists only in one object, it is directly taken over, but if a property is present in both, the value from the object in arr2 must overwrite the value from arr1. Finally, joinedArray is sorted in ascending order by the id key.

Intuition

To solve this problem, we need to find an efficient way to merge the objects based on their id. A Map data structure is suitable for this task because it allows quick access and insertion of key-value pairs where the key is unique (the id in our case). The following steps exemplify the approach:

1. Create a new Map, and populate it with objects from arr1, using id as the key. This enables us to quickly locate any object based on its id.

2. Go through each object in arr2, check if an object with the same id already exists in the Map:

   • If it does, merge the existing object with the object from arr2. Object destructuring ({ ...d.get(x.id), ...x }) facilitates this by copying properties from both objects into a new object, with properties from x (the object from arr2) having priority in case of any conflicts.

   • If it does not, simply add the object from arr2 to the Map.

3. Convert the Map values into an array using [...d.values()], which ensures that each id is represented by a single, merged object.

4. Sort the resulting array by id in ascending order.

This method ensures that we honor the conditions for merging and respect the values from arr2 in cases of overlap, all while preparing the joinedArray to be returned with the correct order of id values.

Solution Approach

The solution approach is straightforward and efficient, leveraging the JavaScript Map object to handle merging and ensuring unique id values. Here's a walkthrough of the implementation:

1. Initialize a new Map and populate it with the id and corresponding object from arr1:

1const d = new Map(arr1.map(x => [x.id, x]));

In this line, arr1.map(x => [x.id, x]) effectively prepares an array of [id, object] pairs that can be accepted by the Map constructor, establishing a direct mapping between each id and its respective object.

2. Iterate through arr2 and merge or add objects as necessary:

1arr2.forEach(x => {
2    if (d.has(x.id)) {
3        d.set(x.id, { ...d.get(x.id), ...x });
4    } else {
5        d.set(x.id, x);
6    }
7});

In this snippet, d.has(x.id) checks if the current id from arr2 is already present in the map d. If it is, the objects from arr1 and arr2 are merged with object spread syntax { ...d.get(x.id), ...x }, where properties from x (from arr2) can overwrite those from d.get(x.id) (from arr1) in case of duplication. If the id is not present, the id and object are added to the map as a new entry.

3. Transform the Map into an array and sort the objects by id:

1return [...d.values()].sort((a, b) => a.id - b.id);

Here, [...d.values()] transforms the Map values (our merged objects) into an array. The sort function is used to sort the array in ascending order based on the id. The comparator (a, b) => a.id - b.id ensures a numerical sort rather than a lexicographic one, which is crucial as ids are integers.

This approach elegantly solves the problem by constructing a Map, handling the merging logic through conditions and object spreading, and then returning the sorted array of unique objects. By using Map, we can efficiently look up and decide how to handle each object from arr2, making the algorithm both straightforward in logic and practical in terms of computation complexity.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach described above.

Suppose arr1 and arr2 are as follows:

1const arr1 = [{ id: 1, name: 'John', age: 25 }, { id: 2, name: 'Jane' }];
2const arr2 = [{ id: 2, city: 'New York' }, { id: 1, age: 26 }, { id: 3, name: 'Kyle' }];

We want to merge these arrays into joinedArray by following the solution's steps.

1. Initialize a new Map and populate it with the id and corresponding object from arr1:

   1const d = new Map(arr1.map(x => [x.id, x]));
   2// Map content after initialization:
   3// 1 => { id: 1, name: 'John', age: 25 }
   4// 2 => { id: 2, name: 'Jane' }

   We start with arr1, turning it into a Map where each object is keyed by its id.

2. Iterate through arr2 and merge or add objects as necessary:

   1arr2.forEach(x => {
   2    if (d.has(x.id)) {
   3        d.set(x.id, { ...d.get(x.id), ...x });
   4    } else {
   5        d.set(x.id, x);
   6    }
   7});
   8
   9// Map content after processing arr2:
   10// 1 => { id: 1, name: 'John', age: 26 }
   11// 2 => { id: 2, name: 'Jane', city: 'New York' }
   12// 3 => { id: 3, name: 'Kyle' }

   As we process arr2, we check if an id is already in the map:

   • For id: 2, we find it in the map and merge the object with { city: 'New York' }. Jane now also has a city property.
   • For id: 1, we merge and update John's age to 26.
   • id: 3 is new, so we add { id: 3, name: 'Kyle' } to the map.

3. Transform the Map into an array and sort the objects by id:

   1return [...d.values()].sort((a, b) => a.id - b.id);
   2// Resulting joinedArray:
   3// [{ id: 1, name: 'John', age: 26 },
   4//  { id: 2, name: 'Jane', city: 'New York' },
   5//  { id: 3, name: 'Kyle' }]

   Finally, we convert the Map back into an array of values and sort this array by id. This gives us the correctly merged and ordered joinedArray.

Through this example, we've seen the effectiveness of using a Map to identify unique objects and merge them when necessary, ensuring that arr2 has precedence in properties, and finished by sorting the joinedArray in ascending order by id.

Solution Implementation

Time and Space Complexity

Time Complexity:

1. The time complexity for creating the Map d from arr1 is O(n), where n is the number of elements in arr1. This involves iterating over arr1 and inserting each element into the Map.

2. The time complexity for the forEach loop over arr2 is O(m), where m is the number of elements in arr2. Inside this loop, checking for the existence of an element with has and updating or setting with set is O(1) because Maps in TypeScript/JavaScript typically provide these operations with constant time complexity.

3. The spread operator ... used in the merge { ...d.get(x.id), ...x } has a time complexity that is linear to the number of properties in the objects being merged. Since this is inside the loop, its impact depends on the size of objects; if we assume they have k properties on average, this operation would have a complexity of O(k) every time it is executed.

4. The sort function has a worst-case time complexity of O(p log(p)), where p is the number of elements in the resulting array which can be at most n + m.

Overall, the time complexity would be O(n) + O(m) + O(mk) + O((n+m) log(n+m)). Assuming k is not very large and can be considered nearly constant, we can simplify this to O((n+m) log(n+m)).

Space Complexity:

1. The space complexity for the Map d involves storing up to n+m elements, giving a space complexity of O(n+m).

2. If the merge { ...d.get(x.id), ...x } creates new objects, this happens m times at most, but does not increase the overall number of keys in the final map, so the space complexity remains O(n+m) for the Map itself.

3. The array returned by [...d.values()] will contain at most n+m elements, so this is O(n+m).

Given these considerations, the overall space complexity of the function is O(n+m).