Scale Engineer

Merge Similar Items

Easy
#2151Time: O((N + M) * log(N + M)), where N is the length of `items1` and M is the length of `items2`. The dominant operation is sorting the combined list of size N + M.Space: O(N + M), where N is the length of `items1` and M is the length of `items2`. This space is required to store the combined list and the result list.
Algorithms
Sorting
Data structures
ArrayHash TableOrdered Set

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves first combining the two lists of items into a single list. Then, this combined list is sorted based on the item values. Finally, we iterate through the sorted list to merge items with the same value by summing their weights.

Algorithm

  • Create a new list, combinedItems.
  • Add all items from items1 and items2 into combinedItems.
  • Sort combinedItems in ascending order based on the value (the first element of each sub-array).
  • Initialize an empty result list, ret.
  • Iterate through the sorted combinedItems list. If the list is not empty, initialize currentVal and currentWeight with the first item's details.
  • For subsequent items, if the value is the same as currentVal, add its weight to currentWeight.
  • If the value is different, add the [currentVal, currentWeight] pair to ret, and then update currentVal and currentWeight to the current item's details.
  • After the loop finishes, make sure to add the last processed group of items to ret.
  • Return ret.

Walkthrough

The core idea is to gather all items together, sort them, and then process them in order. This is a straightforward way to group similar items next to each other, making the merging process a simple linear scan after the sort.

import java.util.ArrayList;import java.util.List;import java.util.Collections;import java.util.Comparator; class Solution {    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {        List<int[]> combined = new ArrayList<>();        for (int[] item : items1) {            combined.add(item);        }        for (int[] item : items2) {            combined.add(item);        }         // Sort the combined list by value        Collections.sort(combined, Comparator.comparingInt(a -> a[0]));         List<List<Integer>> ret = new ArrayList<>();        if (combined.isEmpty()) {            return ret;        }         int currentVal = combined.get(0)[0];        int currentWeight = combined.get(0)[1];         for (int i = 1; i < combined.size(); i++) {            int[] item = combined.get(i);            if (item[0] == currentVal) {                currentWeight += item[1];            } else {                List<Integer> mergedItem = new ArrayList<>();                mergedItem.add(currentVal);                mergedItem.add(currentWeight);                ret.add(mergedItem);                                currentVal = item[0];                currentWeight = item[1];            }        }                // Add the last merged item        List<Integer> lastMergedItem = new ArrayList<>();        lastMergedItem.add(currentVal);        lastMergedItem.add(currentWeight);        ret.add(lastMergedItem);         return ret;    }}

Complexity

Time

O((N + M) * log(N + M)), where N is the length of `items1` and M is the length of `items2`. The dominant operation is sorting the combined list of size N + M.

Space

O(N + M), where N is the length of `items1` and M is the length of `items2`. This space is required to store the combined list and the result list.

Trade-offs

Pros

  • Relatively simple to understand and implement.

  • Does not rely on specialized data structures like hash maps.

Cons

  • The sorting step makes it less efficient than other possible solutions.

  • Requires extra space proportional to the total number of items to hold the combined list.

Solutions

class Solution {public  List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {    int[] cnt = new int[1010];    for (var x : items1) {      cnt[x[0]] += x[1];    }    for (var x : items2) {      cnt[x[0]] += x[1];    }    List<List<Integer>> ans = new ArrayList<>();    for (int i = 0; i < cnt.length; ++i) {      if (cnt[i] > 0) {        ans.add(List.of(i, cnt[i]));      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem