Problem Informations

Problem Index: 2570
Problem Link: Merge Two 2D Arrays by Summing Values
Topics: Array, Hash Table, Two Pointers

Problem Description

You are given two 2D integer arrays nums1 and nums2.

$nums1[i] = [id_i, val_i]$ indicate that the number with the id $id_i$ has a value equal to $val_i$.
$nums2[i] = [id_i, val_i]$ indicate that the number with the id $id_i$ has a value equal to $val_i$.

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 \leq nums1.length, nums2.length \leq 200$
$nums1[i].length == nums2[j].length == 2$
$1 \leq id_i, val_i \leq 1000$
Both arrays contain unique ids.
Both arrays are in strictly ascending order by id.

Intuition

The problem requires merging two separate 2D arrays, each consisting of id-value pairs, such that the resultant array includes all unique ids in ascending order and aggregates values for ids present in both arrays. The solution should efficiently account for the constraints that ids are unique within each array and both arrays are pre-sorted, allowing the use of a two-pointer technique to traverse each array concurrently.

Approach

To solve the problem, we implement a two-pointer strategy to navigate both 2D arrays simultaneously. By exploiting the characteristics of sorted arrays and unique ids, we can efficiently merge them with the following steps:

Initialization: Define an empty result array to store the merged ids and values. Initialize indices idx1 and idx2 to track positions in nums1 and nums2, respectively.
Iterative Merging: Use a loop to traverse both arrays until all elements are accounted for:
- If pointer idx1 reaches the end of nums1, append the remaining elements from nums2 to the result since nums2 is inherently sorted.
- Conversely, if pointer idx2 reaches the end of nums2, append the remaining elements from nums1 for the same reason.
- Compare the current ids pointed by idx1 and idx2. Append the smaller id-value pair to the result, advancing the respective pointer.
- If both ids are identical, calculate the sum of their values, append the id and the computed sum to the result, and move both pointers forward.
Completion: Once the loop finishes, the result contains all unique ids with their respective values aggregated and sorted in ascending order.

By utilizing these steps effectively, the algorithm achieves an optimal merging of the two arrays by preserving order and ensuring all conditions specified in the problem statement are met.

Code

C++

class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        vector<vector<int>> result; // Resultant array to store the merged result
        int len1 = nums1.size(), len2 = nums2.size();
        int idx1 = 0, idx2 = 0;
        
        // Traverse both arrays while elements remain in either of the arrays
        while (idx1 < len1 || idx2 < len2) {
            if (idx1 == len1) {
                // If nums1 is exhausted, take elements from nums2
                result.push_back(nums2[idx2++]);
            } else if (idx2 == len2) {
                // If nums2 is exhausted, take elements from nums1
                result.push_back(nums1[idx1++]);
            } else if (nums1[idx1][0] < nums2[idx2][0]) {
                // If current id in nums1 is less, take this id-value pair
                result.push_back(nums1[idx1++]);
            } else if (nums2[idx2][0] < nums1[idx1][0]) {
                // If current id in nums2 is less, take this id-value pair
                result.push_back(nums2[idx2++]);
            } else {
                // If ids are equal, merge the values
                result.push_back(nums1[idx1++]);
                result.back()[1] += nums2[idx2++][1]; // Sum the values
            }
        }
        
        return result; // Return the merged array
    }
};

Python

class Solution:
    def mergeArrays(self, nums1, nums2):
        result = []  # Resultant array to store the merged result
        len1 = len(nums1)
        len2 = len(nums2)
        idx1 = 0
        idx2 = 0
        
        # Traverse both arrays while elements remain in either of the arrays
        while idx1 < len1 or idx2 < len2:
            if idx1 == len1:
                # If nums1 is exhausted, take elements from nums2
                result.append(nums2[idx2])
                idx2 += 1
            elif idx2 == len2:
                # If nums2 is exhausted, take elements from nums1
                result.append(nums1[idx1])
                idx1 += 1
            elif nums1[idx1][0] < nums2[idx2][0]:
                # If current id in nums1 is less, take this id-value pair
                result.append(nums1[idx1])
                idx1 += 1
            elif nums2[idx2][0] < nums1[idx1][0]:
                # If current id in nums2 is less, take this id-value pair
                result.append(nums2[idx2])
                idx2 += 1
            else:
                # If ids are equal, merge the values
                result.append(nums1[idx1])
                result[-1][1] += nums2[idx2][1]  # Sum the values
                idx1 += 1
                idx2 += 1
        
        return result  # Return the merged array

Complexity

Time complexity: The given algorithm traverses both arrays nums1 and nums2 exactly once. Each element of either nums1 or nums2 is processed exactly once, resulting in a time complexity of $O(n + m)$, where $n$ is the length of nums1 and $m$ is the length of nums2.
Space complexity: The space used by the algorithm is proportional to the number of unique ids present in either nums1 or nums2. In the worst case, all ids are unique between the two arrays, which means that the space required for the result array will be proportional to the sum of the lengths of nums1 and nums2. Thus, the space complexity is $O(n + m)$.

CS Note
中

Leetcode 2570. Merge Two 2D Arrays by Summing Values