• Leetcode POTDs

Problem 2570 Merge Two 2D Arrays by Summing Values

Problem Statement

Link - Problem 2570

Question

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:

• Only ids that appear in at least one of the two arrays should be included in the resulting array.
• Each id should be included only once and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays, then assume its value in that array to be 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 <= 200
• nums1[i].length == nums2[j].length == 2
• 1 <= idi, vali <= 1000
• Both arrays contain unique ids.
• Both arrays are in strictly ascending order by id.

Solution

class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        map<int,int>mp;
        for(const auto& v: nums1){
            mp[v[0]] = v[1];
        }
        for(const auto& v:nums2){
            if(mp.find(v[0])==mp.end()){
                mp[v[0]] = v[1];
            }
            else{
                mp[v[0]] += v[1];
            }
        }
        vector<vector<int>>ans;
        for(auto i:mp){
            ans.push_back({i.first,i.second});
        }
        return ans;
    }
};

Complexity Analysis

| Algorithm        | Time Complexity     | Space Complexity |
| ---------------- | ------------------- | ---------------- |
| Hash Map Merging | O(max(nlogn,mlogm)) | O(n + m)         |

Explanation

Intial Thoughts

The problem involves merging two sorted 2D arrays based on their ids. The first step is to think about how to efficiently combine the information from both arrays, considering that each id appears only once in each array but may appear in either or both arrays. We need to consider a data structure that can handle unique ids and allow for the easy combination of values for matching ids. Using an analogy like a library catalog system can help, where each id is like a book title and the value is like the number of copies available. The goal is to merge the catalogs from two libraries. Another key point is to consider whether to iterate through both arrays simultaneously or process them separately. Additionally, considering the constraints on the input sizes and the range of ids and values can help in determining the feasibility of different approaches.

Intuitive Analysis

One intuitive way to approach this problem is to think of the process as collecting all the information from both arrays into a single, unified view, allowing for easy lookup and combination of matching ids. This can be likened to creating a ‘master catalog’ where each id and its total value are recorded. It’s intuitive to start with one array and then add information from the second array, updating the total value for each id as we go. A key realization is that since the arrays are sorted and contain unique ids, we can efficiently build our master catalog by iterating through both arrays and directly updating the catalog when we encounter a new or existing id. It’s also important to recognize the role of a data structure like a map in this process, as it naturally fits the need to look up, add, and update ids and their values efficiently.

1. Intuition

• The problem requires merging two 2D arrays into one, with each id appearing only once and its value being the sum of the values in the two arrays.
• Since the arrays are sorted in ascending order by id, we can use a data structure that preserves this order.
• A map can be used to store the ids and their corresponding values, allowing for efficient lookups and updates.
• We need to iterate through both arrays, updating the map with the sum of values for each id.
• After updating the map, we can create the resulting array by iterating through the map and adding each id-value pair.
• This approach ensures that the resulting array is sorted in ascending order by id and that each id appears only once.
• The time complexity of this approach is O(n + m), where n and m are the lengths of the input arrays.

2. Implementation

• We start by creating an empty map mp to store the ids and their corresponding values.
• We iterate through the first array nums1 and add each id-value pair to the map mp using mp[v[0]] = v[1].
• We then iterate through the second array nums2 and update the map mp with the sum of values for each id using mp[v[0]] += v[1].
• If an id is not found in the map, we add it with its value using mp[v[0]] = v[1].
• After updating the map, we create the resulting array ans by iterating through the map and adding each id-value pair using ans.push_back({i.first, i.second}).
• Finally, we return the resulting array ans.
• The use of a map allows for efficient lookups and updates, making the implementation concise and efficient.

Complexity Analysis

Time Complexity:

• The algorithm iterates over nums1 and nums2 performing map operations for each element. Since we’re using an ordered map (not an unordered_map), each insertion and lookup operation takes O(log k) time where k is the current size of the map.
• For nums1 with size n: Each element requires a map insertion taking O(log n), totaling O(n log n)
• For nums2 with size m: Each element requires a map lookup and possible insertion/update taking O(log(n+m)), totaling O(m log(n+m))
• Therefore, the overall time complexity is O(max(n log n, m log m))
• This higher complexity compared to O(n + m) is due to the ordered nature of the map operations, which are necessary to maintain the sorted order requirement of the output.

Space Complexity:

• The algorithm uses a map to store the merged key-value pairs, resulting in a space complexity of O(n + m). This is because in the worst case, every key from nums1 and nums2 could be unique, requiring a separate entry in the map.
• The use of a hash map as the data structure impacts the space complexity, as it allows for efficient storage and lookup of key-value pairs. The map’s size is directly proportional to the number of unique keys in the input arrays.
• The space complexity of O(n + m) is justified because the algorithm’s memory usage grows linearly with the size of the inputs. In the worst case, the map could store up to n + m key-value pairs, resulting in a space complexity of O(n + m).

Footnote

This question is rated as Easy difficulty.

Hints

Use a dictionary/hash map to keep track of the indices and their sum values.

Similar Questions: