DSA SheetEasy
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

Merge Two 2D Arrays by Summing Values

EasyEditorial · 5 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

Two sorted 2D arrays being merged with two pointersThe picture places two sorted rows of id-value pairs one above the other. Pointer i marks the first unprocessed pair in the upper row, and pointer j marks the first unprocessed pair in the lower row. A smaller id is copied from its row and its pointer moves right; matching ids are joined into one result pair and both pointers move right. The result row stays sorted because no unprocessed pair can have a smaller id than the pair chosen next.(1,10)(3,5)(7,2)(1,2)(2,8)(7,4)(1,12)(2,8)(3,5)(7,6)102copy 8nums1 — sortednums2 — sortedresultijequal id → emit once: 10 + 2 = 12 | smaller current id → copyimmediatelyBoth pointers advance only forward after consuming a row.

Approach

  1. 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.
  2. 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.
  3. If nums1[i][0] is smaller, append nums1[i] and increment i, because the sorted order proves this id cannot appear later in nums2.
  4. 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.
  5. 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.
  6. After the main loop, append every remaining pair from nums1, because nums2 is exhausted or all earlier ids have already been handled.
  7. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(1) extraThe 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.

Common mistakestwo wrong code shapes that change the merge