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 <= 106This 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.
We 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.
C
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.
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.
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.
JavaScript
Time Complexity: O(n log n + m log m) due to sorting each array.
Space Complexity: O(n + m) for the merged results.
| Approach | Complexity |
|---|---|
| Map-Based Merging | Time Complexity: O((n + m) log(n + m)) where n and m are the lengths of |
| Combined Sorting and Merging | Time Complexity: O(n log n + m log m) due to sorting each array. |
Median of Two Sorted Arrays - Binary Search - Leetcode 4 • NeetCode • 551,948 views views
Watch 9 more video solutions →Practice Join Two Arrays by ID with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor