Merge Similar Items — Editorial

Opening the reading…

Intuitionwhy each value needs exactly one accumulated entry

The output has one row per distinct value, not one row per input item. A value may occur once in each input array, so the natural state is a running total indexed by value: whenever you read [value, weight], add weight to the total stored for value. Processing both arrays into the same state automatically merges values that appear in both and preserves values that appear in only one.

The output also has an ordering requirement. A map keeps its keys in ascending order while you insert them, so iterating over the completed map visits values in exactly the order the answer needs. This means the solution performs two accumulation passes and one ordered output pass, with no special case for values missing from either array.

Approachaccumulate first, then read keys in order

Create an ordered map from value to total weight, because each map key represents one output row and ordered iteration will satisfy the ascending-value requirement.

Visit every pair in items1 and add its weight to the entry for its value, because assignment would discard an earlier contribution if the same value appears in the other array.

Visit every pair in items2 and add its weight to the same map, so values shared by both arrays are combined while values present in only one array remain included.

Create an empty answer array after both inputs have been processed, because the final weight for every value is known only after both accumulation passes finish.

Iterate through the map from begin to end and append [value, total weight] for each entry, because the ordered map guarantees that no separate sort is needed.

Return the answer array, whose rows are unique by value and already arranged in ascending order.

Complexitythe logarithmic cost comes from ordered-map updates

MEASURE	BOUND	WHY
Time	O((n + m) log(n + m))	The two input passes perform n + m map updates, each taking logarithmic time in the number of stored keys; the output pass visits each distinct key once, and there are at most n + m of them, which is no larger than the stated bound.
Space	O(n + m) extra	The map stores one entry per distinct value and the temporary working structure therefore uses at most n + m entries. The returned array is required output and is excluded from extra space; in the worst case every input value is different, so the map reaches that bound.

Here n is items1.length and m is items2.length; the number of distinct values is at most n + m.

Annotated solutionC++ · ordered map · accumulation and sorted output in one structure

CPPStore each value's accumulated weight in an ordered map, then emit the map in ascending key order.

#include <map>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
        map<int, int> totalWeight;

        for (const vector<int>& item : items1) {
            totalWeight[item[0]] += item[1];
        }

        for (const vector<int>& item : items2) {
            totalWeight[item[0]] += item[1];
        }

        vector<vector<int>> answer;
        for (const auto& entry : totalWeight) {
            answer.push_back({entry.first, entry.second});
        }

        return answer;
    }
};

The += operator is the essential operation in both loops: the first occurrence creates a map entry with the item weight, and a later occurrence increases that entry. The final loop does not sort the answer because map iteration already follows increasing key order; replacing the map with an unordered structure would require an explicit sort.

The bounded-array alternativean optimisation that uses the value limit instead of tree nodes

The constraints bound every value from 1 through 1000, so you can use an array as a direct table from value to total weight. This changes each update from logarithmic map work to constant time and makes the final ascending order automatic when you scan values from 1 to 1000. It is an optimisation for these bounds, but it is less general: it depends on the value range staying small.

CPPUse the constrained value range as an index table and scan it in ascending order.

#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
        const int maxValue = 1000;
        vector<int> totalWeight(maxValue + 1, 0);

        for (const vector<int>& item : items1) {
            totalWeight[item[0]] += item[1];
        }

        for (const vector<int>& item : items2) {
            totalWeight[item[0]] += item[1];
        }

        vector<vector<int>> answer;
        for (int value = 1; value <= maxValue; ++value) {
            if (totalWeight[value] > 0) {
                answer.push_back({value, totalWeight[value]});
            }
        }

        return answer;
    }
};

With this version, the time is O(n + m + V) and the extra space is O(V), where V is the largest allowed value range, here 1000. The scan is necessary even when some values never appear, because it is what both discovers present values and emits them in order. For an unconstrained or very sparse value range, the ordered map is the safer choice.