2722. Join Two Arrays by ID
Problem Description
The problem provides two arrays, arr1
and arr2
, each containing objects that have an id
field with an integer value. The goal is to merge these arrays into a single array joinedArray
in such a way that joinedArray
has the combined contents of both arr1
and arr2
, with each object having a unique id
. If an id
exists in only one array, the corresponding object is included in joinedArray
without changes. If the same id
appears in both arrays, then the resultant object in joinedArray
should have its properties merged; if a property exists only in one object, it is directly taken over, but if a property is present in both, the value from the object in arr2
must overwrite the value from arr1
. Finally, joinedArray
is sorted in ascending order by the id
key.
Intuition
To solve this problem, we need to find an efficient way to merge the objects based on their id
. A Map
data structure is suitable for this task because it allows quick access and insertion of key-value pairs where the key is unique (the id
in our case). The following steps exemplify the approach:
-
Create a new
Map
, and populate it with objects fromarr1
, usingid
as the key. This enables us to quickly locate any object based on itsid
. -
Go through each object in
arr2
, check if an object with the sameid
already exists in theMap
:-
If it does, merge the existing object with the object from
arr2
. Object destructuring ({ ...d.get(x.id), ...x }
) facilitates this by copying properties from both objects into a new object, with properties fromx
(the object fromarr2
) having priority in case of any conflicts. -
If it does not, simply add the object from
arr2
to theMap
.
-
-
Convert the
Map
values into an array using[...d.values()]
, which ensures that each id is represented by a single, merged object. -
Sort the resulting array by
id
in ascending order.
This method ensures that we honor the conditions for merging and respect the values from arr2
in cases of overlap, all while preparing the joinedArray
to be returned with the correct order of id
values.
Solution Approach
The solution approach is straightforward and efficient, leveraging the JavaScript Map
object to handle merging and ensuring unique id
values. Here's a walkthrough of the implementation:
- Initialize a new
Map
and populate it with theid
and corresponding object fromarr1
:
const d = new Map(arr1.map(x => [x.id, x]));
In this line, arr1.map(x => [x.id, x])
effectively prepares an array of [id, object]
pairs that can be accepted by the Map
constructor, establishing a direct mapping between each id
and its respective object.
- Iterate through
arr2
and merge or add objects as necessary:
arr2.forEach(x => {
if (d.has(x.id)) {
d.set(x.id, { ...d.get(x.id), ...x });
} else {
d.set(x.id, x);
}
});
In this snippet, d.has(x.id)
checks if the current id
from arr2
is already present in the map d
. If it is, the objects from arr1
and arr2
are merged with object spread syntax { ...d.get(x.id), ...x }
, where properties from x
(from arr2
) can overwrite those from d.get(x.id)
(from arr1
) in case of duplication. If the id
is not present, the id
and object are added to the map as a new entry.
- Transform the
Map
into an array and sort the objects byid
:
return [...d.values()].sort((a, b) => a.id - b.id);
Here, [...d.values()]
transforms the Map
values (our merged objects) into an array. The sort
function is used to sort the array in ascending order based on the id
. The comparator (a, b) => a.id - b.id
ensures a numerical sort rather than a lexicographic one, which is crucial as id
s are integers.
This approach elegantly solves the problem by constructing a Map
, handling the merging logic through conditions and object spreading, and then returning the sorted array of unique objects. By using Map
, we can efficiently look up and decide how to handle each object from arr2
, making the algorithm both straightforward in logic and practical in terms of computation complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach described above.
Suppose arr1
and arr2
are as follows:
const arr1 = [{ id: 1, name: 'John', age: 25 }, { id: 2, name: 'Jane' }]; const arr2 = [{ id: 2, city: 'New York' }, { id: 1, age: 26 }, { id: 3, name: 'Kyle' }];
We want to merge these arrays into joinedArray
by following the solution's steps.
-
Initialize a new
Map
and populate it with theid
and corresponding object fromarr1
:const d = new Map(arr1.map(x => [x.id, x])); // Map content after initialization: // 1 => { id: 1, name: 'John', age: 25 } // 2 => { id: 2, name: 'Jane' }
We start with
arr1
, turning it into aMap
where each object is keyed by itsid
. -
Iterate through
arr2
and merge or add objects as necessary:arr2.forEach(x => { if (d.has(x.id)) { d.set(x.id, { ...d.get(x.id), ...x }); } else { d.set(x.id, x); } }); // Map content after processing arr2: // 1 => { id: 1, name: 'John', age: 26 } // 2 => { id: 2, name: 'Jane', city: 'New York' } // 3 => { id: 3, name: 'Kyle' }
As we process
arr2
, we check if anid
is already in the map:- For
id: 2
, we find it in the map and merge the object with{ city: 'New York' }
. Jane now also has acity
property. - For
id: 1
, we merge and update John'sage
to 26. id: 3
is new, so we add{ id: 3, name: 'Kyle' }
to the map.
- For
-
Transform the
Map
into an array and sort the objects byid
:return [...d.values()].sort((a, b) => a.id - b.id); // Resulting joinedArray: // [{ id: 1, name: 'John', age: 26 }, // { id: 2, name: 'Jane', city: 'New York' }, // { id: 3, name: 'Kyle' }]
Finally, we convert the
Map
back into an array of values and sort this array byid
. This gives us the correctly merged and orderedjoinedArray
.
Through this example, we've seen the effectiveness of using a Map
to identify unique objects and merge them when necessary, ensuring that arr2
has precedence in properties, and finished by sorting the joinedArray
in ascending order by id
.
Solution Implementation
1def join(array1, array2):
2 # Create a dictionary to hold merged objects,
3 # using 'id' as the key for fast access.
4 merged_data = {}
5
6 # Process the first array and map each object's 'id' to itself.
7 for element in array1:
8 merged_data[element['id']] = element
9
10 # Iterate through the second array.
11 for element in array2:
12 # If the 'id' already exists in the dictionary, merge the current object
13 # with the existing one by updating the dictionary at this 'id' key.
14 if element['id'] in merged_data:
15 existing_element = merged_data[element['id']]
16 # Merge existing_element with element. In case of conflicting keys,
17 # the values from element will update those from existing_element.
18 merged_data[element['id']] = {**existing_element, **element}
19 else:
20 # If the 'id' is new, add the current object to the dictionary.
21 merged_data[element['id']] = element
22
23 # Convert the merged data back to a list, then sort by 'id' and return.
24 # Sorting is done by using a lambda function that extracts the 'id' for comparison.
25 return sorted(merged_data.values(), key=lambda x: x['id'])
26
1import java.util.*;
2import java.util.stream.Collectors;
3
4public class ArrayJoiner {
5
6 /**
7 * Joins two lists of objects based on their 'id' property, merges objects with the
8 * same 'id' from both lists, and includes all unique objects. The resulting list is
9 * sorted by the 'id' property in ascending order.
10 *
11 * @param list1 The first list of objects with 'id' property
12 * @param list2 The second list of objects with 'id' property
13 * @return A sorted list of merged objects
14 */
15 public List<Map<String, Object>> join(List<Map<String, Object>> list1, List<Map<String, Object>> list2) {
16 // Create a Map to hold merged objects with the 'id' as the key
17 Map<Integer, Map<String, Object>> mergedData = new HashMap<>();
18
19 // Process the first list and map each object's 'id' to the object itself
20 for (Map<String, Object> element : list1) {
21 mergedData.put((Integer) element.get("id"), element);
22 }
23
24 // Iterate through the second list
25 for (Map<String, Object> element : list2) {
26 Integer id = (Integer) element.get("id");
27 // If the 'id' already exists in the map, merge the existing object with the current one
28 if (mergedData.containsKey(id)) {
29 Map<String, Object> existingElement = mergedData.get(id);
30 // Combine all keys from both maps, preferring the second element's value if a key collision occurs
31 Map<String, Object> combinedElement = new HashMap<>(existingElement);
32 combinedElement.putAll(element);
33 mergedData.put(id, combinedElement);
34 } else {
35 // If the 'id' is new, add the current object to the map
36 mergedData.put(id, element);
37 }
38 }
39
40 // Convert the merged map to a list and sort it by 'id' in ascending order
41 return mergedData.values().stream()
42 .sorted(Comparator.comparingInt(element -> (Integer) element.get("id")))
43 .collect(Collectors.toList());
44 }
45}
46
1#include <vector>
2#include <map>
3#include <algorithm>
4
5// Function to join two vectors of objects based on their 'id' property.
6// It merges objects with the same 'id' and includes all unique objects from both vectors.
7// The function also sorts the resulting vector by the 'id' property in ascending order.
8std::vector<std::map<std::string, int>> Join(
9 const std::vector<std::map<std::string, int>>& array1,
10 const std::vector<std::map<std::string, int>>& array2) {
11
12 // Create a map to hold merged objects, using 'id' as the key.
13 std::map<int, std::map<std::string, int>> mergedData;
14
15 // Process the first vector and map each object's 'id' to itself.
16 for (const auto& element : array1) {
17 mergedData[element.at("id")] = element;
18 }
19
20 // Iterate through the second vector.
21 for (const auto& element : array2) {
22 // If the 'id' already exists in the map, merge the existing object with the current one.
23 if (mergedData.find(element.at("id")) != mergedData.end()) {
24 for (const auto& pair : element) {
25 mergedData[element.at("id")][pair.first] = pair.second;
26 }
27 } else {
28 // If the 'id' is new, add the current object to the map.
29 mergedData[element.at("id")] = element;
30 }
31 }
32
33 // Create a vector to hold the merged objects for sorting.
34 std::vector<std::map<std::string, int>> mergedVector;
35
36 // Extract values from the map and push them into the vector.
37 for (const auto& pair : mergedData) {
38 mergedVector.push_back(pair.second);
39 }
40
41 // Sort the vector by the 'id' in ascending order.
42 std::sort(mergedVector.begin(), mergedVector.end(),
43 [](const std::map<std::string, int>& a, const std::map<std::string, int>& b) {
44 return a.at("id") < b.at("id");
45 });
46
47 return mergedVector;
48}
49
1// Function to join two arrays of objects based on their 'id' property.
2// It merges objects with the same 'id' and includes all unique objects from both arrays.
3// The function also sorts the resulting array by the 'id' property in ascending order.
4function join(array1: any[], array2: any[]): any[] {
5 // Create a Map to hold merged objects, using 'id' as the key.
6 const mergedData = new Map<number, any>();
7
8 // Process the first array and map each object's 'id' to itself.
9 array1.forEach(element => mergedData.set(element.id, element));
10
11 // Iterate through the second array.
12 array2.forEach(element => {
13 // If the 'id' already exists in the map, merge the existing object with the current one.
14 if (mergedData.has(element.id)) {
15 const existingElement = mergedData.get(element.id);
16 mergedData.set(element.id, { ...existingElement, ...element });
17 } else {
18 // If the 'id' is new, add the current object to the map.
19 mergedData.set(element.id, element);
20 }
21 });
22
23 // Return a sorted array of the merged objects, based on their 'id'.
24 return Array.from(mergedData.values()).sort((elementA, elementB) => elementA.id - elementB.id);
25}
26
Time and Space Complexity
Time Complexity:
-
The time complexity for creating the Map
d
fromarr1
isO(n)
, wheren
is the number of elements inarr1
. This involves iterating overarr1
and inserting each element into the Map. -
The time complexity for the
forEach
loop overarr2
isO(m)
, wherem
is the number of elements inarr2
. Inside this loop, checking for the existence of an element withhas
and updating or setting withset
isO(1)
because Maps in TypeScript/JavaScript typically provide these operations with constant time complexity. -
The spread operator
...
used in the merge{ ...d.get(x.id), ...x }
has a time complexity that is linear to the number of properties in the objects being merged. Since this is inside the loop, its impact depends on the size of objects; if we assume they havek
properties on average, this operation would have a complexity ofO(k)
every time it is executed. -
The
sort
function has a worst-case time complexity ofO(p log(p))
, wherep
is the number of elements in the resulting array which can be at mostn + m
.
Overall, the time complexity would be O(n) + O(m) + O(mk) + O((n+m) log(n+m))
. Assuming k
is not very large and can be considered nearly constant, we can simplify this to O((n+m) log(n+m))
.
Space Complexity:
-
The space complexity for the Map
d
involves storing up ton+m
elements, giving a space complexity ofO(n+m)
. -
If the merge
{ ...d.get(x.id), ...x }
creates new objects, this happensm
times at most, but does not increase the overall number of keys in the final map, so the space complexity remainsO(n+m)
for the Map itself. -
The array returned by
[...d.values()]
will contain at mostn+m
elements, so this isO(n+m)
.
Given these considerations, the overall space complexity of the function is O(n+m)
.
Which data structure is used to implement recursion?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!