LeetCode 2363 - Merge Similar Items

The problem gives us two collections of items, items1 and items2, where every item is represented as a pair: The value acts like a unique identifier for an item, while weight represents that item's associated weight.

leetcodeeasyarrayhash-tablesortingordered-set

LeetCode Problem 2363

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting, Ordered Set

Solution

Problem Understanding

The problem gives us two collections of items, items1 and items2, where every item is represented as a pair:

[value, weight]

The value acts like a unique identifier for an item, while weight represents that item's associated weight. Within each individual array, values are guaranteed to be unique, meaning no value appears twice inside items1, and no value appears twice inside items2.

Our goal is to merge these two collections into a single result where items with the same value are combined. When the same value exists in both arrays, we sum their weights. If a value appears in only one array, its weight remains unchanged.

The result must be returned as a list of [value, totalWeight] pairs sorted in ascending order by value.

For example:

items1 = [[1,1],[4,5],[3,8]]
items2 = [[3,1],[1,5]]

Value 1 appears in both arrays, so its total weight becomes 1 + 5 = 6.

Value 3 also appears in both arrays, so its total weight becomes 8 + 1 = 9.

Value 4 appears only in items1, so it remains 5.

The final result becomes:

[[1,6],[3,9],[4,5]]

The constraints provide important hints about the expected solution. Each array can contain up to 1000 items, which is relatively small, but still large enough that an inefficient nested-loop solution becomes less attractive. Since valuei and weighti are bounded by 1000, we know the input size is manageable, but the uniqueness of values strongly suggests using a hash map for efficient aggregation.

A few important guarantees simplify the implementation. We never have duplicate values inside the same array, so we do not need to repeatedly merge entries from a single source. Every item always contains exactly two integers, and both arrays are guaranteed to contain at least one element.

There are several edge cases worth thinking about upfront. One case is when there is no overlap between values in items1 and items2, in which case we simply combine all items and sort them. Another case is when every value overlaps, meaning every weight must be summed. A third important case is when one array contains only a single item while the other contains many, ensuring the implementation handles highly unbalanced input sizes correctly.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to iterate through every item in items1 and search for a matching value inside items2.

For each item in items1, we scan the entirety of items2 to see whether the same value exists. If found, we sum the weights. After finishing this process, we must also scan items2 again to include values that never appeared in items1.

Finally, we sort the merged result by value.

This approach is correct because it explicitly checks every possible match between the two arrays. However, it performs redundant work. For every item in one array, we repeatedly scan the other array, leading to quadratic time complexity.

Optimal Approach, Hash Map Aggregation

The key observation is that the problem is fundamentally asking us to group weights by value.

Instead of repeatedly searching for matching values, we can use a hash map where:

key = value
value = total weight

We process both arrays once. For every item, we add its weight to the corresponding entry in the hash map.

After processing both arrays, the hash map contains the correct total weight for every unique value. We then convert the hash map into the required output format and sort it by value.

This works well because hash maps provide average O(1) insertion and lookup time, eliminating repeated scanning.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × m + k log k) O(k) Repeatedly scans one array for matching values in the other
Optimal O(n + m + k log k) O(k) Uses a hash map to aggregate weights efficiently

Here:

  • n = len(items1)
  • m = len(items2)
  • k = number of unique values

The sorting step contributes O(k log k) complexity.

Algorithm Walkthrough

Optimal Algorithm

  1. Create an empty hash map called weight_map.

This map will store the total accumulated weight for every unique value.

weight_map[value] = totalWeight
  1. Iterate through items1.

For each [value, weight], add the weight to the map:

weight_map[value] += weight

If the value does not exist yet, initialize it with 0 before adding. 3. Iterate through items2.

Repeat the same process, adding each weight into the same hash map.

This automatically merges overlapping values and preserves non-overlapping ones. 4. Convert the hash map into a result list.

For every (value, totalWeight) pair in the map, create:

[value, totalWeight]
  1. Sort the result list in ascending order by value.

Since the problem explicitly requires sorted output, this final step ensures correctness. 6. Return the sorted result.

