# Merge Similar Items
**Difficulty:** EASY
[External](https://leetcode.com/problems/merge-similar-items)
Canonical: https://scaleengineer.com/dsa/problems/merge-similar-items
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Ordered Set
---
## Problem
You are given two 2D integer arrays, `items1` and `items2`, representing two sets of items. Each array `items` has the following properties:

* `items[i] = [valuei, weighti]` where `valuei` represents the **value** and `weighti` represents the **weight** of the `ith` item.
* The value of each item in `items` is **unique**.

Return _a 2D integer array_ `ret` _where_ `ret[i] = [valuei, weighti]`_,_ _with_ `weighti` _being the **sum of weights** of all items with value_ `valuei`.

**Note:** `ret` should be returned in **ascending** order by value.

**Example 1:**

**Input:** items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]
**Output:** [[1,6],[3,9],[4,5]]
**Explanation:** 
The item with value = 1 occurs in items1 with weight = 1 and in items2 with weight = 5, total weight = 1 + 5 = 6.
The item with value = 3 occurs in items1 with weight = 8 and in items2 with weight = 1, total weight = 8 + 1 = 9.
The item with value = 4 occurs in items1 with weight = 5, total weight = 5.  
Therefore, we return [[1,6],[3,9],[4,5]].

**Example 2:**

**Input:** items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[3,2],[1,3]]
**Output:** [[1,4],[2,4],[3,4]]
**Explanation:** 
The item with value = 1 occurs in items1 with weight = 1 and in items2 with weight = 3, total weight = 1 + 3 = 4.
The item with value = 2 occurs in items1 with weight = 3 and in items2 with weight = 1, total weight = 3 + 1 = 4.
The item with value = 3 occurs in items1 with weight = 2 and in items2 with weight = 2, total weight = 2 + 2 = 4.
Therefore, we return [[1,4],[2,4],[3,4]].

**Example 3:**

**Input:** items1 = [[1,3],[2,2]], items2 = [[7,1],[2,2],[1,4]]
**Output:** [[1,7],[2,4],[7,1]]
**Explanation:**
The item with value = 1 occurs in items1 with weight = 3 and in items2 with weight = 4, total weight = 3 + 4 = 7. 
The item with value = 2 occurs in items1 with weight = 2 and in items2 with weight = 2, total weight = 2 + 2 = 4. 
The item with value = 7 occurs in items2 with weight = 1, total weight = 1.
Therefore, we return [[1,7],[2,4],[7,1]].

**Constraints:**

* `1 <= items1.length, items2.length <= 1000`
* `items1[i].length == items2[i].length == 2`
* `1 <= valuei, weighti <= 1000`
* Each `valuei` in `items1` is **unique**.
* Each `valuei` in `items2` is **unique**.

# Approaches
## Brute Force: Concatenate and Sort
This approach involves first combining the two lists of items into a single list. Then, this combined list is sorted based on the item values. Finally, we iterate through the sorted list to merge items with the same value by summing their weights.
**Time:** O((N + M) * log(N + M)), where N is the length of `items1` and M is the length of `items2`. The dominant operation is sorting the combined list of size N + M. · **Space:** O(N + M), where N is the length of `items1` and M is the length of `items2`. This space is required to store the combined list and the result list.
**Pros:** Relatively simple to understand and implement.; Does not rely on specialized data structures like hash maps.
**Cons:** The sorting step makes it less efficient than other possible solutions.; Requires extra space proportional to the total number of items to hold the combined list.
### Explanation
The core idea is to gather all items together, sort them, and then process them in order. This is a straightforward way to group similar items next to each other, making the merging process a simple linear scan after the sort.

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

class Solution {
    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
        List<int[]> combined = new ArrayList<>();
        for (int[] item : items1) {
            combined.add(item);
        }
        for (int[] item : items2) {
            combined.add(item);
        }

        // Sort the combined list by value
        Collections.sort(combined, Comparator.comparingInt(a -> a[0]));

        List<List<Integer>> ret = new ArrayList<>();
        if (combined.isEmpty()) {
            return ret;
        }

        int currentVal = combined.get(0)[0];
        int currentWeight = combined.get(0)[1];

        for (int i = 1; i < combined.size(); i++) {
            int[] item = combined.get(i);
            if (item[0] == currentVal) {
                currentWeight += item[1];
            } else {
                List<Integer> mergedItem = new ArrayList<>();
                mergedItem.add(currentVal);
                mergedItem.add(currentWeight);
                ret.add(mergedItem);
                
                currentVal = item[0];
                currentWeight = item[1];
            }
        }
        
        // Add the last merged item
        List<Integer> lastMergedItem = new ArrayList<>();
        lastMergedItem.add(currentVal);
        lastMergedItem.add(currentWeight);
        ret.add(lastMergedItem);

