Merge Similar Items

easy hash map sorting

Problem

You are given two 2D arrays, items1 and items2, where each entry is a pair [value, weight] and every value within a single array is unique. Merge both arrays so that each distinct value appears exactly once, with its weight equal to the sum of the weights it carries across both arrays. Return the merged list as [value, total weight] pairs sorted by value in ascending order.

Inputitems1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]

Output[[1,6],[3,9],[4,5]]

Value 1 appears in both (1 + 5 = 6), value 3 appears in both (8 + 1 = 9), and value 4 appears only once (5). Sorted by value gives [[1,6],[3,9],[4,5]].

items1 as value:weight pairs (comma-separated)

items2 as value:weight pairs (comma-separated)

def merge_similar_items(items1, items2):
    total = {}
    for value, weight in items1 + items2:
        total[value] = total.get(value, 0) + weight
    result = []
    for value in sorted(total):
        result.append([value, total[value]])
    return result

function mergeSimilarItems(items1, items2) {
  const total = new Map();
  for (const [value, weight] of items1.concat(items2)) {
    total.set(value, (total.get(value) || 0) + weight);
  }
  const values = [...total.keys()].sort((a, b) => a - b);
  return values.map(value => [value, total.get(value)]);
}

class Solution {
    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
        Map<Integer, Integer> total = new TreeMap<>();
        for (int[] it : items1) total.merge(it[0], it[1], Integer::sum);
        for (int[] it : items2) total.merge(it[0], it[1], Integer::sum);
        List<List<Integer>> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : total.entrySet())
            result.add(Arrays.asList(e.getKey(), e.getValue()));
        return result;
    }
}

vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
    map<int, int> total;
    for (auto& it : items1) total[it[0]] += it[1];
    for (auto& it : items2) total[it[0]] += it[1];
    vector<vector<int>> result;
    for (auto& [value, weight] : total)
        result.push_back({ value, weight });
    return result;
}

Explanation

The same value can show up in both arrays, and when it does we want its weights added together. A hash map from value to running weight makes that effortless: walk through every pair and do total[value] += weight.

Because each array has unique values on its own, a value contributes at most once per array — so a value appears either once (in a single array) or twice (in both). The map naturally collapses those into a single accumulated weight.

The answer must come out sorted by value, so after accumulating we iterate the keys in ascending order (Python's sorted(total), or a TreeMap / std::map which keeps keys ordered) and emit each [value, total weight] pair.

Example: items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]. Value 1 gathers 1 + 5 = 6, value 3 gathers 8 + 1 = 9, and value 4 stays at 5. Sorted by value the result is [[1,6],[3,9],[4,5]].

Each pair is touched once to build the map and once more when reading it back out, with a sort over the distinct values, which is what gives the time bound below.

Time: O(n log n) Space: O(n)