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:
const 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.

  1. Iterate through arr2 and merge or add objects as necessary:
arr2.forEach(x => {
    if (d.has(x.id)) {
        d.set(x.id, { ...d.get(x.id), ...x });
    } else {
        d.set(x.id, x);
    }
});

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.

  1. Transform the Map into an array and sort the objects by id:
return [...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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

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

Suppose arr1 and arr2 are as follows:

const arr1 = [{ id: 1, name: 'John', age: 25 }, { id: 2, name: 'Jane' }];
const 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:

    const d = new Map(arr1.map(x => [x.id, x]));
    // Map content after initialization:
    // 1 => { id: 1, name: 'John', age: 25 }
    // 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:

    arr2.forEach(x => {
        if (d.has(x.id)) {
            d.set(x.id, { ...d.get(x.id), ...x });
        } else {
            d.set(x.id, x);
        }
    });
    
    // Map content after processing arr2:
    // 1 => { id: 1, name: 'John', age: 26 }
    // 2 => { id: 2, name: 'Jane', city: 'New York' }
    // 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:

    return [...d.values()].sort((a, b) => a.id - b.id);
    // Resulting joinedArray:
    // [{ id: 1, name: 'John', age: 26 },
    //  { id: 2, name: 'Jane', city: 'New York' },
    //  { 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

1def join(array1, array2):
2    # Create a dictionary to hold merged objects,
3    # using 'id' as the key for fast access.
4    merged_data = {}
5
6    # Process the first array and map each object's 'id' to itself.
7    for element in array1:
8        merged_data[element['id']] = element
9
10    # Iterate through the second array.
11    for element in array2:
12        # If the 'id' already exists in the dictionary, merge the current object 
13        # with the existing one by updating the dictionary at this 'id' key.
14        if element['id'] in merged_data:
15            existing_element = merged_data[element['id']]
16            # Merge existing_element with element. In case of conflicting keys,
17            # the values from element will update those from existing_element.
18            merged_data[element['id']] = {**existing_element, **element}
19        else:
20            # If the 'id' is new, add the current object to the dictionary.
21            merged_data[element['id']] = element
22
23    # Convert the merged data back to a list, then sort by 'id' and return.
24    # Sorting is done by using a lambda function that extracts the 'id' for comparison.
25    return sorted(merged_data.values(), key=lambda x: x['id'])
26
1import java.util.*;
2import java.util.stream.Collectors;
3
4public class ArrayJoiner {
5  
6    /**
7     * Joins two lists of objects based on their 'id' property, merges objects with the
8     * same 'id' from both lists, and includes all unique objects. The resulting list is
9     * sorted by the 'id' property in ascending order.
10     * 
11     * @param list1 The first list of objects with 'id' property
12     * @param list2 The second list of objects with 'id' property
13     * @return A sorted list of merged objects
14     */
15    public List<Map<String, Object>> join(List<Map<String, Object>> list1, List<Map<String, Object>> list2) {
16        // Create a Map to hold merged objects with the 'id' as the key
17        Map<Integer, Map<String, Object>> mergedData = new HashMap<>();
18
19        // Process the first list and map each object's 'id' to the object itself
20        for (Map<String, Object> element : list1) {
21            mergedData.put((Integer) element.get("id"), element);
22        }
23
24        // Iterate through the second list
25        for (Map<String, Object> element : list2) {
26            Integer id = (Integer) element.get("id");
27            // If the 'id' already exists in the map, merge the existing object with the current one
28            if (mergedData.containsKey(id)) {
29                Map<String, Object> existingElement = mergedData.get(id);
30                // Combine all keys from both maps, preferring the second element's value if a key collision occurs
31                Map<String, Object> combinedElement = new HashMap<>(existingElement);
32                combinedElement.putAll(element);
33                mergedData.put(id, combinedElement);
34            } else {
35                // If the 'id' is new, add the current object to the map
36                mergedData.put(id, element);
37            }
38        }
39
40        // Convert the merged map to a list and sort it by 'id' in ascending order
41        return mergedData.values().stream()
42                .sorted(Comparator.comparingInt(element -> (Integer) element.get("id")))
43                .collect(Collectors.toList());
44    }
45}
46
1#include <vector>
2#include <map>
3#include <algorithm>
4
5// Function to join two vectors of objects based on their 'id' property.
6// It merges objects with the same 'id' and includes all unique objects from both vectors.
7// The function also sorts the resulting vector by the 'id' property in ascending order.
8std::vector<std::map<std::string, int>> Join(
9    const std::vector<std::map<std::string, int>>& array1,
10    const std::vector<std::map<std::string, int>>& array2) {
11  
12    // Create a map to hold merged objects, using 'id' as the key.
13    std::map<int, std::map<std::string, int>> mergedData;
14
15    // Process the first vector and map each object's 'id' to itself.
16    for (const auto& element : array1) {
17        mergedData[element.at("id")] = element;
18    }
19
20    // Iterate through the second vector.
21    for (const auto& element : array2) {
22        // If the 'id' already exists in the map, merge the existing object with the current one.
23        if (mergedData.find(element.at("id")) != mergedData.end()) {
24            for (const auto& pair : element) {
25                mergedData[element.at("id")][pair.first] = pair.second;
26            }
27        } else {
28            // If the 'id' is new, add the current object to the map.
29            mergedData[element.at("id")] = element;
30        }
31    }
32
33    // Create a vector to hold the merged objects for sorting.
34    std::vector<std::map<std::string, int>> mergedVector;
35
36    // Extract values from the map and push them into the vector.
37    for (const auto& pair : mergedData) {
38        mergedVector.push_back(pair.second);
39    }
40
41    // Sort the vector by the 'id' in ascending order.
42    std::sort(mergedVector.begin(), mergedVector.end(),
43        [](const std::map<std::string, int>& a, const std::map<std::string, int>& b) {
44            return a.at("id") < b.at("id");
45        });
46
47    return mergedVector;
48}
49
1// Function to join two arrays of objects based on their 'id' property.
2// It merges objects with the same 'id' and includes all unique objects from both arrays.
3// The function also sorts the resulting array by the 'id' property in ascending order.
4function join(array1: any[], array2: any[]): any[] {
5    // Create a Map to hold merged objects, using 'id' as the key.
6    const mergedData = new Map<number, any>();
7
8    // Process the first array and map each object's 'id' to itself.
9    array1.forEach(element => mergedData.set(element.id, element));
10
11    // Iterate through the second array.
12    array2.forEach(element => {
13        // If the 'id' already exists in the map, merge the existing object with the current one.
14        if (mergedData.has(element.id)) {
15            const existingElement = mergedData.get(element.id);
16            mergedData.set(element.id, { ...existingElement, ...element });
17        } else {
18            // If the 'id' is new, add the current object to the map.
19            mergedData.set(element.id, element);
20        }
21    });
22
23    // Return a sorted array of the merged objects, based on their 'id'.
24    return Array.from(mergedData.values()).sort((elementA, elementB) => elementA.id - elementB.id);
25}
26

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).


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used to implement recursion?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More