2363. Merge Similar Items

EasyArrayHash TableOrdered SetSorting
Leetcode Link

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:

  1. 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.

  2. Iterate over both items1 and items2 (using chain from the itertools module to avoid writing two loops or concatenating the lists) and for each item, add its weight to the corresponding value in the Counter.

  3. 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.

  4. 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.

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:

  1. Counter from collections: In Python, the Counter 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.

  2. chain from itertools: The chain function is used to iterate over multiple iterables as if they were a single iterable. In this problem, we treat items1 and items2 as one continuous iterable so that we can apply the same action to both without duplicating code.

  3. Iteration and accumulation: We iterate over each item provided by chain(items1, items2). For each value-weight pair (v, w), we add the weight w to the count of v in our Counter. If v is not yet in the Counter, it's added with the starting weight w.

  4. 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.

  5. 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:

1class Solution:
2    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
3        cnt = Counter()
4        # Chain both item lists and accumulate the weights in Counter
5        for v, w in chain(items1, items2):
6            cnt[v] += w
7        # Sort by value and return the (value, total_weight) pairs as a list
8        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

Example 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:

  1. 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().

  2. Now, we chain items1 and items2 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] from items1, cnt[1] = 3.
    • Next, [4, 5] from items1, cnt[4] = 5.
    • Then [6, 7] from items1, cnt[6] = 7.
    • Now we move to items2. The first pair is [1, 1]. Since 1 is already in cnt, we add to its weight: cnt[1] = 3 + 1 = 4.
    • Next, [3, 3] from items2, cnt[3] = 3 since 3 is not yet in cnt.
    • Finally, [4, 1] from items2, where 4 is already in cnt, so we update: cnt[4] = 5 + 1 = 6.
  3. After iterating, we have a Counter with the following contents: Counter({1: 4, 4: 6, 6: 7, 3: 3}).

  4. 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)].

  5. 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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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:

  1. Chain Iteration: The chain function from itertools takes two lists items1 and items2 and creates an iterator that will iterate over both. The iteration itself takes O(N + M) time where N is the length of items1 and M is the length of items2.

  2. Counter Update: For each (v, w) pair in the combined iterator, the counter's value is updated, which is an O(1) operation. Since this happens for each element in the combined lists, it contributes to O(N + M) time complexity.

  3. 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 of O(X * log(X)), where X is the number of unique keys in the cnt Counter. In the worst case, each item could be unique, leading to X = 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:

  1. Counter Space: The Counter stores unique keys and their counts. In the worst case, every (v, w) pair might have a unique v, which means it could have up to N + M entries. Thus, it requires O(N + M) space.

  2. 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).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