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 <= 200Each inner array has length 21 <= id <= 10001 <= value <= 1000Ids within each array are strictly increasing.
Hints for Merge Two 2D Arrays by Summing Values
Hint 1
Both inputs are already sorted by id, so this is the merge step of merge sort.
Hint 2
When the two front ids match, emit their sum and advance both pointers.
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
- Walk
iovernums1andjovernums2. - On equal ids, push
[id, v1 + v2]and advance both. - Otherwise push the pair with the smaller id and advance that pointer.
- 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 outJava
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