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 <= 106Problem Overview: You receive two arrays of objects where each object contains an id and additional properties. The task is to join both arrays by matching id values. If the same id appears in both arrays, merge their properties into one object. The final result must contain unique ids with merged values.
Approach 1: Map-Based Merging (O(n + m) time, O(n + m) space)
This approach uses a hash map keyed by id. Iterate through the first array and insert each object into the map. Then iterate through the second array. For each element, perform a constant-time hash lookup. If the id already exists, merge the fields so the second array’s values overwrite duplicates. If the id does not exist, insert it directly. After processing both arrays, convert the map values into a result list and sort by id if required by the problem. The key insight is that hash lookups make merging efficient without nested iteration. This approach relies on concepts from hash map usage and array traversal.
Approach 2: Combined Sorting and Merging (O((n + m) log(n + m)) time, O(1)–O(n + m) space)
This method treats the task like merging two sorted datasets. First combine the arrays and sort them by id. Once sorted, iterate sequentially and merge adjacent objects that share the same id. Because identical ids become neighbors after sorting, you can combine them while scanning with a single pointer. Another variation sorts both arrays individually and uses a two-pointer merge process similar to merge sort. The advantage is predictable ordering and no hash map dependency. This method highlights patterns from sorting and two-pointer merging techniques.
Recommended for interviews: The map-based approach is usually the expected solution. It runs in linear time and clearly demonstrates your ability to use hash-based indexing to eliminate nested loops. Sorting-based merging is still valid and useful when input data is already sorted or when deterministic ordering is required without additional data structures.
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.
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.
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.
Java
JavaScript
Time Complexity: O(n log n + m log m) due to sorting each array.
Space Complexity: O(n + m) for the merged results.
TypeScript
| 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. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Map-Based Merging | O(n + m) | O(n + m) | General case. Best performance when arrays are unsorted and fast lookups are needed. |
| Combined Sorting and Merging | O((n + m) log(n + m)) | O(1)–O(n + m) | Useful when deterministic ordering is required or when arrays are already sorted. |
Join Two Arrays by ID | Leetcode 2722 | JSON | 30 Days of JavaScript #javascript #leetcode • Learn With Chirag • 2,101 views views
Watch 5 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