Merge Similar Items — Solution in Python, Java & C++
Merge Similar Items solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon.
Merge Similar Items is an easy coding problem on arrays, hash table and sorting, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting, Ordered Set
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two lists of items, items1 and items2. Each entry [value, weight] describes an item: its value and its weight. The values within one list are unique, but a value may appear in both lists.
Return a list ret of pairs [value, totalWeight], one for every value that appears in either list, where totalWeight is the sum of the weights of all items with that value. Return ret sorted by value in ascending order.
Example 1
Input: items1 = [[2,3],[7,1]], items2 = [[7,4],[5,2],[2,1]]
Output: [[2,4],[5,2],[7,5]]
Explanation: Value 2 weighs 3 + 1, value 5 weighs 2, value 7 weighs 1 + 4.
Example 2
Input: items1 = [[1,1]], items2 = [[2,2]]
Output: [[1,1],[2,2]]
Explanation: No value is shared, so each item passes through unchanged.
Example 3
Input: items1 = [[9,1000]], items2 = [[9,1000]]
Output: [[9,2000]]
Constraints
1 <= items1.length, items2.length <= 1000items1[i].length == items2[i].length == 21 <= value, weight <= 1000the values in items1 are unique, and so are the values in items2
Hints for Merge Similar Items
Hint 1
Add up weights per value — a hash map or, since values are at most 1000, an array indexed by value.
Hint 2
Walking the indices 1..1000 in order produces the values already sorted.
How to solve Merge Similar Items
Sum the weights per value; because values are small integers, an array indexed by value both accumulates and sorts them.
Approach
- Create
total[1..1000]filled with 0. - For each
[v, w]in both lists, addwtototal[v]. - For
vfrom 1 to 1000, emit[v, total[v]]whenever it is positive.
Why it works
Every item contributes its weight to exactly its own value, and weights are positive, so a value appears in the output exactly when some item has it. Scanning the indices in increasing order yields ascending values without a sort.
Complexity
- Time —
O(n + m + V) with V = 1000 - Space —
O(V)
Pitfalls
- A value present in only one list must still appear in the result.
- The output order is by value, not by first appearance.
Reference solution
Python
from typing import List
def mergeSimilarItems(items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
total = [0] * 1001
for v, w in items1 + items2:
total[v] += w
return [[v, total[v]] for v in range(1, 1001) if total[v]]Java
public static int[][] mergeSimilarItems(int[][] items1, int[][] items2) {
int[] total = new int[1001];
for (int[] it : items1) total[it[0]] += it[1];
for (int[] it : items2) total[it[0]] += it[1];
List<int[]> out = new ArrayList<>();
for (int v = 1; v <= 1000; v++) if (total[v] > 0) out.add(new int[] { v, total[v] });
return out.toArray(new int[0][]);
}C++
vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
vector<int> total(1001, 0);
for (auto& it : items1) total[it[0]] += it[1];
for (auto& it : items2) total[it[0]] += it[1];
vector<vector<int>> out;
for (int v = 1; v <= 1000; v++) if (total[v] > 0) out.push_back({v, total[v]});
return out;
}JavaScript
var mergeSimilarItems = function(items1, items2) {
var total = new Array(1001).fill(0);
var all = items1.concat(items2);
for (var i = 0; i < all.length; i++) total[all[i][0]] += all[i][1];
var out = [];
for (var v = 1; v <= 1000; v++) if (total[v] > 0) out.push([v, total[v]]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets