Merge Two 2D Arrays by Summing Values — Editorial

Opening the reading…

Intuitionthe sorted order tells you which pair is safe to consume

The result must be sorted by id, and both input arrays already provide their ids in sorted order. Compare the first unprocessed pair in each array. If one id is smaller, it cannot match any later id in the other array, so you can place it in the result and move past it safely.

If the ids are equal, they describe the same identifier and must become one result pair with the two values added. When one array runs out, every remaining pair in the other array is already larger than everything you have processed, so you append those pairs without more comparisons.

Approach

Create an empty result and set i and j to the first positions, because every pair is initially unprocessed and the result must preserve ascending id order.

While both pointers are inside their arrays, compare nums1[i][0] and nums2[j][0], because only these two current ids can be the next id in the merged result.

If nums1[i][0] is smaller, append nums1[i] and increment i, because the sorted order proves this id cannot appear later in nums2.

If nums2[j][0] is smaller, append nums2[j] and increment j, because its id is the smallest available and leaving it behind would break the result order.

If the ids are equal, append one pair containing that id and the sum of both values, then increment both pointers so the shared id is not emitted twice.

After the main loop, append every remaining pair from nums1, because nums2 is exhausted or all earlier ids have already been handled.

Append every remaining pair from nums2 for the same reason, ensuring that pairs after the shorter array ends are not lost.

Complexityone pass over both input arrays

MEASURE	BOUND	WHY
Time	O(n + m)	Each pointer only moves forward, and each input pair is inspected and appended at most once. Equal ids advance both pointers together, while disjoint ids still cause each pair to be consumed once, so even the worst case of no overlap remains linear.
Space	O(1) extra	The result is required output and is excluded. Apart from that output, the algorithm stores only two indices and a constant number of temporary values, so the working memory does not grow with n or m.

Here n is nums1.length and m is nums2.length. The output itself is excluded from the extra-space bound.

Annotated solutionC++ · two pointers · complete judge-ready implementation

CPPAdvance the pointer for the smaller id, or advance both pointers after summing equal ids.

#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        vector<vector<int>> res;
        int i = 0;
        int j = 0;

        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i][0] < nums2[j][0]) {
                res.push_back(nums1[i]);
                i++;
            } else if (nums1[i][0] > nums2[j][0]) {
                res.push_back(nums2[j]);
                j++;
            } else {
                res.push_back({nums1[i][0], nums1[i][1] + nums2[j][1]});
                i++;
                j++;
            }
        }

        while (i < nums1.size()) {
            res.push_back(nums1[i]);
            i++;
        }

        while (j < nums2.size()) {
            res.push_back(nums2[j]);
            j++;
        }

        return res;
    }
};

The main loop stops as soon as either array is exhausted, which keeps every comparison valid. The two tail loops are not separate merging logic: once one side is empty, the remaining side is already sorted and cannot conflict with anything still unseen. In the equal-id branch, constructing a fresh pair is important because copying either input pair would discard one of the two values.