Watch 10 video solutions for Merge Similar Items, a easy level problem involving Array, Hash Table, Sorting. This walkthrough by Coding Techniques with Komal | Newton School has 1,054 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |