'2025/03/02'에 해당되는 글 1건

Leetcode Problem:

• Merge Two 2D Arrays by Summing Values

Summary

• Merge two sorted arrays of integers with unique ids, into one array sorted by id, respecting the conditions that only ids appearing in at least one array should be included and each id should be included only once with its value being the sum of the values of this id in the two arrays.

Approach

• The approach used is to first create a map where the keys are the ids and the values are the sums of the values of each id in the two arrays
• Then, we create a vector of vectors and iterate over the map, pushing back a vector for each key-value pair into the vector.

Complexity

• O(n + m) where n and m are the sizes of the two input arrays, because we are iterating over each element in both arrays once.

Explanation

• The solution starts by creating a map where the keys are the ids and the values are the sums of the values of each id in the two arrays
• This is done by iterating over the first array and adding the value of each id to the corresponding key in the map
• Then, we do the same for the second array
• After that, we create a vector of vectors and iterate over the map, pushing back a vector for each key-value pair into the vector
• This results in a vector of vectors where each inner vector contains an id and its corresponding sum, sorted by id in ascending order.

Solution Code:

class Solution {
public:
    vector> mergeArrays(vector>& nums1, vector>& nums2) {
        map m;
        for(int i = 0 ; i < nums1.size(); i++){
            int id = nums1[i][0];
            int v = nums1[i][1];
            m[id] += v;
        }
        for(int i = 0 ; i < nums2.size(); i++){
            int id = nums2[i][0];
            int v = nums2[i][1];
            m[id] += v;
        }
        vector> ans;
        for (auto iter : m){
            int id = iter.first;
            int v = iter.second;
            ans.push_back({id, v});
        }
        return ans;
    }
};