Leetcode 2363: Merge Similar Items

Input: The input consists of two 2D arrays, items1 and items2. Each array contains pairs of integers where the first integer is the item's value and the second integer is the item's weight.

Example: items1 = [[2,3],[5,7],[4,1]], items2 = [[4,2],[2,4]]

Constraints:

• 1 <= items1.length, items2.length <= 1000

• items1[i].length == items2[i].length == 2

• 1 <= valuei, weighti <= 1000

• Each valuei in items1 is unique.

• Each valuei in items2 is unique.

Output: The output should be a 2D array where each element is a pair [value, weight], where the weight is the sum of weights of all items with the same value. The result should be sorted by value in ascending order.

Example: [[2,7],[4,3],[5,7]]

Constraints:

Goal: We need to combine the items from both arrays and sum the weights for the same values, then return the sorted result.

Steps:

• Create a map to store the value and weight pairs.

• Iterate through the items of the first array and add the value-weight pairs to the map.

• For each item in the second array, check if the value already exists in the map. If it does, add the weight; if it doesn't, create a new entry.

• Convert the map to a 2D array and sort it by the value.

Goal: Constraints ensure that the number of items and their values are within manageable limits.

Steps:

• 1 <= items1.length, items2.length <= 1000

• 1 <= valuei, weighti <= 1000

Assumptions:

• The value of each item is unique within the respective arrays.

• Each array contains at least one item.

• Input: Input: items1 = [[2,3],[5,7],[4,1]], items2 = [[4,2],[2,4]]

• Explanation: Here, the item with value 2 has a weight of 3 in items1 and a weight of 4 in items2, so the total weight becomes 7. Similarly, for value 4, the total weight is 3 (1 from items1 and 2 from items2). After merging, the result is sorted by the values: [[2,7],[4,3],[5,7]].

Approach: The problem can be solved using a hashmap to track the sum of weights for each unique value. This allows us to efficiently combine the arrays and sort the results.

Observations:

• We need to efficiently combine the weights of matching items from two arrays.

• The output should be sorted by value.

• Using a hashmap is an efficient way to accumulate the total weight for each unique value.

Steps:

• Create a hashmap to store the value as the key and the sum of weights as the value.

• Traverse the first array and populate the hashmap.

• Traverse the second array and update the hashmap accordingly.

• Convert the hashmap into a list and sort it based on the keys (values).

Empty Inputs:

• If either items1 or items2 is empty, the result should be the other array sorted by values.

Large Inputs:

• If the input arrays are large, the hashmap approach will still work efficiently.

Special Values:

• If two arrays contain the same value but different weights, the result should reflect the sum of the weights.

Constraints:

• Ensure that the input arrays follow the specified constraints.

vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) 
{
    map<int,int> m;
    for(int i=0;i<items1.size();i++)
    {
        m[items1[i][0]]=items1[i][1];
    }
    for(int i=0;i<items2.size();i++)
    {
        if(m.find(items2[i][0])!=m.end())
        {
            m[items2[i][0]]+=items2[i][1];
        }
        else
        {
            m[items2[i][0]]=items2[i][1];
        }
    }
    vector<vector<int>> ans;
    for(auto it : m)
    {
        ans.push_back({it.first,it.second});
    }
    return ans;
    
}

1 : Function Definition

vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2)

Define a function that takes two vectors of pairs as input: `items1` and `items2`. The function returns a vector of pairs where each pair contains an ID and its corresponding total value.

2 : Data Structures

    map<int,int> m;

Declare a map `m` that will store each item's ID as the key and its value as the associated value.

3 : Iteration

    for(int i=0;i<items1.size();i++)

Start iterating over the first input list `items1`.

4 : Map Update

        m[items1[i][0]]=items1[i][1];

Insert the item ID and value from `items1` into the map `m`. If the ID is already present, it will be overwritten.

5 : Iteration

    for(int i=0;i<items2.size();i++)

Start iterating over the second input list `items2`.

6 : Condition Check

        if(m.find(items2[i][0])!=m.end())

Check if the item ID from `items2` already exists in the map `m`.

7 : Map Update

            m[items2[i][0]]+=items2[i][1];

Add the value from `items2` to the existing value for that item ID in the map `m`.

8 : Add New Entry

        else

If the item ID is not found in the map, insert a new entry.

9 : Map Update

            m[items2[i][0]]=items2[i][1];

Insert the new item ID and its value from `items2` into the map `m`.

10 : Initialization

    vector<vector<int>> ans;

Declare a vector `ans` to store the final merged and summed items.

11 : Iteration

    for(auto it : m)

Iterate over the map `m` to extract the summed items.

12 : Vector Update

        ans.push_back({it.first,it.second});

Push each item (ID and value) from the map `m` into the result vector `ans`.

13 : Return Statement

    return ans;

Return the final result vector `ans` containing the merged items.

Best Case: O(n log n)

Average Case: O(n log n)

Worst Case: O(n log n)

Description: The time complexity is dominated by the sorting step after populating the hashmap.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) due to the storage required for the hashmap.

Leetcode 2363: Merge Similar Items

Explore →