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 thesum of weights of all items with value valuei.

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

Examples

Example 1

1
2
3
4
5
6
7
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

1
2
3
4
5
6
7
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

1
2
3
4
5
6
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.

Solution

Method 1 – Hash Map and Sorting

Intuition

To merge items with the same value, sum their weights using a hash map. After collecting all weights, sort the result by value for the final output.

Approach

  1. Initialize a hash map to store the sum of weights for each value.
  2. Iterate through items1 and items2, adding weights to the map for each value.
  3. Convert the map to a list of [value, weight] pairs.
  4. Sort the list by value in ascending order.
  5. Return the sorted list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
        map<int, int> mp;
        for (auto& v : items1) mp[v[0]] += v[1];
        for (auto& v : items2) mp[v[0]] += v[1];
        vector<vector<int>> ans;
        for (auto& [val, wt] : mp) ans.push_back({val, wt});
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func mergeSimilarItems(items1 [][]int, items2 [][]int) [][]int {
    mp := map[int]int{}
    for _, v := range items1 {
        mp[v[0]] += v[1]
    }
    for _, v := range items2 {
        mp[v[0]] += v[1]
    }
    ans := [][]int{}
    keys := []int{}
    for k := range mp {
        keys = append(keys, k)
    }
    sort.Ints(keys)
    for _, k := range keys {
        ans = append(ans, []int{k, mp[k]})
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
        Map<Integer, Integer> mp = new HashMap<>();
        for (int[] v : items1) mp.put(v[0], mp.getOrDefault(v[0], 0) + v[1]);
        for (int[] v : items2) mp.put(v[0], mp.getOrDefault(v[0], 0) + v[1]);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> keys = new ArrayList<>(mp.keySet());
        Collections.sort(keys);
        for (int k : keys) ans.add(Arrays.asList(k, mp.get(k)));
        return ans;
    }
}
1
2
3
4
5
6
7
8
class Solution {
    fun mergeSimilarItems(items1: Array<IntArray>, items2: Array<IntArray>): List<List<Int>> {
        val mp = mutableMapOf<Int, Int>()
        for (v in items1) mp[v[0]] = mp.getOrDefault(v[0], 0) + v[1]
        for (v in items2) mp[v[0]] = mp.getOrDefault(v[0], 0) + v[1]
        return mp.keys.sorted().map { listOf(it, mp[it]!!) }
    }
}
1
2
3
4
5
def merge_similar_items(items1: list[list[int]], items2: list[list[int]]) -> list[list[int]]:
    mp = {}
    for v, w in items1 + items2:
        mp[v] = mp.get(v, 0) + w
    return sorted([[v, w] for v, w in mp.items()])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
impl Solution {
    pub fn merge_similar_items(items1: Vec<Vec<i32>>, items2: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        use std::collections::BTreeMap;
        let mut mp = BTreeMap::new();
        for v in items1.iter().chain(items2.iter()) {
            *mp.entry(v[0]).or_insert(0) += v[1];
        }
        mp.into_iter().map(|(v, w)| vec![v, w]).collect()
    }
}
1
2
3
4
5
6
7
8
9
class Solution {
    mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
        const mp = new Map<number, number>();
        for (const [v, w] of [...items1, ...items2]) {
            mp.set(v, (mp.get(v) ?? 0) + w);
        }
        return Array.from(mp.entries()).sort((a, b) => a[0] - b[0]).map(([v, w]) => [v, w]);
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for sorting the result.
  • 🧺 Space complexity: O(n), for the hash map and result list.