Merge Two 2D Arrays by Summing Values

easy two pointers merge sorted arrays

Problem

You are given two 2D arrays nums1 and nums2, where each entry is [id, val]. Each array has unique ids and is sorted in ascending order by id. Merge them into one array sorted by id: every id from either array appears exactly once, and its value is the sum of its values across both arrays (treat a missing id as value 0).

Inputnums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]

Output[[1,6],[2,3],[3,2],[4,6]]

id 1 → 2+4=6, id 2 → 3, id 3 → 2, id 4 → 5+1=6.

nums1 (id:val, comma-separated)

nums2 (id:val, comma-separated)

def merge_arrays(nums1, nums2):
    i, j = 0, 0
    res = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i][0] == nums2[j][0]:
            res.append([nums1[i][0], nums1[i][1] + nums2[j][1]])
            i += 1
            j += 1
        elif nums1[i][0] < nums2[j][0]:
            res.append(nums1[i])
            i += 1
        else:
            res.append(nums2[j])
            j += 1
    while i < len(nums1):
        res.append(nums1[i])
        i += 1
    while j < len(nums2):
        res.append(nums2[j])
        j += 1
    return res

function mergeArrays(nums1, nums2) {
  let i = 0, j = 0;
  const res = [];
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i][0] === nums2[j][0]) {
      res.push([nums1[i][0], nums1[i][1] + nums2[j][1]]);
      i++; j++;
    } else if (nums1[i][0] < nums2[j][0]) {
      res.push(nums1[i]);
      i++;
    } else {
      res.push(nums2[j]);
      j++;
    }
  }
  while (i < nums1.length) res.push(nums1[i++]);
  while (j < nums2.length) res.push(nums2[j++]);
  return res;
}

int[][] mergeArrays(int[][] nums1, int[][] nums2) {
    List<int[]> res = new ArrayList<>();
    int i = 0, j = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i][0] == nums2[j][0]) {
            res.add(new int[]{nums1[i][0], nums1[i][1] + nums2[j][1]});
            i++; j++;
        } else if (nums1[i][0] < nums2[j][0]) {
            res.add(nums1[i++]);
        } else {
            res.add(nums2[j++]);
        }
    }
    while (i < nums1.length) res.add(nums1[i++]);
    while (j < nums2.length) res.add(nums2[j++]);
    return res.toArray(new int[0][]);
}

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

Explanation

Both inputs are already sorted by id and contain unique ids, so this is the classic merge step of merge sort. We walk both arrays at once with two pointers, i into nums1 and j into nums2, always comparing the id at each cursor.

At every comparison there are three cases. If the two ids are equal, this id lives in both arrays, so we emit one entry whose value is the sum of the two values and advance both pointers. If nums1[i] has the smaller id, we emit it and advance only i. Otherwise nums2[j] has the smaller id, so we emit it and advance only j.

Because we always take the smaller id (or the merged equal id) next, the output is produced in ascending id order automatically — no sorting needed afterward.

When one array is exhausted, its pointer can no longer advance, so we drain whatever remains in the other array. Those leftover ids are all larger than everything emitted so far, so appending them keeps the result sorted.

Each element of each array is visited exactly once, giving linear time. The only extra space is the output list itself.

Time: O(n + m) Space: O(n + m)