Merge Similar Items

Easy
1796.

Merge Similar Items

Merge Similar Items is an easy coding problem on arrays, hash table and sorting, asked in Amazon interviews.

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 <= 1000
  • items1[i].length == items2[i].length == 2
  • 1 <= value, weight <= 1000
  • the values in items1 are unique, and so are the values in items2
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} items1
 * @param {number[][]} items2
 * @return {number[][]}
 */
var mergeSimilarItems = function(items1, items2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • items1[i].length == items2[i].length == 2
  • 1 <= value, weight <= 1000
  • the values in items1 are unique, and so are the values in items2

Hints for Merge Similar Items

  1. Hint 1

    Add up weights per value — a hash map or, since values are at most 1000, an array indexed by value.

  2. 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

  1. Create total[1..1000] filled with 0.
  2. For each [v, w] in both lists, add w to total[v].
  3. For v from 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