Merge Similar Items
Easy · Design · Array · Hash Table · Sorting · Ordered Set
Problem
You are given two lists of items, items1 and items2. Each entry [value, weight] describes one item: value identifies it and weight is how much of it there is. Within one list every value appears at most once, but the same value may appear in both lists.
Return a list ret where ret[i] = [value_i, weight_i], one entry per distinct value across both lists, with weight_i the total weight of that value in both lists. Sort ret by value in ascending order.
Examples
Input: items1 = [[4,2],[1,5]], items2 = [[1,3],[6,1]] Output: [[1,8],[4,2],[6,1]]
Value 1 is in both lists, so its weights add to 5 + 3 = 8. Values 4 and 6 appear once.
Input: items1 = [[9,9]], items2 = [[9,1]] Output: [[9,10]]
The only value, 9, totals 9 + 1 = 10.
Input: items1 = [[3,1],[2,4]], items2 = [[5,7]] Output: [[2,4],[3,1],[5,7]]
No value repeats, so the answer is every item sorted by value.
Constraints
- 1 <= len(items1), len(items2) <= 1000
- len(items1[i]) == len(items2[i]) == 2
- 1 <= value, weight <= 1000
- Each value in items1 is unique
- Each value in items2 is unique
Approaches
- Scan the result list for each item — time O((n + m)²), space O(n + m)
Follow-up
If both lists were already sorted by value, you could merge them with two pointers in O(n + m) without a map, exactly like the merge step of merge sort. With values bounded by 1000, a counting array gives the same O(n + m + V) time.
Related problems
Start free on Cariara · Coding problems · System design studio
