You are given two 2D integer arrays nums1 and nums2.
nums1[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.nums2[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.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, respecting the following conditions:
0.Return the resulting array. The returned array must be sorted in ascending order by id.
Example 1:
Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]] Output: [[1,6],[2,3],[3,2],[4,6]] Explanation: The resulting array contains the following: - id = 1, the value of this id is 2 + 4 = 6. - id = 2, the value of this id is 3. - id = 3, the value of this id is 2. - id = 4, the value of this id is 5 + 1 = 6.
Example 2:
Input: nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]] Output: [[1,3],[2,4],[3,6],[4,3],[5,5]] Explanation: There are no common ids, so we just include each id with its value in the resulting list.
Constraints:
1 <= nums1.length, nums2.length <= 200nums1[i].length == nums2[j].length == 21 <= idi, vali <= 1000This method involves utilizing a hash map (or dictionary) to store the sums of values associated with each id. As you iterate through both arrays, you'll update the map with the sums. After processing both, you can convert the map to the desired output format.
The solution uses a default dictionary to keep track of summed values by id. First, it traverses nums1, updating the dictionary. Then, it does the same for nums2. Finally, it constructs a list of lists from the sorted keys of the dictionary, each containing the id and its corresponding summed value.
Java
C#
Time Complexity: O(n + m), where n is the length of nums1 and m is the length of nums2, as we iterate through both arrays once.
Space Complexity: O(n + m) for the dictionary storing ids and summed values.
Given that both arrays are sorted by id, we can effectively use a two pointers technique to traverse both arrays simultaneously. This allows us to merge them in a single pass by comparing the ids at the current pointer positions.
This C++ solution employs two pointers to traverse both arrays. It compares the ids at current positions and adds the appropriate result to the output. If ids match, their values are summed; otherwise, the entry from the array with the smaller id is added. Remaining elements are added after one array is exhausted.
JavaScript
C
Time Complexity: O(n + m), where n and m are the lengths of the arrays.
Space Complexity: O(1), aside from the output storage.
| Approach | Complexity |
|---|---|
| Using a Hash Map or Dictionary | Time Complexity: O(n + m), where n is the length of nums1 and m is the length of nums2, as we iterate through both arrays once. |
| Two Pointers Technique | Time Complexity: O(n + m), where n and m are the lengths of the arrays. |
Merge Two 2D Arrays by Summing Values - Leetcode 2570 - Python • NeetCodeIO • 4,852 views views
Watch 9 more video solutions →Practice Merge Two 2D Arrays by Summing Values with our built-in code editor and test cases.
Practice on FleetCode