Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Merge Similar Items solution and explanation

EasyArrayHash TableOrdered SetSorting6 min read77.4% acceptanceUpdated 9 Apr 2026
Asked atGoogle
Practise Merge Similar Items
11:25
Merge Similar Items || Leetcode Contest Easy || CPP || Most intuitive solution 🤩🤩Coding Techniques with Komal | Newton School · 11:25 · 1K viewsWatch on YouTube
9 more videos on this problem
  1. Merge Similar Items || Leetcode Contest Easy || CPP || Most intuitive solution 🤩🤩Coding Techniques with Komal | Newton School · 11:25 · 1K views
  2. 2363. Merge Similar Items (Leetcode Easy)Programming Live with Larry · 3:01 · 759 views
  3. Leetcode 2363: Merge Similar ItemsAlgorithms Casts · 3:47 · 695 views
  4. Leetcode BiWeekly contest 84 - Easy - Merge Similar ItemsPrakhar Agrawal · 4:36 · 412 views
  5. LeetCode 2363 | Merge Similar Items | TreeMap | JavaSleepy Cracker · 5:30 · 340 views
  6. 2363. Merge Similar Items - LeetCode JavascriptBecoming A Better Dev (with David) · 11:22 · 297 views
  7. Steady Leetcode Progress: 2363. Merge Similar ItemsTimothy Lee Grant · 57:26 · 281 views
  8. leetcode MERGE SIMILAR ITEMSPrasun kumar · 0:25 · 256 views
  9. Leetcode 2363. Merge Similar Items - simple stuff practice - dict get method and chain list togetherCode-Yao · 4:14 · 150 views
  10. 2363. Merge Similar Items || Python || LeetcodeRohit Punetha · 4:18 · 118 views

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

def merge_similar_items(items1, items2):
    weight_map = {}
    for value, weight in items1 + items2:
        if value in weight_map:
            weight_map[value] += weight
        else:
            weight_map[value] = weight
    return sorted([[value, weight] for value, weight in weight_map.items()])
import java.util.*;

public List<int[]> mergeSimilarItems(int[][] items1, int[][] items2) {
    Map<Integer, Integer> weightMap = new HashMap<>();
    for (int[] item : items1) {
        weightMap.put(item[0], weightMap.getOrDefault(item[0], 0) + item[1]);
    }
    for (int[] item : items2) {
        weightMap.put(item[0], weightMap.getOrDefault(item[0], 0) + item[1]);
    }
    List<int[]> result = new ArrayList<>();
    for (Map.Entry<Integer, Integer> entry : weightMap.entrySet()) {
        result.add(new int[]{entry.getKey(), entry.getValue()});
    }
    result.sort(Comparator.comparingInt(a -> a[0]));
    return result;
}
#include <vector>
#include <map>
using namespace std;

vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
    map<int, int> weightMap;
    for (auto& item : items1) {
        weightMap[item[0]] += item[1];
    }
    for (auto& item : items2) {
        weightMap[item[0]] += item[1];
    }
    vector<vector<int>> result;
    for (auto& kv : weightMap) {
        result.push_back({kv.first, kv.second});
    }
    return result;
}
function mergeSimilarItems(items1, items2) {
    const weightMap = new Map();
    [...items1, ...items2].forEach(([value, weight]) => {
        weightMap.set(value, (weightMap.get(value) || 0) + weight);
    });
    return Array.from(weightMap.entries()).sort(([a], [b]) => a - b);
}
#include <stdio.h>
#include <stdlib.h>

int** mergeSimilarItems(int** items1, int items1Size, int** items2, int items2Size, int* returnSize, int** returnColumnSizes) {
    int* weightMap = calloc(1001, sizeof(int));
    for (int i = 0; i < items1Size; ++i) {
        weightMap[items1[i][0]] += items1[i][1];
    }
    for (int i = 0; i < items2Size; ++i) {
        weightMap[items2[i][0]] += items2[i][1];
    }
    int count = 0;
    for (int i = 0; i < 1001; ++i) {
        if (weightMap[i] != 0) count++;
    }
    int** result = malloc(count * sizeof(int*));
    *returnColumnSizes = malloc(count * sizeof(int));
    *returnSize = count;
    int index = 0;
    for (int i = 0; i < 1001; ++i) {
        if (weightMap[i] != 0) {
            result[index] = malloc(2 * sizeof(int));
            result[index][0] = i;
            result[index][1] = weightMap[i];
            (*returnColumnSizes)[index] = 2;
            index++;
        }
    }
    free(weightMap);
    return result;
}
using System;
using System.Collections.Generic;

public class Solution {
    public IList<int[]> MergeSimilarItems(int[][] items1, int[][] items2) {
        var weightMap = new Dictionary<int, int>();
        foreach (var item in items1) {
            if (weightMap.ContainsKey(item[0]))
                weightMap[item[0]] += item[1];
            else
                weightMap[item[0]] = item[1];
        }
        foreach (var item in items2) {
            if (weightMap.ContainsKey(item[0]))
                weightMap[item[0]] += item[1];
            else
                weightMap[item[0]] = item[1];
        }
        var result = new List<int[]>();
        foreach (var kvp in weightMap) {
            result.Add(new int[] { kvp.Key, kvp.Value });
        }
        result.Sort((a, b) => a[0].CompareTo(b[0]));
        return result;
    }
}

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.

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.

