We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Merge Similar Items

Difficulty: Easy

Problem Description

You are given two 2D integer arrays, items1 and items2, representing two sets of items. Each array items has the following properties:

  • items[i] = [value_i, weight_i] where value_i represents the value and weight_i represents the weight of the ith item.
  • The value of each item in items is unique.

Return a 2D integer array ret where ret[i] = [value_i, weight_i], with weight_i being the sum of weights of all items with value value_i. Note: ret should be returned in ascending order by value.

Key Insights

  • Each item has a unique value, allowing for straightforward merging of weights.
  • We can utilize a hash map (dictionary) to easily aggregate weights based on values.
  • Sorting the final result is necessary to meet the requirement of returning values in ascending order.

Space and Time Complexity

Time Complexity: O(n + m + k log k) where n is the length of items1, m is the length of items2, and k is the number of unique values in the merged result.

Space Complexity: O(k) where k is the number of unique values in the merged result, since we need to store them in a hash map.

Solution

To solve the problem, we will use a hash map (dictionary) to store the total weight for each unique value from both items1 and items2. We will iterate through both lists and update the weights in the hash map. After merging the weights, we will convert the hash map into a list and sort it based on the values to return the final result.

Code Solutions

def mergeSimilarItems(items1, items2):
    weight_map = {}
    
    # Aggregate weights from items1
    for value, weight in items1:
        weight_map[value] = weight_map.get(value, 0) + weight
    
    # Aggregate weights from items2
    for value, weight in items2:
        weight_map[value] = weight_map.get(value, 0) + weight
    
    # Convert the dictionary to a list and sort by value
    result = [[value, weight] for value, weight in weight_map.items()]
    result.sort(key=lambda x: x[0])
    
    return result
← Back to All Questions