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 <= 1000Problem Overview: You are given two 2D arrays where each element is [id, value]. Both arrays are sorted by id. The goal is to merge them into a single sorted array where matching IDs have their values summed, and unique IDs appear as-is.
Approach 1: Hash Map / Dictionary (O(n + m) time, O(n + m) space)
This approach treats the problem as a frequency aggregation task. Iterate through both arrays and store values in a hash map keyed by id. For each pair, perform a constant-time hash lookup and add the value to the existing total. After processing both arrays, convert the map into a sorted list of [id, value] pairs.
The key insight: hash tables allow fast updates when the same ID appears in both arrays. This makes the logic simple and easy to implement. The tradeoff is extra memory proportional to the number of unique IDs. This solution heavily relies on the properties of a hash table for O(1) average updates.
Approach 2: Two Pointers Technique (O(n + m) time, O(1) extra space)
Since both arrays are already sorted by ID, you can merge them similarly to the merge step of merge sort. Use two pointers, one for each array. Compare the current IDs and append the smaller one to the result. If the IDs match, sum their values and move both pointers forward.
This avoids the extra memory used by a dictionary. Each element is processed exactly once, producing linear time complexity. The approach relies on sequential scanning and pointer movement across sorted data. This is a classic pattern when working with sorted arrays and appears frequently in two pointers problems.
The algorithm continues until one array is exhausted, then appends the remaining elements from the other array. Because the arrays are already sorted, the merged output remains sorted automatically.
Recommended for interviews: The two pointers solution is usually the expected answer. It demonstrates that you recognized the sorted property and avoided unnecessary memory. The hash map solution still shows correct reasoning and is often the fastest to implement during a timed interview. Understanding both approaches is useful when working with array merging problems and data aggregation tasks.
This 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.
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.
C++
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.
We can use a hash table or an array cnt to count the frequency of each number in the two arrays.
Then we enumerate each number in cnt from small to large. If the frequency of a number is greater than 0, we add it to the answer array.
The time complexity is O(n + m), and the space complexity is O(M). Where n and m are the lengths of the two arrays respectively; and M is the maximum value in the two arrays, in this problem, M = 1000.
| 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. |
| Counting + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map / Dictionary | O(n + m) | O(n + m) | General case when simplicity matters and extra memory is acceptable |
| Two Pointers (Sorted Merge) | O(n + m) | O(1) | Best when arrays are already sorted and memory efficiency is required |
Merge Two 2D Arrays by Summing Values - Leetcode 2570 - Python • NeetCodeIO • 6,006 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