algoadvance

Leetcode 2570. Merge Two 2D Arrays by Summing Values

Problem Statement

Given two 2D integer arrays nums1 and nums2, each array contains elements in the form [id, val] where:

• id is a unique identifier,
• val is the value associated with the identifier.

Merge these two arrays such that the resulting array contains unique ids and sums the val for any id that appears in both arrays. The resulting array should be sorted by id.

Example:

Input: nums1 = [[1, 2], [2, 3], [4, 5]], nums2 = [[1, 3], [2, 1], [3, 2]]
Output: [[1, 5], [2, 4], [3, 2], [4, 5]]

Clarifying Questions

1. Input Validation: Can we assume that inputs are always well-formed (i.e., no negative ids, no missing id or val, etc.)?
2. Ordering of ids: Should the input lists be considered pre-sorted, or can they be unordered? (Clarification: In the resulting array, ids must be sorted.)

Strategy

1. Use a Map: Utilize an unordered map (or map) to store the id as key and the val as the cumulative value.
2. Iterate and Aggregate: Iterate over both arrays, updating the map’s values by summing up for the same ids.
3. Convert to Vector: Convert the map back to a vector of pairs.
4. Sort the Result: Sort the resulting vector by id.

Code

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
    unordered_map<int, int> idMap;

    // Aggregate values from nums1
    for (const auto& pair : nums1) {
        idMap[pair[0]] += pair[1];
    }

    // Aggregate values from nums2
    for (const auto& pair : nums2) {
        idMap[pair[0]] += pair[1];
    }

    vector<vector<int>> result;
    for (const auto& entry : idMap) {
        result.push_back({entry.first, entry.second});
    }

    // Sort by id
    sort(result.begin(), result.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });

    return result;
}

Time Complexity

• Insertion into Map: O(n + m) where n is the length of nums1 and m is the length of nums2.
• Conversion to Vector: O(k) where k is the number of unique ids.
• Sorting: O(k log k), where k is the number of unique ids (because it is sorted by id).
• Total Time Complexity: O(n + m + k log k)

This solution efficiently aggregates and sorts the values, making it suitable for this kind of merging task. By using an unordered map, we ensure an average case constant time complexity for insertions and lookups.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?