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.
1#include <stdio.h>
2#
In this C solution, we combine objects into the result array and use the function qsort to sort it by id. We iterate through both input arrays to add objects to result, checking an inner loop to handle overriding by arr2.
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.