Merge Similar Items — LeetCode 2363 Python Solution

The problem

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.

Example

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.

Python solution

class Solution:
    def mergeSimilarItems(
        self, items1: List[List[int]], items2: List[List[int]]
    ) -> List[List[int]]:
        cnt = Counter()
        for v, w in chain(items1, items2):
            cnt[v] += w
        return sorted(cnt.items())

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2363. Merge Similar Items is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems