Sponsored
Sponsored
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
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.
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
3class Solution {
4 public List<Map<String, Integer>> joinArrays(List<Map<String, Integer>> arr1, List<Map<String, Integer>> arr2) {
5 arr1.sort(Comparator.comparingInt(o -> o.get("id")));
6 arr2.sort(Comparator.comparingInt(o -> o.get("id")));
7
8 List<Map<String, Integer>> result = new ArrayList<>();
9 int i = 0, j = 0;
10
11 while(i < arr1.size() && j < arr2.size()) {
12 int id1 = arr1.get(i).get("id");
13 int id2 = arr2.get(j).get("id");
14
15 if(id1 == id2) {
16 Map<String, Integer> merged = new HashMap<>(arr1.get(i));
17 merged.putAll(arr2.get(j));
18 result.add(merged);
19 i++; j++;
20 } else if(id1 < id2) {
21 result.add(arr1.get(i++));
22 } else {
23 result.add(arr2.get(j++));
24 }
25 }
26
27 while(i < arr1.size()) result.add(arr1.get(i++));
28 while(j < arr2.size()) result.add(arr2.get(j++));
29
30 return result;
31 }
32}
33We 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.