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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Merge Similar Items

Number: 2447

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given two 2D integer arrays items1 and items2 representing two sets of items, where each item is represented by [value, weight], merge the items by summing the weights for items with the same value. Return the result as a 2D integer array sorted in ascending order by the value.

Key Insights

  • Use a hash table (or dictionary) to accumulate the sum of weights for each unique value.
  • Process both input arrays by iterating through them and updating the cumulative weight in the hash table.
  • Extract the key-value pairs from the hash table and sort them by key (the item value) to form the final answer.
  • The problem constraints ensure that using a hash table for this task will be efficient.

Space and Time Complexity

Time Complexity: O(n log n) - where n is the total number of items; the log n factor comes from sorting the unique values. Space Complexity: O(n) - space required for the hash table to store weights for each unique value.

Solution

We use a hash table (or similar data structure) to store the sum of weights for each unique value from both items1 and items2. As we iterate over each list, we update the cumulative weight for each value. Finally, the entries from the hash table are gathered into a list and sorted by their keys (values). This approach efficiently merges and sorts the items.

Code Solutions

def mergeSimilarItems(items1, items2):
    # Dictionary to store cumulative weight for each unique value.
    weight_map = {}
    
    # Process items1: add weight for each value.
    for value, weight in items1:
        weight_map[value] = weight_map.get(value, 0) + weight
    
    # Process items2: add weight for each value.
    for value, weight in items2:
        weight_map[value] = weight_map.get(value, 0) + weight
    
    # Prepare result: convert dictionary to list and sort by value.
    result = [[value, total_weight] for value, total_weight in weight_map.items()]
    result.sort(key=lambda x: x[0])
    return result

# Example usage:
items1 = [[1, 1], [4, 5], [3, 8]]
items2 = [[3, 1], [1, 5]]
print(mergeSimilarItems(items1, items2))  # Output: [[1, 6], [3, 9], [4, 5]]
← Back to All Questions