Difficulty: Easy | Acceptance: 81.70% | Paid: No Topics: Array, Hash Table, Two Pointers
You are given two 2D integer arrays nums1 and nums2.
nums1[i] = [idi, vali] indicates that the value vali is associated with the id idi. nums2[j] = [idj, valj] indicates that the value valj is associated with the id idj.
Each array is strictly increasing in id, meaning that the ids in each array are distinct and sorted in ascending order.
Merge the two arrays into one array that is sorted in ascending order by id, and if an id appears in both arrays, sum the values associated with that id. The resulting array should only contain unique ids.
Return the resulting array.
- Examples
- Constraints
- Hash Map Approach
- Two Pointers Approach
- Brute Force Approach
Examples
Example 1
Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,6]]
Output: [[1,6],[2,3],[3,2],[4,11]]
Explanation: The id 1 appears in both arrays with values 2 and 4, so we sum them to get 6.
The id 2 appears only in nums1 with value 3. The id 3 appears only in nums2 with value 2.
The id 4 appears in both arrays with values 5 and 6, so we sum them to get 11.
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 all ids from both arrays in sorted order.
Constraints
1 <= nums1.length, nums2.length <= 200
nums1[i].length == nums2[j].length == 2
1 <= idi, idj <= 1000
0 <= vali, valj <= 10⁶
nums1 and nums2 are strictly increasing in id.
Hash Map Approach
Intuition Use a hash map to accumulate values for each unique ID from both arrays, then sort the keys to produce the final result.
Steps
- Create a hash map to store ID to value mappings
- Iterate through nums1 and add each ID-value pair to the map
- Iterate through nums2 and add each ID-value pair to the map (summing if ID exists)
- Sort the map keys and construct the result array
class Solution:
def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
from collections import defaultdict
counter = defaultdict(int)
for id, val in nums1:
counter[id] += val
for id, val in nums2:
counter[id] += val
return [[id, counter[id]] for id in sorted(counter.keys())]
Complexity
- Time: O((n + m) log(n + m)) where n and m are lengths of input arrays
- Space: O(n + m) for the hash map
- Notes: Using TreeMap in Java or map in C++ automatically handles sorting
Two Pointers Approach
Intuition Since both arrays are already sorted by ID, use two pointers to merge them in a single pass, similar to the merge step in merge sort.
Steps
- Initialize two pointers at the start of both arrays
- Compare IDs at both pointers, add the smaller one to result
- If IDs are equal, sum the values and advance both pointers
- Add remaining elements from whichever array has leftovers
class Solution:
def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
i, j = 0, 0
result = []
while i < len(nums1) and j < len(nums2):
if nums1[i][0] < nums2[j][0]:
result.append(nums1[i])
i += 1
elif nums1[i][0] > nums2[j][0]:
result.append(nums2[j])
j += 1
else:
result.append([nums1[i][0], nums1[i][1] + nums2[j][1]])
i += 1
j += 1
while i < len(nums1):
result.append(nums1[i])
i += 1
while j < len(nums2):
result.append(nums2[j])
j += 1
return result
Complexity
- Time: O(n + m) where n and m are lengths of input arrays
- Space: O(n + m) for the result array
- Notes: Optimal approach that leverages the sorted input property
Brute Force Approach
Intuition Combine both arrays, sort by ID, then iterate through to sum values for consecutive duplicate IDs.
Steps
- Concatenate both arrays into one combined array
- Sort the combined array by ID
- Iterate through sorted array, summing values for consecutive same IDs
- Build result with unique IDs and summed values
class Solution:
def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
combined = nums1 + nums2
combined.sort(key=lambda x: x[0])
result = []
for id, val in combined:
if result and result[-1][0] == id:
result[-1][1] += val
else:
result.append([id, val])
return result
Complexity
- Time: O((n + m) log(n + m)) due to sorting
- Space: O(n + m) for the combined array and result
- Notes: Simpler to implement but less efficient than two pointers approach