Watch 10 video solutions for Merge Two 2D Arrays by Summing Values, a easy level problem involving Array, Hash Table, Two Pointers. This walkthrough by NeetCodeIO has 6,006 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |