Merge Two 2D Arrays by Summing Values

Easy
749.

Merge Two 2D Arrays by Summing Values

Merge Two 2D Arrays by Summing Values is an easy coding problem on arrays and two pointers, asked in Amazon, TCS and Infosys interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} nums1
 * @param {number[][]} nums2
 * @return {number[][]}
 */
var mergeArrays = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Merge Two 2D Arrays by Summing Values solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Merge Two 2D Arrays by Summing Values is an easy coding problem on arrays and two pointers, asked in Amazon, TCS and Infosys interviews.

  • Difficulty: Easy
  • Topics: Arrays, Two Pointers
  • Asked at: Amazon, TCS, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Merge Two 2D Arrays by Summing Values

  1. Hint 1

    Both inputs are already sorted by id, so this is the merge step of merge sort.

  2. Hint 2

    When the two front ids match, emit their sum and advance both pointers.

  3. Hint 3

    Otherwise emit the smaller id and advance only that pointer.

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

Java

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

C++

vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
    vector<vector<int>> out;
    size_t i = 0, j = 0;
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i][0] == nums2[j][0]) {
            out.push_back({ nums1[i][0], nums1[i][1] + nums2[j][1] });
            i++;
            j++;
        } else if (nums1[i][0] < nums2[j][0]) {
            out.push_back({ nums1[i][0], nums1[i][1] });
            i++;
        } else {
            out.push_back({ nums2[j][0], nums2[j][1] });
            j++;
        }
    }
    while (i < nums1.size()) { out.push_back({ nums1[i][0], nums1[i][1] }); i++; }
    while (j < nums2.size()) { out.push_back({ nums2[j][0], nums2[j][1] }); j++; }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique