Skip to main content
Talentd

Merge Similar Items - Solution & Explanation

EasyArrayHash TableSortingOrdered Set17 min readAsked at: Google
Practice this problem

Problem Statement

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

  • items[i] = [valuei, weighti] where valuei represents the value and weighti 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] = [valuei, weighti], with weighti being the sum of weights of all items with value valuei.

Note: ret should be returned in ascending order by value.

 

Example 1:

Input: items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]
Output: [[1,6],[3,9],[4,5]]
Explanation: 
The item with value = 1 occurs in items1 with weight = 1 and in items2 with weight = 5, total weight = 1 + 5 = 6.
The item with value = 3 occurs in items1 with weight = 8 and in items2 with weight = 1, total weight = 8 + 1 = 9.
The item with value = 4 occurs in items1 with weight = 5, total weight = 5.  
Therefore, we return [[1,6],[3,9],[4,5]].

Example 2:

Input: items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[3,2],[1,3]]
Output: [[1,4],[2,4],[3,4]]
Explanation: 
The item with value = 1 occurs in items1 with weight = 1 and in items2 with weight = 3, total weight = 1 + 3 = 4.
The item with value = 2 occurs in items1 with weight = 3 and in items2 with weight = 1, total weight = 3 + 1 = 4.
The item with value = 3 occurs in items1 with weight = 2 and in items2 with weight = 2, total weight = 2 + 2 = 4.
Therefore, we return [[1,4],[2,4],[3,4]].

Example 3:

Input: items1 = [[1,3],[2,2]], items2 = [[7,1],[2,2],[1,4]]
Output: [[1,7],[2,4],[7,1]]
Explanation:
The item with value = 1 occurs in items1 with weight = 3 and in items2 with weight = 4, total weight = 3 + 4 = 7. 
The item with value = 2 occurs in items1 with weight = 2 and in items2 with weight = 2, total weight = 2 + 2 = 4. 
The item with value = 7 occurs in items2 with weight = 1, total weight = 1.
Therefore, we return [[1,7],[2,4],[7,1]].

 

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.

Approach Overview

Problem Overview: You receive two arrays of items where each element is [value, weight]. Items with the same value represent the same type, so their weights must be combined. After merging both lists, return a sorted list of [value, totalWeight] pairs ordered by value.

The key observation: values may appear multiple times across both arrays, so you need a way to aggregate weights by value before producing the final sorted output.

Approach 1: Use HashMap to Aggregate Weights (O(n log n) time, O(n) space)

Use a hash map where the key is the item value and the value is the accumulated weight. Iterate through both input arrays and update the map with map[value] += weight. This handles duplicates across arrays in constant-time lookups. After aggregation, convert the map entries into a list and sort by value to meet the output requirement.

This approach relies on fast hash lookups from a hash table and simple iteration over the array. The sorting step ensures results appear in increasing order of value. Total complexity becomes O(n log n) due to sorting the unique values, with O(n) auxiliary space for the map.

Approach 2: Use Counting Array (O(n + k) time, O(k) space)

If the value range is small and bounded, a counting array becomes even simpler. Create an array where the index represents the item value and the element stores the accumulated weight. Iterate through both input arrays and add weights directly to count[value]. After processing all items, scan the counting array and collect indices whose weight is greater than zero.

This technique removes the need for hashing and sorting because the array indices naturally produce values in ascending order. The runtime becomes O(n + k), where n is the number of items and k is the maximum value range. Space complexity is O(k). Conceptually this behaves like a lightweight form of bucket counting related to sorting techniques.

Recommended for interviews: The HashMap aggregation approach is the expected solution. It demonstrates understanding of frequency counting and efficient lookups, a common pattern in array problems. The counting array version is slightly faster but only works when the value range is small and known ahead of time. Interviewers usually want to see the general-purpose hash map solution first, then discuss optimizations if constraints allow.

Approach 1: Approach 1: Use HashMap to Aggregate Weights

In this approach, we utilize a hash map (or dictionary) to store the cumulative weights of items using their values as keys. We iterate over both lists, updating the map with the total weights. Finally, we extract the entries from the map, sort them by their keys, and format them into the desired list structure.

This Python solution merges both item lists, iterating over each pair of value and weight, updating a dictionary to accumulate weights based on item values. The final list is obtained by sorting and extracting the dictionary entries.

Code

PythonCJavaC++C#JavaScript

Python

C

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(n + m), where n and m are the number of items in items1 and items2 respectively.
Space Complexity: O(n + m), to store the weights in the map.

Try this approach in the editor →

Approach 2: Approach 2: Use Counting Array

This approach leverages a fixed-size array as a counting mechanism due to the constraint of item values being between 1 and 1000. This way, we simplify weight sum calculations using a direct addressable array.

This Python solution creates an array indexed by values (1 to 1000), incrementing counts as it iterates through item lists. Outputs are filtered and sorted by nature of index iteration.

Code

PythonCJavaC++C#JavaScript

Python

C

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(n + m + k), where k is fixed at 1000.
Space Complexity: O(k), for the counting array.

Try this approach in the editor →

Approach 3: Hash Table or Array

We can use a hash table or array cnt to count the total weight of each item in items1 and items2. Then, we traverse the values in ascending order, adding each value and its corresponding total weight to the result array.

The time complexity is O(n + m) and the space complexity is O(n + m), where n and m are the lengths of items1 and items2 respectively.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Use HashMap to Aggregate Weights

Time Complexity: O(n + m), where n and m are the number of items in items1 and items2 respectively.
Space Complexity: O(n + m), to store the weights in the map.

Approach 2: Use Counting Array

Time Complexity: O(n + m + k), where k is fixed at 1000.
Space Complexity: O(k), for the counting array.

Hash Table or Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap Aggregation + SortO(n log n)O(n)General case when values may appear multiple times and need aggregation
Counting ArrayO(n + k)O(k)When the value range is small and bounded, allowing direct indexing

Video Solution

Merge Similar Items || Leetcode Contest Easy || CPP || Most intuitive solution 🤩🤩 • Coding Techniques with Komal | Newton School • 1,068 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Merge Similar Items easy or hard?
Merge Similar Items is classified as an Easy problem. The main skill tested is recognizing the frequency aggregation pattern using a hash map or counting array, which is a common technique in array and hash table problems.
Merge Similar Items Python/Java solution
In Python, use a dictionary to accumulate weights and then return a sorted list of key-value pairs. In Java, a HashMap<Integer, Integer> performs the same aggregation before converting entries to a sorted list. Both implementations follow the same O(n log n) approach.
How to solve Merge Similar Items in O(n)?
Use a counting array if the value range is small. Each index represents a value and stores the accumulated weight. Iterate through both arrays to update counts, then scan the counting array to produce the sorted output. The runtime becomes O(n + k), where k is the value range.
What is the best approach for Merge Similar Items?
The HashMap aggregation approach is the most practical solution. Iterate through both arrays, store weights in a hash map keyed by value, and sum duplicates. After aggregation, sort the keys and return the merged list. The overall complexity is O(n log n) time and O(n) space.
Is Merge Similar Items asked at Google/Amazon/Meta?
Problems based on frequency counting and hash map aggregation frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern of grouping values and summing counts is very common.
What data structure is used in Merge Similar Items?
The core data structure is a hash table (HashMap or dictionary). It maps each item value to its cumulative weight, allowing constant-time updates while scanning the arrays. Some solutions also use a counting array when the value range is constrained.
What is the time complexity of Merge Similar Items?
The typical solution runs in O(n log n) time because values are aggregated in a hash map and then sorted. Hash map insertion and updates are O(1) on average, while sorting the unique values takes O(m log m), where m is the number of distinct items.

Ready to solve this problem?

Practice Merge Similar Items with our built-in code editor and test cases.

Practice on FleetCode
Previous

Merge Two 2D Arrays by Summing Values