# Merge Two 2D Arrays by Summing Values
**Difficulty:** EASY
[External](https://leetcode.com/problems/merge-two-2d-arrays-by-summing-values)
Canonical: https://scaleengineer.com/dsa/problems/merge-two-2d-arrays-by-summing-values
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, Hash Table
---
## Problem
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.

# Approaches
## Using a TreeMap for Aggregation and Sorting
This approach uses a `TreeMap` to aggregate the values for each ID. A `TreeMap` is a sorted map data structure that maintains its entries in ascending order of keys. We can iterate through both input arrays and populate the `TreeMap`, using the ID as the key and the sum of values as the value. The `TreeMap` naturally handles the sorting requirement, making the final conversion to a sorted 2D array straightforward.
**Time:** O((N + M) * log(K)), where N and M are the lengths of the input arrays and K is the number of unique IDs (K <= N + M). Each insertion/update operation in a `TreeMap` takes O(log K) time. · **Space:** O(N + M), where N and M are the lengths of `nums1` and `nums2` respectively. This space is required to store the entries in the `TreeMap` and the resulting list.
**Pros:** The logic is straightforward and easy to implement.; The use of `TreeMap` automatically handles the sorting of IDs, simplifying the code.; This approach would work correctly even if the input arrays were not sorted.
**Cons:** Less efficient in terms of time complexity compared to the two-pointer approach due to the logarithmic cost of map operations.; It does not leverage the pre-sorted nature of the input arrays, which is a key property of the problem.
### Explanation
The core idea is to use a data structure that can both store key-value pairs and keep them sorted by the key. A `TreeMap` in Java is perfect for this. 

1.  We first declare a `TreeMap<Integer, Integer>`.
2.  We iterate through `nums1` and put each `[id, value]` pair into the map.
3.  Then, we iterate through `nums2`. For each `[id, value]` pair, we update the map. The `getOrDefault` method is particularly useful here. `map.put(id, map.getOrDefault(id, 0) + value)` will fetch the current value for the given `id` (or 0 if it's not present), add the new value to it, and put the result back into the map. This correctly handles both new IDs and existing IDs.
4.  Because we used a `TreeMap`, the entries are already sorted by ID. The final step is to iterate through the map's entries and construct the final 2D array.

```java
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

class Solution {
    public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
        Map<Integer, Integer> map = new TreeMap<>();

        // Process the first array
        for (int[] item : nums1) {
            map.put(item[0], item[1]);
        }

        // Process the second array, summing values for common IDs
        for (int[] item : nums2) {
            map.put(item[0], map.getOrDefault(item[0], 0) + item[1]);
        }

        // Convert the map to the result 2D array
        List<int[]> resultList = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            resultList.add(new int[]{entry.getKey(), entry.getValue()});
        }

        return resultList.toArray(new int[resultList.size()][]);
    }
}
```
### Algorithm
- Initialize a `TreeMap<Integer, Integer>` to store ID-to-value mappings. A `TreeMap` is used because it automatically keeps the keys (IDs) in sorted order.
- Iterate through the first array, `nums1`. For each pair `[id, val]`, add it to the map.
- Iterate through the second array, `nums2`. For each pair `[id, val]`, update the map. If the ID already exists, add the new value to the existing value. If it doesn't exist, insert it. The `map.put(id, map.getOrDefault(id, 0) + val)` operation handles both cases efficiently.
- After processing both arrays, the `TreeMap` will contain all the unique IDs from both arrays, sorted, with their corresponding summed values.
- Create a new list to store the result in the required `int[]` format.
- Iterate through the entries of the `TreeMap` and add each `[id, value]` pair to the result list.
- Convert the result list to a 2D integer array and return it.

## Two Pointers Approach
This approach leverages the fact that both input arrays are already sorted by ID. We can use a two-pointer technique, similar to the merge step in merge sort, to build the final merged array in a single pass. This is the most efficient method as it avoids the overhead of map data structures or explicit sorting.
**Time:** O(N + M), where N and M are the lengths of the input arrays. This is because we iterate through both arrays with two pointers in a single pass. · **Space:** O(N + M), where N and M are the lengths of `nums1` and `nums2`. This space is used for the result list. If the output array is not considered extra space, the complexity is O(1).
**Pros:** Optimal time complexity, as it processes each element from both arrays only once.; Efficiently uses the sorted property of the input arrays.; Low overhead compared to map-based solutions.
**Cons:** This approach relies heavily on the input arrays being sorted. It would not work correctly for unsorted inputs without a pre-sorting step.
### Explanation
By maintaining a pointer for each array, we can iterate through them simultaneously. We compare the IDs at the current pointers and decide which element to add to our result list. This ensures that the result list is built in sorted order from the beginning.

1.  We start with pointers `i = 0` for `nums1` and `j = 0` for `nums2`.
2.  We compare `id1 = nums1[i][0]` and `id2 = nums2[j][0]`.
3.  If they are equal, we've found a common ID. We sum their values and add the new pair to our result. Since we've processed both elements, we advance both pointers `i` and `j`.
4.  If `id1` is smaller, it means `id1` comes first in the sorted merged list. We add the pair from `nums1` to our result and advance only pointer `i` to consider the next element in `nums1`.
5.  If `id2` is smaller, we do the opposite: add the pair from `nums2` and advance `j`.
6.  This process continues until we exhaust one of the arrays. Any remaining elements in the other array must have IDs greater than all processed IDs, so we can simply append them to the result.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
        List<int[]> result = new ArrayList<>();
        int i = 0, j = 0;
        int n1 = nums1.length;
        int n2 = nums2.length;

        while (i < n1 && j < n2) {
            if (nums1[i][0] == nums2[j][0]) {
                result.add(new int[]{nums1[i][0], nums1[i][1] + nums2[j][1]});
                i++;
                j++;
            } else if (nums1[i][0] < nums2[j][0]) {
                result.add(nums1[i]);
                i++;
            } else {
                result.add(nums2[j]);
                j++;
            }
        }

        // Add remaining elements from nums1
        while (i < n1) {
            result.add(nums1[i]);
            i++;
        }

        // Add remaining elements from nums2
        while (j < n2) {
            result.add(nums2[j]);
            j++;
        }

        return result.toArray(new int[result.size()][]);
    }
}
```
### Algorithm
- Initialize two pointers, `i` for `nums1` and `j` for `nums2`, both starting at `0`.
- Initialize an empty list, `result`, to store the merged `[id, value]` pairs.
- Loop while both pointers `i` and `j` are within the bounds of their respective arrays.
- In each iteration, compare `nums1[i][0]` and `nums2[j][0]`:
  - If `nums1[i][0] == nums2[j][0]`: The IDs are the same. Add a new entry `[id, sum_of_values]` to the `result` list. Increment both `i` and `j`.
  - If `nums1[i][0] < nums2[j][0]`: The ID from `nums1` is smaller. Add the entry `nums1[i]` to the `result` list. Increment only `i`.
  - If `nums1[i][0] > nums2[j][0]`: The ID from `nums2` is smaller. Add the entry `nums2[j]` to the `result` list. Increment only `j`.
- After the main loop, one of the arrays might have remaining elements. Append all remaining elements from `nums1` (if any) to the `result`.
- Append all remaining elements from `nums2` (if any) to the `result`.
- Convert the `result` list to a 2D array and return it.

# Solutions
### Java

```java
class Solution { public int [][] mergeArrays ( int [][] nums1 , int [][] nums2 ) { int [] cnt = new int [ 1001 ]; for ( var x : nums1 ) { cnt [ x [ 0 ]] += x [ 1 ]; } for ( var x : nums2 ) { cnt [ x [ 0 ]] += x [ 1 ]; } int n = 0 ; for ( int i = 0 ; i < 1001 ; ++ i ) { if ( cnt [ i ] > 0 ) { ++ n ; } } int [][] ans = new int [ n ][ 2 ]; for ( int i = 0 , j = 0 ; i < 1001 ; ++ i ) { if ( cnt [ i ] > 0 ) { ans [ j ++] = new int [] { i , cnt [ i ]}; } } return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < vector < int >> mergeArrays ( vector < vector < int >>& nums1 , vector < vector < int >>& nums2 ) { int cnt [ 1001 ]{}; for ( auto & x : nums1 ) { cnt [ x [ 0 ]] += x [ 1 ]; } for ( auto & x : nums2 ) { cnt [ x [ 0 ]] += x [ 1 ]; } vector < vector < int >> ans ; for ( int i = 0 ; i < 1001 ; ++ i ) { if ( cnt [ i ]) { ans . push_back ({ i , cnt [ i ]}); } } return ans ; } };
```

### Python

```python
class Solution : def mergeArrays ( self , nums1 : List [ List [ int ]], nums2 : List [ List [ int ]] ) -> List [ List [ int ]]: cnt = Counter () for i , v in nums1 + nums2 : cnt [ i ] += v return sorted ( cnt . items ())
```