Merge Similar Items
EasyPrompt
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]wherevalueirepresents the value andweightirepresents the weight of theithitem.- The value of each item in
itemsis 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 <= 1000- Each
valueiinitems1is unique. - Each
valueiinitems2is unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves first combining the two lists of items into a single list. Then, this combined list is sorted based on the item values. Finally, we iterate through the sorted list to merge items with the same value by summing their weights.
Algorithm
- Create a new list,
combinedItems. - Add all items from
items1anditems2intocombinedItems. - Sort
combinedItemsin ascending order based on thevalue(the first element of each sub-array). - Initialize an empty result list,
ret. - Iterate through the sorted
combinedItemslist. If the list is not empty, initializecurrentValandcurrentWeightwith the first item's details. - For subsequent items, if the
valueis the same ascurrentVal, add itsweighttocurrentWeight. - If the
valueis different, add the[currentVal, currentWeight]pair toret, and then updatecurrentValandcurrentWeightto the current item's details. - After the loop finishes, make sure to add the last processed group of items to
ret. - Return
ret.
Walkthrough
The core idea is to gather all items together, sort them, and then process them in order. This is a straightforward way to group similar items next to each other, making the merging process a simple linear scan after the sort.
import java.util.ArrayList;import java.util.List;import java.util.Collections;import java.util.Comparator; class Solution { public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) { List<int[]> combined = new ArrayList<>(); for (int[] item : items1) { combined.add(item); } for (int[] item : items2) { combined.add(item); } // Sort the combined list by value Collections.sort(combined, Comparator.comparingInt(a -> a[0])); List<List<Integer>> ret = new ArrayList<>(); if (combined.isEmpty()) { return ret; } int currentVal = combined.get(0)[0]; int currentWeight = combined.get(0)[1]; for (int i = 1; i < combined.size(); i++) { int[] item = combined.get(i); if (item[0] == currentVal) { currentWeight += item[1]; } else { List<Integer> mergedItem = new ArrayList<>(); mergedItem.add(currentVal); mergedItem.add(currentWeight); ret.add(mergedItem); currentVal = item[0]; currentWeight = item[1]; } } // Add the last merged item List<Integer> lastMergedItem = new ArrayList<>(); lastMergedItem.add(currentVal); lastMergedItem.add(currentWeight); ret.add(lastMergedItem); return ret; }}Complexity
Time
O((N + M) * log(N + M)), where N is the length of `items1` and M is the length of `items2`. The dominant operation is sorting the combined list of size N + M.
Space
O(N + M), where N is the length of `items1` and M is the length of `items2`. This space is required to store the combined list and the result list.
Trade-offs
Pros
Relatively simple to understand and implement.
Does not rely on specialized data structures like hash maps.
Cons
The sorting step makes it less efficient than other possible solutions.
Requires extra space proportional to the total number of items to hold the combined list.
A more efficient approach uses a map to store the sum of weights for each unique value. A TreeMap is specifically chosen because it automatically keeps the entries sorted by key (the item's value). This eliminates the need for a separate sorting step at the end.
Algorithm
- Initialize a
TreeMap<Integer, Integer>calledvalueToWeightMap. - Iterate through
items1. For each item[value, weight], update the map:map.put(value, map.getOrDefault(value, 0) + weight). - Iterate through
items2and perform the same update operation on the map for each item. - After processing both lists, the
TreeMapwill contain all unique values as keys and their corresponding total weights as values, already sorted by the key. - Initialize an empty result list,
ret. - Iterate through the entries of the
TreeMapand add each[key, value]pair to theretlist. - Return
ret.
Walkthrough
We can iterate through both input arrays and use a map to aggregate weights for each value. The key of the map will be the item's value, and the value of the map will be the total weight. By using a TreeMap, the keys (values) are maintained in sorted order automatically, which simplifies the final step of creating the sorted output list.
import java.util.ArrayList;import java.util.List;import java.util.Map;import java.util.TreeMap; class Solution { public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) { Map<Integer, Integer> map = new TreeMap<>(); // Process items1 for (int[] item : items1) { int value = item[0]; int weight = item[1]; map.put(value, map.getOrDefault(value, 0) + weight); } // Process items2 for (int[] item : items2) { int value = item[0]; int weight = item[1]; map.put(value, map.getOrDefault(value, 0) + weight); } // Convert map to the result list format List<List<Integer>> ret = new ArrayList<>(); for (Map.Entry<Integer, Integer> entry : map.entrySet()) { List<Integer> item = new ArrayList<>(); item.add(entry.getKey()); item.add(entry.getValue()); ret.add(item); } return ret; }}Complexity
Time
O((N + M) * logK), where N and M are the lengths of `items1` and `items2`, and K is the number of unique items. Each insertion or update in a `TreeMap` takes `O(logK)` time.
Space
O(K), where K is the number of unique items. This space is used to store the K unique items in the `TreeMap` and the result list.
Trade-offs
Pros
More efficient than the brute-force sorting approach.
The code is clean and concise.
Handles the sorting requirement elegantly by the nature of the
TreeMap.
Cons
Has a logarithmic time complexity factor for each item processed, which is slower than a linear-time approach if one is possible.
The overhead of maintaining a balanced binary tree can make it slightly slower in practice than a
HashMapfollowed by a sort, though the asymptotic complexity is similar.
This is the most efficient approach, leveraging the constraint that item values are within a limited range (1 to 1000). We can use a simple array as a direct-access map (or frequency map) to store the total weight for each value. The index of the array corresponds to the item's value.
Algorithm
- Create an integer array
weightsof size 1001 and initialize all its elements to 0. - Iterate through
items1. For each item[value, weight], update the array:weights[value] += weight. - Iterate through
items2and perform the same update:weights[value] += weight. - Initialize an empty result list,
ret. - Iterate through the
weightsarray from index 1 to 1000. - If
weights[i]is greater than 0, it means an item withvalue = iexists. Create a new list[i, weights[i]]and add it toret. - Since we iterate through the array by index, the resulting list
retwill be automatically sorted by value. - Return
ret.
Walkthrough
Since the maximum value is 1000, we can create an array of size 1001. array[i] will store the sum of weights for items with value = i. This approach avoids the overhead of hashing (like in HashMap) or maintaining a balanced tree (like in TreeMap) and provides O(1) access time for updates. The final result is built by iterating through this array, which naturally produces a list sorted by value.
import java.util.ArrayList;import java.util.List; class Solution { public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) { // Max value is 1000, so we need an array of size 1001 for indices 0-1000. int[] weights = new int[1001]; // Process items1 for (int[] item : items1) { weights[item[0]] += item[1]; } // Process items2 for (int[] item : items2) { weights[item[0]] += item[1]; } List<List<Integer>> ret = new ArrayList<>(); for (int value = 1; value <= 1000; value++) { if (weights[value] > 0) { List<Integer> item = new ArrayList<>(); item.add(value); item.add(weights[value]); ret.add(item); } } return ret; }}Complexity
Time
O(N + M + V), where N and M are the lengths of the input arrays, and V is the maximum possible value (1000). This simplifies to linear time complexity as V is a constant.
Space
O(V), where V is the maximum possible value (1000). The space for the result list depends on the number of unique items, K, so it's O(K). The dominant factor is O(V).
Trade-offs
Pros
The most efficient solution with linear time complexity.
Simple implementation without complex data structures.
Low constant factors, making it very fast in practice.
Cons
This approach is only feasible because the range of values is small and known beforehand.
It would be impractical or memory-intensive if values could be very large or were not positive integers.
Solutions
Solution
class Solution {public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) { int[] cnt = new int[1010]; for (var x : items1) { cnt[x[0]] += x[1]; } for (var x : items2) { cnt[x[0]] += x[1]; } List<List<Integer>> ans = new ArrayList<>(); for (int i = 0; i < cnt.length; ++i) { if (cnt[i] > 0) { ans.add(List.of(i, cnt[i])); } } return ans; }}class Solution {public: vector<vector<int>> mergeSimilarItems(vector<vector<int>> &items1, vector<vector<int>> &items2) { int cnt[1010]{}; for (auto &x : items1) { cnt[x[0]] += x[1]; } for (auto &x : items2) { cnt[x[0]] += x[1]; } vector<vector<int>> ans; for (int i = 0; i < 1010; ++i) { if (cnt[i]) { ans.push_back({i, cnt[i]}); } } return ans; }};class Solution: def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]: cnt = Counter() for v, w in chain(items1, items2): cnt[v] += w return sorted(cnt . items())Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.