Leetcode 2570: Merge Two 2D Arrays by Summing Values
You are given two 2D integer arrays nums1 and nums2. Each element in nums1 and nums2 is an array of two integers: an id and a value. The arrays are sorted in ascending order by the id. Your task is to merge the two arrays into a single array, sorted by id. Each id should appear only once, and if an id appears in both arrays, its value should be the sum of the values from both arrays. If an id is present in only one array, its value remains as it is.
Problem
Approach
Steps
Complexity
Input: The input consists of two arrays nums1 and nums2. Each array contains pairs of integers, where each pair represents an id and its corresponding value.
Example: For example, nums1 = [[1, 3], [2, 5], [4, 7]] and nums2 = [[1, 4], [3, 2], [4, 3]].
Constraints:
• 1 <= nums1.length, nums2.length <= 200
• nums1[i].length == nums2[i].length == 2
• 1 <= idi, vali <= 1000
• Both arrays contain unique ids.
• Both arrays are sorted in strictly ascending order by id.
Output: Return the merged array where each id appears only once. If an id appears in both arrays, its value should be the sum of the values in both arrays. The array should be sorted in ascending order by id.
Example: For nums1 = [[1, 3], [2, 5], [4, 7]] and nums2 = [[1, 4], [3, 2], [4, 3]], the output is [[1, 7], [2, 5], [3, 2], [4, 10]].
Constraints:
• The output should be a merged array sorted by id, with each id appearing only once.
Goal: To merge two arrays of ids and values into one array, summing the values for duplicate ids and sorting the array by id.
Steps:
• 1. Use a map to store the id as the key and the sum of values as the value.
• 2. Traverse both nums1 and nums2, adding the values to the map based on the ids.
• 3. Convert the map to a vector of pairs, where each pair contains an id and its corresponding summed value.
• 4. Return the resulting vector sorted by id.
Goal: The input arrays nums1 and nums2 are both sorted in ascending order by id, and each array contains unique ids. The arrays can each contain up to 200 elements, and each id and value is between 1 and 1000.
Steps:
• 1 <= nums1.length, nums2.length <= 200
• nums1[i].length == nums2[i].length == 2
• 1 <= idi, vali <= 1000
• Both arrays contain unique ids.
• Both arrays are sorted in strictly ascending order by id.
Assumptions:
• The input arrays nums1 and nums2 are sorted in strictly ascending order by id.
• The arrays will not contain duplicate ids within each array.
• Input: For nums1 = [[1, 3], [2, 5], [4, 7]] and nums2 = [[1, 4], [3, 2], [4, 3]], the output is [[1, 7], [2, 5], [3, 2], [4, 10]].
• Explanation: In this case, the values for ids 1 and 4 are added because they appear in both arrays. The other ids are included as they are.
• Input: For nums1 = [[3, 5], [7, 6]] and nums2 = [[2, 4], [5, 8]], the output is [[2, 4], [3, 5], [5, 8], [7, 6]].
• Explanation: No ids overlap between the two arrays, so the result is a simple combination of the two arrays sorted by id.
Approach: The approach is based on using a map to accumulate the values for each unique id and then sorting the result by id.
Observations:
• The arrays are sorted by id, so we can efficiently traverse them and merge the values for each id.
• Use a map to store the sum of values for each id, then sort the results before returning.
Steps:
• 1. Initialize a map to store ids and their summed values.
• 2. Traverse nums1 and nums2, updating the map with the values for each id.
• 3. Convert the map into a vector of pairs and sort by id.
• 4. Return the sorted vector.
Empty Inputs:
• Empty arrays are not possible, as the problem guarantees each array will have at least one element.
Large Inputs:
• Ensure that the solution can handle arrays of length up to 200 efficiently.
Special Values:
• The values can range from 1 to 1000, and ids are unique in each array.
Constraints:
• Both arrays are sorted, which helps with efficient merging.
vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
map<int,int> m;
for(auto& itr : nums1){
m[itr[0]] += itr[1];
}
for(auto& itr : nums2){
m[itr[0]] += itr[1];
}
vector<vector<int> > v;
for(auto& itr : m){
v.push_back({itr.first,itr.second});
}
return v;
}
1 : Function Declaration
vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
Declares the function `mergeArrays` that takes two 2D vectors `nums1` and `nums2` and returns a 2D vector containing the merged and summed pairs.
2 : Map Initialization
map<int,int> m;
Declares a map `m` that will store key-value pairs, where the key is an integer and the value is the sum of values from the input arrays.
3 : Loop
for(auto& itr : nums1){
Starts a loop to iterate over each element (pair) in the first input array `nums1`.
4 : Map Insertion
m[itr[0]] += itr[1];
For each pair, the first element (`itr[0]`) is used as the key, and the second element (`itr[1]`) is added to the corresponding value in the map.
5 : Loop
for(auto& itr : nums2){
Starts a loop to iterate over each element (pair) in the second input array `nums2`.
6 : Map Insertion
m[itr[0]] += itr[1];
For each pair in `nums2`, the value is added to the existing sum in the map for the key `itr[0]`.
7 : Vector Initialization
vector<vector<int> > v;
Declares a 2D vector `v` which will store the final result.
8 : Loop
for(auto& itr : m){
Starts a loop to iterate over each key-value pair in the map `m`.
9 : Vector Insertion
v.push_back({itr.first,itr.second});
For each key-value pair in the map, a new pair is pushed into the vector `v`.
10 : Return Statement
return v;
Returns the final 2D vector `v` containing the merged and summed pairs from `nums1` and `nums2`.
Best Case: O(n log n), where n is the number of unique ids in the final result.
Average Case: O(n log n), due to sorting the result array.
Worst Case: O(n log n), where n is the total number of ids from both arrays.
Description: The time complexity is dominated by the sorting step, which takes O(n log n).
Best Case: O(n), where n is the number of unique ids.
Worst Case: O(n), where n is the total number of ids from both arrays.
Description: The space complexity is determined by the map and the result vector, both of which store ids and their values.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus