Join Two Arrays by ID

Medium

Asked by:

18 views

Topics:

Arrays

Given two arrays arr1 and arr2, return a new array joinedArray. All the objects in each of the two inputs arrays will contain an id field that has an integer value.

joinedArray is an array formed by merging arr1 and arr2 based on their id key. The length of joinedArray should be the length of unique values of id. The returned array should be sorted in ascending order based on the id key.

If a given id exists in one array but not the other, the single object with that id should be included in the result array without modification.

If two objects share an id, their properties should be merged into a single object:

If a key only exists in one object, that single key-value pair should be included in the object.
If a key is included in both objects, the value in the object from arr2 should override the value from arr1.

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 <= 10⁶
2 <= JSON.stringify(arr2).length <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should the output be if an ID exists in one array but not the other? Should the missing values be filled with null or omitted from the output?
What are the possible data types of the values associated with each ID in the arrays? Can they be objects, arrays, or primitive types?
Can the input arrays be empty or null? If so, what should the output be in those cases?
Are the IDs guaranteed to be unique within each input array individually?
What is the expected data type of the ID field (e.g., integer, string)? Are there any constraints on the ID values, such as a maximum length or range?

Brute Force Solution

Approach

We want to combine information from two lists based on matching IDs. The brute force approach is like checking every possible pair of items from the two lists to see if their IDs match, one by one. This guarantees we find all the matching items, but it can take a lot of time.

Here's how the algorithm would work step-by-step:

Take the first item from the first list.
Now, go through every single item in the second list and check if its ID is the same as the ID of the first item from the first list.
If the IDs match, combine the information from both items into a new combined item and save it.
After checking all items in the second list against the first item, move to the second item in the first list.
Repeat the process: check this second item's ID against the ID of every item in the second list.
Continue this process until you have checked every item in the first list against every item in the second list.
At the end, you will have a collection of all the combined items where the IDs matched.

Code Implementation

def join_two_arrays_by_id_brute_force(array_one, array_two):
    combined_array = []

    for first_array_item in array_one:
        # Iterate through the second array
        for second_array_item in array_two:

            # Key decision: compare IDs for a match
            if first_array_item['id'] == second_array_item['id']:

                combined_item = first_array_item.copy()
                combined_item.update(second_array_item)
                combined_array.append(combined_item)

    return combined_array

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each element in the first array (let's say of size n) and for each of these elements, it iterates through every element in the second array (also of size n). This results in comparing each element in the first array with every element in the second array, performing a matching operation for each pair. Thus, we have n * n operations. The total number of operations approximates n², therefore the time complexity is O(n²).

Space Complexity

O(N * M) – The algorithm iterates through each item in the first list (let's say it has size N) and compares it with every item in the second list (let's say it has size M). When the IDs match, a new combined item is created and saved. In the worst-case scenario, every item in the first list matches with every item in the second list, resulting in N * M combined items being stored. Therefore, the auxiliary space required to store the combined items grows proportionally to the product of the sizes of the two input lists. This results in a space complexity of O(N * M).

Optimal Solution

Approach

The key is to organize the first set of items into a format that makes it easy to quickly find matching items in the second set. Then, we build our result by combining information from both sets based on the matching identifiers.

Here's how the algorithm would work step-by-step:

First, take the first set of items and rearrange it into a special lookup table or dictionary. This way, we can instantly find an item's information using its ID.
Now, go through the second set of items, one by one.
For each item in the second set, use its ID to find the matching item in our special lookup table.
If you find a match, combine the information from the two matched items into a new item.
If there's no match in the first set for an ID in the second set, do nothing with that item. You could also say the result should include the entry from the first or second array, depending on the prompt.
Keep building the list of combined items until you've checked every item in the second set.
The resulting list of combined items is your final answer.

Code Implementation

def join_arrays_by_id(array_one, array_two):
    # Create a lookup table for the first array using the 'id' as the key
    first_array_lookup = {item['id']: item for item in array_one}

    result_array = []

    for item_from_second_array in array_two:
        item_id = item_from_second_array['id']

        # Find matching item in the first array
        matching_item_in_first_array = first_array_lookup.get(item_id)

        if matching_item_in_first_array:
            # Merge the two items into a new dictionary
            merged_item = {**matching_item_in_first_array, **item_from_second_array}
            result_array.append(merged_item)

    return result_array

Big(O) Analysis

Time Complexity

O(m + n) – The solution first iterates through the first array of size m to create a lookup table (dictionary) using the ID as the key. This takes O(m) time. Then, it iterates through the second array of size n, and for each element, it performs a lookup in the dictionary, which takes O(1) on average. Therefore, iterating through the second array takes O(n) time. The total time complexity is O(m) + O(n), which simplifies to O(m + n).

Space Complexity

O(N) – The algorithm's space complexity is primarily determined by the lookup table (dictionary) created from the first array of items. This lookup table stores each item from the first array, indexed by its ID, so the size of this table scales linearly with the number of items in the first array. In the worst case, where the first array contains N unique items (where N represents the number of items in the first array), the lookup table will require O(N) space. No other significant auxiliary data structures are used, so the overall space complexity is O(N).

Edge Cases

Case	How to Handle
One or both input arrays are null or empty.	Return an empty array or null if either input is invalid, based on problem specification.
Arrays contain objects with the same ID.	The join operation should either merge the objects or prefer the object from the first array, as defined in the requirements.
Arrays contain objects with null or undefined IDs.	Define how to handle null/undefined IDs, either by treating them as non-matching or considering them for a 'null ID' match.
No matching IDs exist between the two arrays.	The result should be an empty array or contain all elements from both arrays (outer join), according to the problem requirements.
One array is significantly larger than the other.	Use a hash map based on the smaller array's IDs for efficient lookups in the larger array.
The arrays are very large, potentially exceeding memory limits.	Consider a streaming approach, processing the arrays in chunks to limit memory usage.
IDs are not strings or numbers (e.g., objects).	Ensure the comparison of IDs is type-agnostic or specify a type constraint in the problem statement.
Arrays are already sorted by ID.	A two-pointer approach can optimize the join operation in this specific scenario with O(n+m) time complexity.

One or both input arrays are null or empty.

How to Handle:

Return an empty array or null if either input is invalid, based on problem specification.

Arrays contain objects with the same ID.

How to Handle:

The join operation should either merge the objects or prefer the object from the first array, as defined in the requirements.

Arrays contain objects with null or undefined IDs.

How to Handle:

Define how to handle null/undefined IDs, either by treating them as non-matching or considering them for a 'null ID' match.

No matching IDs exist between the two arrays.

How to Handle:

The result should be an empty array or contain all elements from both arrays (outer join), according to the problem requirements.

One array is significantly larger than the other.

How to Handle:

Use a hash map based on the smaller array's IDs for efficient lookups in the larger array.

The arrays are very large, potentially exceeding memory limits.

How to Handle:

Consider a streaming approach, processing the arrays in chunks to limit memory usage.

IDs are not strings or numbers (e.g., objects).

How to Handle:

Ensure the comparison of IDs is type-agnostic or specify a type constraint in the problem statement.

Arrays are already sorted by ID.

How to Handle:

A two-pointer approach can optimize the join operation in this specific scenario with O(n+m) time complexity.