Why it works

The correctness comes from the invariant that after processing both arrays, weight_map[v] always equals the sum of all weights associated with value v.

Every item contributes exactly once to its corresponding map entry, and because we never overwrite values incorrectly, the final map contains the precise merged totals. Sorting the result afterward guarantees compliance with the required ascending order.

Python Solution

from typing import List

class Solution:
    def mergeSimilarItems(
        self,
        items1: List[List[int]],
        items2: List[List[int]]
    ) -> List[List[int]]:

        weight_map = {}

        # Process first array
        for value, weight in items1:
            weight_map[value] = weight_map.get(value, 0) + weight

        # Process second array
        for value, weight in items2:
            weight_map[value] = weight_map.get(value, 0) + weight

        # Build and sort result
        result = []

        for value, total_weight in weight_map.items():
            result.append([value, total_weight])

        result.sort(key=lambda item: item[0])

        return result

The implementation closely follows the algorithm.

We begin by creating weight_map, a dictionary that stores cumulative weights indexed by value. The get(value, 0) call simplifies insertion because it returns 0 for unseen values.

We process items1 first and add every weight to the map. Then we repeat the same logic for items2. Since both arrays write into the same dictionary, duplicate values naturally merge through addition.

After aggregation is complete, we transform the dictionary into the required list-of-lists format. Finally, we sort using:

key=lambda item: item[0]

which sorts by the value field, satisfying the problem requirement.

Go Solution

func mergeSimilarItems(items1 [][]int, items2 [][]int) [][]int {
	weightMap := make(map[int]int)

	// Process items1
	for _, item := range items1 {
		value := item[0]
		weight := item[1]
		weightMap[value] += weight
	}

	// Process items2
	for _, item := range items2 {
		value := item[0]
		weight := item[1]
		weightMap[value] += weight
	}

	// Build result
	result := make([][]int, 0, len(weightMap))

	for value, totalWeight := range weightMap {
		result = append(result, []int{value, totalWeight})
	}

	// Sort by value
	sort.Slice(result, func(i, j int) bool {
		return result[i][0] < result[j][0]
	})

	return result
}

The Go implementation mirrors the Python approach, but there are a few language-specific details.

Go maps automatically return the zero value for missing keys, so:

weightMap[value] += weight

works without requiring an explicit existence check.

Unlike Python, Go does not provide built-in list sorting with a key function for slices of slices, so we use:

sort.Slice()

with a custom comparison function.

Integer overflow is not a concern here because the maximum possible summed weight remains small relative to Go's integer limits.

Worked Examples

Example 1

Input:

items1 = [[1,1],[4,5],[3,8]]
items2 = [[3,1],[1,5]]

Process items1

Item Hash Map State
[1,1] {1: 1}
[4,5] {1: 1, 4: 5}
[3,8] {1: 1, 4: 5, 3: 8}

Process items2

Item Hash Map State
[3,1] {1: 1, 4: 5, 3: 9}
[1,5] {1: 6, 4: 5, 3: 9}

Build Result

Unsorted:

[[1,6],[4,5],[3,9]]

Sorted:

[[1,6],[3,9],[4,5]]

Example 2

Input:

items1 = [[1,1],[3,2],[2,3]]
items2 = [[2,1],[3,2],[1,3]]

Process items1

Item Hash Map State
[1,1] {1: 1}
[3,2] {1: 1, 3: 2}
[2,3] {1: 1, 3: 2, 2: 3}

Process items2

Item Hash Map State
[2,1] {1: 1, 3: 2, 2: 4}
[3,2] {1: 1, 3: 4, 2: 4}
[1,3] {1: 4, 3: 4, 2: 4}

Final sorted result:

[[1,4],[2,4],[3,4]]

Example 3

Input:

items1 = [[1,3],[2,2]]
items2 = [[7,1],[2,2],[1,4]]

Process items1

Item Hash Map State
[1,3] {1: 3}
[2,2] {1: 3, 2: 2}

Process items2

Item Hash Map State
[7,1] {1: 3, 2: 2, 7: 1}
[2,2] {1: 3, 2: 4, 7: 1}
[1,4] {1: 7, 2: 4, 7: 1}

