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:
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 arraysarr1 and arr2 has a unique integer id key2 <= JSON.stringify(arr1).length <= 1062 <= JSON.stringify(arr2).length <= 106In #2722 Join Two Arrays by ID, you are given two arrays of objects where each object contains a unique id. The goal is to combine both arrays so that objects with the same id are merged into a single object, while preserving all unique entries. When the same property exists in both objects, the value from the second array should overwrite the one from the first.
A practical approach is to use a hash map (dictionary) keyed by id. First, iterate through the first array and store each object in the map. Then process the second array: if the id already exists, merge the properties; otherwise insert it as a new entry. After processing both arrays, extract the values from the map and sort them by id to produce the final result.
This approach efficiently handles merging and lookups in constant time per operation, leading to an overall linear traversal of both arrays.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map Merge + Sort by ID | O(n + m + k log k) | O(n + m) |
NeetCode
This approach utilizes a map or dictionary to streamline the merging process. By iterating over the two input arrays, we can store each object in a map with its id as the key. This allows constant-time access when merging objects sharing the same id. After processing both arrays, the map's entries can be retrieved and sorted by id to form the final result.
Time Complexity: O((n + m) log(n + m)) where n and m are the lengths of arr1 and arr2, due to the sorting operation.
Space Complexity: O(n + m) for the storage of objects in the dictionary.
1def join_arrays(arr1, arr2):
2 merged_dict = {}
3
4 for obj in arr1:
5 merged_dict[obj['id']] = obj
6
7 for obj in arr2:
8 if obj['id'] in merged_dict:
9 merged_dict[obj['id']].update(obj)
10 else:
11 merged_dict[obj['id']] = obj
12
13 joined_array = list(merged_dict.values())
14 joined_array.sort(key=lambda x: x['id'])
15
16 return joined_array
17We start by creating an empty dictionary merged_dict to serve as our map. Traverse through arr1, inserting each object into the dictionary using its id as the key. We then iterate over arr2, and for any id already present in the dictionary, we update the respective object, allowing the properties of arr2 to override those in arr1. Finally, we convert the map's values to a list and sort them by id before returning.
This method involves sorting both arrays prior to merging. After sorting, we can employ a two-pointer technique to iterate through the arrays simultaneously, aligning ids and merging objects as necessary. By maintaining an additional list, the sorted and merged result can be constructed efficiently.
Time Complexity: O(n log n + m log m) due to sorting each array.
Space Complexity: O(n + m) for the merged results.
1import java.util.*;
2
3
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems involving array merging and hash maps are very common in FAANG-style interviews. While the exact problem may vary, the concept of joining datasets by a key and resolving conflicts is frequently tested.
Sorting ensures the final output is ordered by the id field as typically required by the problem statement. After merging using a hash map, the entries may not be in order, so sorting guarantees consistent output.
A hash map (or dictionary) is the best data structure because it allows constant-time lookup and updates by id. This makes it easy to merge objects efficiently when the same id appears in both arrays.
The optimal approach uses a hash map keyed by the id field. Insert objects from the first array, then merge or insert objects from the second array. Finally, collect the merged objects and sort them by id.
We first sort arr1 and arr2 in ascending order of their id. Using two pointers, we walk through both lists, merging objects with matching ids using a hashmap (caused by the call to putAll() for objects with the same id), and appending the results to our list.