Merge Similar Items

Difficulty: Easy | Acceptance: 77.50% | Paid: No Topics: Array, Hash Table, Sorting, Ordered Set

You are given two 2D integer arrays, items1 and items2, representing two sets of items. Each array items has the form items[i] = [valuei, weighti] where valuei is the value of the ith item and weighti is the weight of the ith item.

The weight of the ith item is the number of times the ith item appears.

You need to merge the two sets of items by summing the weights of items with the same value.

Return the merged items sorted by value in ascending order.

Examples

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

Table of Contents

• Examples
• Constraints
• Hash Map Approach
• Sorting + Two Pointers Approach
• Ordered Map Approach

Hash Map Approach

Intuition Use a hash map to accumulate weights for each value from both arrays, then convert to a sorted list.

Steps

• Create a hash map to store value -> weight mappings
• Iterate through items1 and add each value-weight pair to the map
• Iterate through items2 and add each value-weight pair to the map (summing weights for existing values)
• Convert the map entries to a list and sort by value
• Return the sorted list

class Solution:
    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
        from collections import defaultdict
        
        weight_map = defaultdict(int)
        
        for value, weight in items1:
            weight_map[value] += weight
        
        for value, weight in items2:
            weight_map[value] += weight
        
        result = [[value, weight_map[value]] for value in sorted(weight_map.keys())]
        return result

Complexity

• Time: O(n log n) where n is the total number of unique values
• Space: O(n) for the hash map
• Notes: Simple and intuitive, but requires sorting at the end

Sorting + Two Pointers Approach

Intuition Sort both arrays by value, then use two pointers to merge them like in merge sort.

Steps

• Sort items1 and items2 by value
• Use two pointers to traverse both arrays
• Compare values at current pointers:
  • If equal, sum weights and advance both pointers
  • If one is smaller, add that item and advance its pointer
• Add remaining items from either array
• Return the merged result

class Solution:
    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
        items1.sort()
        items2.sort()
        
        result = []
        i, j = 0, 0
        n, m = len(items1), len(items2)
        
        while i < n and j < m:
            val1, w1 = items1[i]
            val2, w2 = items2[j]
            
            if val1 == val2:
                result.append([val1, w1 + w2])
                i += 1
                j += 1
            elif val1 < val2:
                result.append([val1, w1])
                i += 1
            else:
                result.append([val2, w2])
                j += 1
        
        while i < n:
            result.append(items1[i])
            i += 1
        
        while j < m:
            result.append(items2[j])
            j += 1
        
        return result

Complexity

• Time: O(n log n) for sorting both arrays
• Space: O(n) for the result array
• Notes: More complex implementation but avoids hash map overhead

Ordered Map Approach

Intuition Use an ordered map (TreeMap in Java, map in C++) that maintains keys in sorted order while allowing updates.

Steps

• Create an ordered map
• Iterate through items1 and add each value-weight pair
• Iterate through items2 and add each value-weight pair (summing weights)
• Convert the ordered map to a list (already sorted)
• Return the result

class Solution:
    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
        from collections import defaultdict
        
        weight_map = defaultdict(int)
        
        for value, weight in items1:
            weight_map[value] += weight
        
        for value, weight in items2:
            weight_map[value] += weight
        
        result = [[value, weight_map[value]] for value in sorted(weight_map.keys())]
        return result

Complexity

• Time: O(n log n) for ordered map operations
• Space: O(n) for the ordered map
• Notes: Cleanest solution in languages with built-in ordered maps (Java TreeMap, C++ map)