Final sorted result:

[[1,7],[2,4],[7,1]]

Complexity Analysis

Measure Complexity Explanation
Time O(n + m + k log k) Process both arrays once, then sort unique values
Space O(k) Hash map stores one entry per unique value

The algorithm visits every item in items1 and items2 exactly once, contributing O(n + m) time. The final sorting step dominates when there are many unique values, costing O(k log k).

Space complexity is O(k) because the hash map stores one entry for each distinct value across both arrays.

Test Cases

solution = Solution()

# Example 1
assert solution.mergeSimilarItems(
    [[1, 1], [4, 5], [3, 8]],
    [[3, 1], [1, 5]]
) == [[1, 6], [3, 9], [4, 5]]  # overlapping and unique values

# Example 2
assert solution.mergeSimilarItems(
    [[1, 1], [3, 2], [2, 3]],
    [[2, 1], [3, 2], [1, 3]]
) == [[1, 4], [2, 4], [3, 4]]  # all values overlap

# Example 3
assert solution.mergeSimilarItems(
    [[1, 3], [2, 2]],
    [[7, 1], [2, 2], [1, 4]]
) == [[1, 7], [2, 4], [7, 1]]  # one unique value in second array

# No overlapping values
assert solution.mergeSimilarItems(
    [[1, 2], [3, 4]],
    [[5, 6], [7, 8]]
) == [[1, 2], [3, 4], [5, 6], [7, 8]]  # merge without additions

# Single element arrays with overlap
assert solution.mergeSimilarItems(
    [[1, 10]],
    [[1, 20]]
) == [[1, 30]]  # smallest valid input

# Single element arrays without overlap
assert solution.mergeSimilarItems(
    [[2, 5]],
    [[1, 7]]
) == [[1, 7], [2, 5]]  # sorting correctness

# Maximum weight accumulation scenario
assert solution.mergeSimilarItems(
    [[1000, 1000]],
    [[1000, 1000]]
) == [[1000, 2000]]  # large values

# Larger mixed overlap
assert solution.mergeSimilarItems(
    [[1, 5], [2, 10], [4, 7]],
    [[2, 3], [3, 8], [4, 1]]
) == [[1, 5], [2, 13], [3, 8], [4, 8]]  # mixed merge case
Test Why
Example 1 Validates overlapping and unique values
Example 2 Validates complete overlap
Example 3 Validates partial overlap
No overlapping values Ensures independent items remain unchanged
Single element overlap Tests minimum input size
Single element non-overlap Verifies sorting behavior
Maximum weight accumulation Tests upper-bound style values
Larger mixed overlap Validates realistic mixed scenarios

Edge Cases

No overlapping values

One important edge case occurs when the two arrays contain completely different values. A naive implementation might incorrectly assume every item has a match and accidentally skip unmatched entries.

For example:

items1 = [[1,2]]
items2 = [[3,4]]

The implementation handles this correctly because every item is independently inserted into the hash map. Since no values overlap, no additions occur, and both entries remain intact.

Every value overlaps

Another important case is when every value appears in both arrays. A buggy implementation could accidentally overwrite weights instead of summing them.

For example:

items1 = [[1,2],[2,3]]
items2 = [[1,5],[2,4]]

The dictionary update logic:

weight_map[value] = weight_map.get(value, 0) + weight

ensures weights are accumulated rather than replaced, producing the correct totals.

Already unsorted input

The input arrays are not guaranteed to be sorted. A naive implementation might accidentally return items in insertion order, which would violate the problem requirement.

For example:

items1 = [[5,1],[1,2]]
items2 = [[3,4]]

Even though values are encountered in an arbitrary order, the final sorting step guarantees the output is always returned in ascending order by value.

Highly unbalanced input sizes

One array may contain only one item while the other contains many. Some implementations can accidentally assume balanced iteration.

Because this solution processes each array independently, it works correctly regardless of size differences. Every item contributes exactly once to the hash map, ensuring correctness even when one array is much larger than the other.