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.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 <= 1000items1[i].length == items2[i].length == 21 <= valuei, weighti <= 1000valuei in items1 is unique.valuei in items2 is unique.Problem Overview: You receive two arrays of items where each element is [value, weight]. Items with the same value represent the same type, so their weights must be combined. After merging both lists, return a sorted list of [value, totalWeight] pairs ordered by value.
The key observation: values may appear multiple times across both arrays, so you need a way to aggregate weights by value before producing the final sorted output.
Approach 1: Use HashMap to Aggregate Weights (O(n log n) time, O(n) space)
Use a hash map where the key is the item value and the value is the accumulated weight. Iterate through both input arrays and update the map with map[value] += weight. This handles duplicates across arrays in constant-time lookups. After aggregation, convert the map entries into a list and sort by value to meet the output requirement.
This approach relies on fast hash lookups from a hash table and simple iteration over the array. The sorting step ensures results appear in increasing order of value. Total complexity becomes O(n log n) due to sorting the unique values, with O(n) auxiliary space for the map.
Approach 2: Use Counting Array (O(n + k) time, O(k) space)
If the value range is small and bounded, a counting array becomes even simpler. Create an array where the index represents the item value and the element stores the accumulated weight. Iterate through both input arrays and add weights directly to count[value]. After processing all items, scan the counting array and collect indices whose weight is greater than zero.
This technique removes the need for hashing and sorting because the array indices naturally produce values in ascending order. The runtime becomes O(n + k), where n is the number of items and k is the maximum value range. Space complexity is O(k). Conceptually this behaves like a lightweight form of bucket counting related to sorting techniques.
Recommended for interviews: The HashMap aggregation approach is the expected solution. It demonstrates understanding of frequency counting and efficient lookups, a common pattern in array problems. The counting array version is slightly faster but only works when the value range is small and known ahead of time. Interviewers usually want to see the general-purpose hash map solution first, then discuss optimizations if constraints allow.
In this approach, we utilize a hash map (or dictionary) to store the cumulative weights of items using their values as keys. We iterate over both lists, updating the map with the total weights. Finally, we extract the entries from the map, sort them by their keys, and format them into the desired list structure.
This Python solution merges both item lists, iterating over each pair of value and weight, updating a dictionary to accumulate weights based on item values. The final list is obtained by sorting and extracting the dictionary entries.
Time Complexity: O(n + m), where n and m are the number of items in items1 and items2 respectively.
Space Complexity: O(n + m), to store the weights in the map.
This approach leverages a fixed-size array as a counting mechanism due to the constraint of item values being between 1 and 1000. This way, we simplify weight sum calculations using a direct addressable array.
This Python solution creates an array indexed by values (1 to 1000), incrementing counts as it iterates through item lists. Outputs are filtered and sorted by nature of index iteration.
Time Complexity: O(n + m + k), where k is fixed at 1000.
Space Complexity: O(k), for the counting array.
We can use a hash table or array cnt to count the total weight of each item in items1 and items2. Then, we traverse the values in ascending order, adding each value and its corresponding total weight to the result array.
The time complexity is O(n + m) and the space complexity is O(n + m), where n and m are the lengths of items1 and items2 respectively.
| Approach | Complexity |
|---|---|
| Approach 1: Use HashMap to Aggregate Weights | Time Complexity: O(n + m), where n and m are the number of items in items1 and items2 respectively. |
| Approach 2: Use Counting Array | Time Complexity: O(n + m + k), where k is fixed at 1000. |
| Hash Table or Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Aggregation + Sort | O(n log n) | O(n) | General case when values may appear multiple times and need aggregation |
| Counting Array | O(n + k) | O(k) | When the value range is small and bounded, allowing direct indexing |
Merge Similar Items || Leetcode Contest Easy || CPP || Most intuitive solution 🤩🤩 • Coding Techniques with Komal | Newton School • 1,054 views views
Watch 9 more video solutions →Practice Merge Similar Items with our built-in code editor and test cases.
Practice on FleetCode