        return ret;
    }
}
```
### Algorithm
- Create a new list, `combinedItems`.
- Add all items from `items1` and `items2` into `combinedItems`.
- Sort `combinedItems` in ascending order based on the `value` (the first element of each sub-array).
- Initialize an empty result list, `ret`.
- Iterate through the sorted `combinedItems` list. If the list is not empty, initialize `currentVal` and `currentWeight` with the first item's details.
- For subsequent items, if the `value` is the same as `currentVal`, add its `weight` to `currentWeight`.
- If the `value` is different, add the `[currentVal, currentWeight]` pair to `ret`, and then update `currentVal` and `currentWeight` to the current item's details.
- After the loop finishes, make sure to add the last processed group of items to `ret`.
- Return `ret`.

## Using a Sorted Map (TreeMap)
A more efficient approach uses a map to store the sum of weights for each unique value. A `TreeMap` is specifically chosen because it automatically keeps the entries sorted by key (the item's value). This eliminates the need for a separate sorting step at the end.
**Time:** O((N + M) * logK), where N and M are the lengths of `items1` and `items2`, and K is the number of unique items. Each insertion or update in a `TreeMap` takes `O(logK)` time. · **Space:** O(K), where K is the number of unique items. This space is used to store the K unique items in the `TreeMap` and the result list.
**Pros:** More efficient than the brute-force sorting approach.; The code is clean and concise.; Handles the sorting requirement elegantly by the nature of the `TreeMap`.
**Cons:** Has a logarithmic time complexity factor for each item processed, which is slower than a linear-time approach if one is possible.; The overhead of maintaining a balanced binary tree can make it slightly slower in practice than a `HashMap` followed by a sort, though the asymptotic complexity is similar.
### Explanation
We can iterate through both input arrays and use a map to aggregate weights for each value. The key of the map will be the item's `value`, and the value of the map will be the total `weight`. By using a `TreeMap`, the keys (values) are maintained in sorted order automatically, which simplifies the final step of creating the sorted output list.

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

class Solution {
    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
        Map<Integer, Integer> map = new TreeMap<>();

        // Process items1
        for (int[] item : items1) {
            int value = item[0];
            int weight = item[1];
            map.put(value, map.getOrDefault(value, 0) + weight);
        }

        // Process items2
        for (int[] item : items2) {
            int value = item[0];
            int weight = item[1];
            map.put(value, map.getOrDefault(value, 0) + weight);
        }

        // Convert map to the result list format
        List<List<Integer>> ret = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            List<Integer> item = new ArrayList<>();
            item.add(entry.getKey());
            item.add(entry.getValue());
            ret.add(item);
        }

        return ret;
    }
}
```
### Algorithm
- Initialize a `TreeMap<Integer, Integer>` called `valueToWeightMap`.
- Iterate through `items1`. For each item `[value, weight]`, update the map: `map.put(value, map.getOrDefault(value, 0) + weight)`.
- Iterate through `items2` and perform the same update operation on the map for each item.
- After processing both lists, the `TreeMap` will contain all unique values as keys and their corresponding total weights as values, already sorted by the key.
- Initialize an empty result list, `ret`.
- Iterate through the entries of the `TreeMap` and add each `[key, value]` pair to the `ret` list.
- Return `ret`.

## Optimal: Array as a Frequency Map
This is the most efficient approach, leveraging the constraint that item values are within a limited range (1 to 1000). We can use a simple array as a direct-access map (or frequency map) to store the total weight for each value. The index of the array corresponds to the item's value.
**Time:** O(N + M + V), where N and M are the lengths of the input arrays, and V is the maximum possible value (1000). This simplifies to linear time complexity as V is a constant. · **Space:** O(V), where V is the maximum possible value (1000). The space for the result list depends on the number of unique items, K, so it's O(K). The dominant factor is O(V).
**Pros:** The most efficient solution with linear time complexity.; Simple implementation without complex data structures.; Low constant factors, making it very fast in practice.
**Cons:** This approach is only feasible because the range of values is small and known beforehand.; It would be impractical or memory-intensive if values could be very large or were not positive integers.
### Explanation
Since the maximum value is 1000, we can create an array of size 1001. `array[i]` will store the sum of weights for items with `value = i`. This approach avoids the overhead of hashing (like in `HashMap`) or maintaining a balanced tree (like in `TreeMap`) and provides O(1) access time for updates. The final result is built by iterating through this array, which naturally produces a list sorted by value.

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

class Solution {
    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
        // Max value is 1000, so we need an array of size 1001 for indices 0-1000.
        int[] weights = new int[1001];

        // Process items1
        for (int[] item : items1) {
            weights[item[0]] += item[1];
        }

        // Process items2
        for (int[] item : items2) {
            weights[item[0]] += item[1];
        }

        List<List<Integer>> ret = new ArrayList<>();
        for (int value = 1; value <= 1000; value++) {
            if (weights[value] > 0) {
                List<Integer> item = new ArrayList<>();
                item.add(value);
                item.add(weights[value]);
                ret.add(item);
            }
        }

        return ret;
    }
}
```
### Algorithm
- Create an integer array `weights` of size 1001 and initialize all its elements to 0.
- Iterate through `items1`. For each item `[value, weight]`, update the array: `weights[value] += weight`.
- Iterate through `items2` and perform the same update: `weights[value] += weight`.
- Initialize an empty result list, `ret`.
- Iterate through the `weights` array from index 1 to 1000.
- If `weights[i]` is greater than 0, it means an item with `value = i` exists. Create a new list `[i, weights[i]]` and add it to `ret`.
- Since we iterate through the array by index, the resulting list `ret` will be automatically sorted by value.
- Return `ret`.

# Solutions
### Java

```java
class Solution {
public
  List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
    int[] cnt = new int[1010];
    for (var x : items1) {
      cnt[x[0]] += x[1];
    }
    for (var x : items2) {
      cnt[x[0]] += x[1];
    }
    List<List<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < cnt.length; ++i) {
      if (cnt[i] > 0) {
        ans.add(List.of(i, cnt[i]));
      }
    }
    return ans;
  }
}

```

### CPP

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

```

### Python

```python
class Solution:
    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]: cnt = Counter() for v, w in chain(items1, items2): cnt[v] += w return sorted(cnt . items())

```