Problem Description
You are given two 2D integer arrays nums1 and nums2. Each array contains unique ids and is sorted in ascending order by id. Merge the two arrays into one array that is sorted in ascending order by id, where each id should be included only once, and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays, then assume its value in that array to be 0.
Key Insights
- The input arrays are sorted by id, which allows for efficient merging using a two-pointer technique.
- Using a hash table (dictionary) allows for easy accumulation of values for each unique id.
- The result must be sorted by id, which can be achieved by sorting the keys of the hash table before constructing the final output.
Space and Time Complexity
Time Complexity: O(n + m + k log k), where n and m are the lengths of nums1 and nums2, respectively, and k is the number of unique ids in the merged result (the sorting step).
Space Complexity: O(k), for storing the merged results in the hash table.
Solution
To solve the problem, we can use a hash table to accumulate the values for each id from both arrays. We will iterate over both nums1 and nums2, adding the values to their corresponding ids in the hash table. Finally, we will extract the ids from the hash table, sort them, and construct the resulting array.