def merge_similar_items(items1, items2):
    weight_array = [0] * 1001
    for value, weight in items1 + items2:
        weight_array[value] += weight
    return [[i, weight] for i, weight in enumerate(weight_array) if weight > 0]
import java.util.*;

public List<int[]> mergeSimilarItems(int[][] items1, int[][] items2) {
    int[] weightArray = new int[1001];
    for (int[] item : items1) {
        weightArray[item[0]] += item[1];
    }
    for (int[] item : items2) {
        weightArray[item[0]] += item[1];
    }
    List<int[]> result = new ArrayList<>();
    for (int i = 1; i < weightArray.length; i++) {
        if (weightArray[i] > 0) {
            result.add(new int[]{i, weightArray[i]});
        }
    }
    return result;
}
#include <vector>
using namespace std;

vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
    int weightArray[1001] = {0};
    for (const auto& item : items1) {
        weightArray[item[0]] += item[1];
    }
    for (const auto& item : items2) {
        weightArray[item[0]] += item[1];
    }
    vector<vector<int>> result;
    for (int i = 1; i <= 1000; ++i) {
        if (weightArray[i] > 0) {
            result.push_back({i, weightArray[i]});
        }
    }
    return result;
}
function mergeSimilarItems(items1, items2) {
    const weightArray = new Array(1001).fill(0);
    [...items1, ...items2].forEach(([value, weight]) => {
        weightArray[value] += weight;
    });
    const result = [];
    for (let i = 1; i < weightArray.length; i++) {
        if (weightArray[i] > 0) {
            result.push([i, weightArray[i]]);
        }
    }
    return result;
}
#include <stdio.h>
#include <stdlib.h>

int** mergeSimilarItems(int** items1, int items1Size, int** items2, int items2Size, int* returnSize, int** returnColumnSizes) {
    int weightArray[1001] = {0};
    for (int i = 0; i < items1Size; ++i) {
        weightArray[items1[i][0]] += items1[i][1];
    }
    for (int i = 0; i < items2Size; ++i) {
        weightArray[items2[i][0]] += items2[i][1];
    }
    int count = 0;
    for (int i = 0; i < 1001; ++i) {
        if (weightArray[i] != 0) count++;
    }
    int** result = malloc(count * sizeof(int*));
    *returnColumnSizes = malloc(count * sizeof(int));
    *returnSize = count;
    int index = 0;
    for (int i = 0; i < 1001; ++i) {
        if (weightArray[i] != 0) {
            result[index] = malloc(2 * sizeof(int));
            result[index][0] = i;
            result[index][1] = weightArray[i];
            (*returnColumnSizes)[index] = 2;
            index++;
        }
    }
    return result;
}
using System.Collections.Generic;

public class Solution {
    public IList<int[]> MergeSimilarItems(int[][] items1, int[][] items2) {
        int[] weightArray = new int[1001];
        foreach (var item in items1) {
            weightArray[item[0]] += item[1];
        }
        foreach (var item in items2) {
            weightArray[item[0]] += item[1];
        }
        var result = new List<int[]>();
        for (int i = 1; i < weightArray.Length; i++) {
            if (weightArray[i] > 0) {
                result.Add(new int[] { i, weightArray[i] });
            }
        }
        return result;
    }
}

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.

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.

function mergeSimilarItems(items1: number[][], items2: number[][]): number[][] {
    const count = new Array(1001).fill(0);
    for (const [v, w] of items1) {
        count[v] += w;
    }
    for (const [v, w] of items2) {
        count[v] += w;
    }
    return [...count.entries()].filter(v => v[1] !== 0);
}
func mergeSimilarItems(items1 [][]int, items2 [][]int) (ans [][]int) {
	cnt := [1010]int{}
	for _, x := range items1 {
		cnt[x[0]] += x[1]
	}
	for _, x := range items2 {
		cnt[x[0]] += x[1]
	}
	for i, x := range cnt {
		if x > 0 {
			ans = append(ans, []int{i, x})
		}
	}
	return
}
impl Solution {
    pub fn merge_similar_items(items1: Vec<Vec<i32>>, items2: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut count = [0; 1001];
        for item in items1.iter() {
            count[item[0] as usize] += item[1];
        }
        for item in items2.iter() {
            count[item[0] as usize] += item[1];
        }
        count
            .iter()
            .enumerate()
            .filter_map(|(i, &v)| {
                if v == 0 {
                    return None;
                }
                Some(vec![i as i32, v])
            })
            .collect()
    }
}
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–

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

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.

Comments

Next problem · similarMerge Two 2D Arrays by Summing ValuesEasy
Now write it yourselfClose this page and solve Merge Similar Items in the editor, without looking.
Practise Merge Similar Items