2363. Merge Similar Items
Problem Description
You are provided with two 2D integer arrays called items1
and items2
. Each of these arrays contains pairs representing individual items, where the first number in the pair is the unique value of the item, and the second number is the weight of the item. The primary task is to merge these two sets of items together. When merging, if an item with the same value exists in both sets, you should add their weights together. Once merged, you should return a new 2D array containing pairs of items. Each pair should contain a unique value from any of the original arrays and the total weight for that value. Make sure to return the merged array in ascending order based on the item values.
Intuition
The solution focuses on efficiently combining two sets of items and accumulating the weights for items with the same value. The central idea is to use a data structure that allows easy updates of weights when the same value is encountered and also supports retrieval of items in a sorted manner based on their values. This can be achieved using a hash map that keeps track of the sum of weights for each unique value.
Here's a step-by-step approach on how we arrive at the solution:
-
Use a Counter (a special dictionary for counting hashable objects) from Python's collections module. It conveniently handles the addition of weights for us whenever we encounter an item with a value that's already in the Counter.
-
Iterate over both
items1
anditems2
(usingchain
from theitertools
module to avoid writing two loops or concatenating the lists) and for each item, add its weight to the corresponding value in the Counter. -
After processing all items, we have a Counter where the keys are the unique values and the values are the corresponding total weights. The remaining task is to sort this Counter by the item values.
-
Return the sorted items as a list of lists, which matches the expected output format.
By following these steps, we merge the two arrays and aggregate the weights for any duplicates, providing us with the correct output.
Learn more about Sorting patterns.
Solution Approach
The implementation of the solution is straightforward and utilizes Python's built-in libraries and data structures. Below is a step-by-step breakdown of the approach:
-
Counter from
collections
: In Python, theCounter
class is specifically designed to count hashable objects. It is essentially a dictionary subclass that helps to count the occurrences of each element. In the given solution, we use it not just to count, but to sum up the weights of items based on their unique values. -
chain
fromitertools
: Thechain
function is used to iterate over multiple iterables as if they were a single iterable. In this problem, we treatitems1
anditems2
as one continuous iterable so that we can apply the same action to both without duplicating code. -
Iteration and accumulation: We iterate over each item provided by
chain(items1, items2)
. For each value-weight pair(v, w)
, we add the weightw
to the count ofv
in our Counter. Ifv
is not yet in the Counter, it's added with the starting weightw
. -
Sorting the result: Once we have the Counter with all values and their collective weights, we need to sort this data. However, a Counter doesn't maintain sorted order, so we convert the Counter into a list of items using
cnt.items()
. Each item is a tuple of(value, total_weight)
. We then sort this list of tuples by the first element in each tuple, which is the value, as required for the output. -
Returning the result: After sorting, the items are in the form of a list of tuples. Since the problem specifies that the result should be a 2D integer array, we return the sorted list without any further transformation, as the list of tuples is interpreted as a 2D list.
Here's how the code achieves this:
class Solution:
def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
cnt = Counter()
# Chain both item lists and accumulate the weights in Counter
for v, w in chain(items1, items2):
cnt[v] += w
# Sort by value and return the (value, total_weight) pairs as a list
return sorted(cnt.items())
By relying on Counter and chain, the solution merges the two item lists effectively, with minimal lines of code and high readability.kÄi
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach:
Suppose we're given the following two lists of items:
items1
is[[1, 3], [4, 5], [6, 7]]
items2
is[[1, 1], [3, 3], [4, 1]]
We want to merge these lists by combining the weights of items that have the same value and sort them by value.
Using the steps provided:
-
Create a Counter. Since Python's Counter isn't explicitly mentioned in our example code, we'll start by simply creating an empty one:
cnt = Counter()
. -
Now, we chain
items1
anditems2
and begin to iterate over them. As we encounter each item, we add its weight to the corresponding value in the Counter:- For the first pair
[1, 3]
fromitems1
,cnt[1] = 3
. - Next,
[4, 5]
fromitems1
,cnt[4] = 5
. - Then
[6, 7]
fromitems1
,cnt[6] = 7
. - Now we move to
items2
. The first pair is[1, 1]
. Since1
is already incnt
, we add to its weight:cnt[1] = 3 + 1 = 4
. - Next,
[3, 3]
fromitems2
,cnt[3] = 3
since3
is not yet incnt
. - Finally,
[4, 1]
fromitems2
, where4
is already incnt
, so we update:cnt[4] = 5 + 1 = 6
.
- For the first pair
-
After iterating, we have a Counter with the following contents:
Counter({1: 4, 4: 6, 6: 7, 3: 3})
. -
We need to sort this by item values. We convert the Counter to a list of items with
cnt.items()
which gives us:[(1, 4), (4, 6), (6, 7), (3, 3)]
. When we sort this list, we get:[(1, 4), (3, 3), (4, 6), (6, 7)]
. -
Finally, we return the sorted list of tuples. This is exactly the output that the problem is expecting, which is a 2D list (or array in other programming languages) with item values and their total weights:
[[1, 4], [3, 3], [4, 6], [6, 7]]
.
So, the merged and sorted list is [[1, 4], [3, 3], [4, 6], [6, 7]]
. This small example demonstrates how the provided solution approach effectively combines and sorts the item pairs from two different lists.
Solution Implementation
1from collections import Counter
2from itertools import chain
3
4class Solution:
5 def mergeSimilarItems(self, items1, items2):
6 # Create a Counter object to keep track of item weights
7 item_weights = Counter()
8
9 # Iterate over the combined items from both lists
10 for value, weight in chain(items1, items2):
11 # Sum the weights of items with the same value
12 item_weights[value] += weight
13
14 # Return a sorted list of tuples, where each tuple consists of an item value and its total weight
15 # The list is sorted by item values
16 return sorted(item_weights.items())
17
1class Solution {
2 public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
3 // Array to count the quantities of each item where index represents the item value
4 int[] itemCounts = new int[1010];
5
6 // Adding quantities of items from items1 to itemCounts
7 for (int[] item : items1) {
8 int value = item[0]; // Item value
9 int quantity = item[1]; // Item quantity
10 itemCounts[value] += quantity;
11 }
12
13 // Adding quantities of items from items2 to itemCounts
14 for (int[] item : items2) {
15 int value = item[0]; // Item value
16 int quantity = item[1]; // Item quantity
17 itemCounts[value] += quantity;
18 }
19
20 // List to store the merged items as {value, quantity}
21 List<List<Integer>> mergedItems = new ArrayList<>();
22
23 // Iterating through itemCounts to add non-zero quantities to mergedItems
24 for (int value = 0; value < itemCounts.length; ++value) {
25 if (itemCounts[value] > 0) {
26 // Creating a list of item value and quantity and adding it to the result
27 mergedItems.add(List.of(value, itemCounts[value]));
28 }
29 }
30
31 // Return the list of merged items
32 return mergedItems;
33 }
34}
35
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
7 // Initialize a counter array to store frequencies for items up to index 1000
8 int itemFrequency[1010] = {};
9
10 // Iterate through first list of items, increment the frequency of each item
11 for (const auto& item : items1) {
12 itemFrequency[item[0]] += item[1];
13 }
14
15 // Iterate through second list of items, increment the frequency of each item
16 for (const auto& item : items2) {
17 itemFrequency[item[0]] += item[1];
18 }
19
20 // Declare a vector to hold the merged items
21 vector<vector<int>> mergedItems;
22
23 // Iterate through the frequency array
24 for (int i = 0; i < 1010; ++i) {
25 // If the current item has a non-zero frequency, add it to the merged list
26 if (itemFrequency[i]) {
27 mergedItems.push_back({i, itemFrequency[i]});
28 }
29 }
30
31 // Return the merged list of items
32 return mergedItems;
33 }
34};
35
1function mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
2 // Create an array to keep track of the combined weights. Initialize all counts to 0.
3 // The index represents the item's value, and the value at each index represents the weight.
4 const itemWeights = new Array(1001).fill(0);
5
6 // Iterate over the first array of items to add their weights to the itemWeights array
7 for (const [value, weight] of items1) {
8 itemWeights[value] += weight;
9 }
10
11 // Iterate over the second array of items to add their weights to the itemWeights array
12 for (const [value, weight] of items2) {
13 itemWeights[value] += weight;
14 }
15
16 // Convert the itemWeights array into tuples (value, weight), filter out items with a weight of 0,
17 // and return the result.
18 return itemWeights.map((weight, value) => [value, weight]) // Convert to tuples
19 .filter(([value, weight]) => weight !== 0); // Filter out items with zero weight
20}
21
Time and Space Complexity
Time Complexity
The time complexity of the given code can be analyzed in the following steps:
-
Chain Iteration: The
chain
function fromitertools
takes two listsitems1
anditems2
and creates an iterator that will iterate over both. The iteration itself takesO(N + M)
time whereN
is the length ofitems1
andM
is the length ofitems2
. -
Counter Update: For each
(v, w)
pair in the combined iterator, the counter's value is updated, which is anO(1)
operation. Since this happens for each element in the combined lists, it contributes toO(N + M)
time complexity. -
Sorting: The
sorted
function sorts the items in the counter based on keys. In Python, sorting is implemented with the Timsort algorithm which has a time complexity ofO(X * log(X))
, whereX
is the number of unique keys in thecnt
Counter. In the worst case, each item could be unique, leading toX = N + M
.
Combining these, the overall time complexity is O(N + M) + O(N + M) + O((N + M) * log(N + M))
which simplifies to O((N + M) * log(N + M))
.
Space Complexity
The space complexity of the given code can be considered as follows:
-
Counter Space: The
Counter
stores unique keys and their counts. In the worst case, every(v, w)
pair might have a uniquev
, which means it could have up toN + M
entries. Thus, it requiresO(N + M)
space. -
Output List: The space required to hold the sorted items is also
O(N + M)
because every key-count pair from the counter is converted into a list[v, w]
in the final output.
Therefore, the overall space complexity is O(N + M)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!