Merge Two 2D Arrays by Summing Values — Easy Problem & Solution

Problem statement

Each of nums1 and nums2 holds [id, value] pairs sorted by strictly increasing id, with no id repeated inside one array.

Merge them: every id that appears in either array appears once in the result, carrying the sum of its values. Return the merged array sorted by id.

Example 1

Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
Output: [[1,6],[2,3],[3,2],[4,6]]
Explanation: Ids 1 and 4 appear in both, so their values add.

Example 2

Input: nums1 = [[2,4],[3,6]], nums2 = [[1,3],[4,3]]
Output: [[1,3],[2,4],[3,6],[4,3]]
Explanation: No id is shared.

Example 3

Input: nums1 = [[1,1]], nums2 = [[1,1]]
Output: [[1,2]]

Constraints

• 1 <= nums1.length, nums2.length <= 200
• Each inner array has length 2
• 1 <= id <= 1000
• 1 <= value <= 1000
• Ids within each array are strictly increasing.

How to solve Merge Two 2D Arrays by Summing Values

Sorted inputs make a single linear merge sufficient: compare the two front ids and either combine them or take the smaller one.

Approach

1. Walk i over nums1 and j over nums2.
2. On equal ids, push [id, v1 + v2] and advance both.
3. Otherwise push the pair with the smaller id and advance that pointer.
4. Append whatever remains of either array.

Why it works

Because each array's ids strictly increase, the smaller front id can never appear again later in the other array, so emitting it immediately is safe and the output stays sorted.

Complexity

• Time — O(n + m)
• Space — O(n + m) for the output

Pitfalls

• Forgetting the tail loops drops the longer array's remainder.
• Advancing only one pointer on an equal id emits that id twice.
• Concatenating and sorting works but throws away the inputs' existing order.

Reference solution

Python

from typing import List

def mergeArrays(nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
    out = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i][0] == nums2[j][0]:
            out.append([nums1[i][0], nums1[i][1] + nums2[j][1]])
            i += 1
            j += 1
        elif nums1[i][0] < nums2[j][0]:
            out.append(list(nums1[i]))
            i += 1
        else:
            out.append(list(nums2[j]))
            j += 1
    while i < len(nums1):
        out.append(list(nums1[i]))
        i += 1
    while j < len(nums2):
        out.append(list(nums2[j]))
        j += 1
    return out

JavaScript

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

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy