LeetCode Problem Workspace
Join Two Arrays by ID
Merge two arrays of objects by their id keys, resolving conflicts with arr2 values and sorting by id ascending.
0
Topics
1
Code langs
0
Related
Practice Focus
Medium · Join Two Arrays by ID core interview pattern
Answer-first summary
Merge two arrays of objects by their id keys, resolving conflicts with arr2 values and sorting by id ascending.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for Join Two Arrays by ID core interview pattern
To solve Join Two Arrays by ID, combine arr1 and arr2 objects using the id key. When ids overlap, merge objects with arr2 values overriding arr1. Finally, sort the resulting array by id ascending to meet problem requirements and handle unique and conflicting ids correctly.
Problem Statement
You are given two arrays arr1 and arr2 containing objects with integer id keys. Your task is to create a joined array that merges these two arrays based on the id field.
If an id exists in both arrays, merge the objects with keys from arr2 overriding arr1. If an id exists in only one array, include it unchanged. The final joined array must be sorted in ascending order by id.
Examples
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} ]
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} ]
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} ]
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 <= 106
- 2 <= JSON.stringify(arr2).length <= 106
Solution Approach
Use a Map for Merging by ID
Create a Map where each key is the id and the value is the object. Iterate over arr1 and arr2, inserting or merging objects. For duplicates, overwrite with arr2 values to resolve conflicts.
Merge Objects with Care
When an id exists in both arrays, merge their objects field by field. Take keys from arr2 if present; otherwise, keep arr1 values. This ensures correct overriding behavior for overlapping ids.
Sort the Resulting Array
Once all objects are in the Map, convert it to an array and sort it ascending by id. This guarantees that the final array respects the required order and unique ids.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | ** The `arr |
| Space | ** Since we are creating a joinedArray to store the result, which can grow up to the size of arr1 and arr2 we can say that the space complexity is |
Time complexity is O(n + m + k log k) where n and m are the lengths of arr1 and arr2, and k is the number of unique ids. Space complexity is O(k) to store the merged results in a map.
What Interviewers Usually Probe
- Checking if you handle merging overlapping ids correctly.
- Ensuring you sort the final array by id.
- Evaluating if your solution handles unique and missing ids without errors.
Common Pitfalls or Variants
Common pitfalls
- Overwriting arr1 values incorrectly instead of using arr2 overrides.
- Failing to sort the resulting array by id.
- Not handling objects that exist in only one array.
Follow-up variants
- Join arrays by id with nested object merging rules.
- Handle arrays where arr2 may have additional fields not present in arr1.
- Merge arrays where id fields are not initially sorted.
FAQ
What is the main pattern in Join Two Arrays by ID?
The core pattern is merging objects by id, overriding arr1 values with arr2 and sorting the result by id.
How do I handle ids that exist in only one array?
Simply include the object unchanged in the joined array to preserve unique ids.
Should I always overwrite arr1 values with arr2 for duplicate ids?
Yes, arr2 values take priority when merging objects with the same id to satisfy problem constraints.
What is the optimal data structure for merging by id?
Using a Map or dictionary keyed by id ensures efficient merging and easy retrieval for sorting.
Does the joined array need to be sorted?
Yes, sorting by id ascending is required so that the output meets the problem specification.
Solution
Solution 1
#### TypeScript
function join(arr1: ArrayType[], arr2: ArrayType[]): ArrayType[] {
const r = (acc: Obj, x: ArrayType): Obj => ((acc[x.id] = x), acc);
const d = arr1.reduce(r, {});
arr2.forEach(x => {
if (d[x.id]) {
Object.assign(d[x.id], x);
} else {
d[x.id] = x;
}
});
return Object.values(d);
}
type JSONValue = null | boolean | number | string | JSONValue[] | { [key: string]: JSONValue };
type ArrayType = { id: number } & Record<string, JSONValue>;
type Obj = Record<number, ArrayType>;