LeetCode 2570 - Merge Two 2D Arrays by Summing Values

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Two Pointers

Solution

Problem Understanding

The problem gives us two sorted 2D integer arrays, nums1 and nums2, where every element is a pair of integers in the form [id, value].

Each id uniquely identifies an entry inside its own array, and the corresponding value represents that id's associated number. Since both arrays are already sorted in ascending order by id, we can take advantage of this ordering to process them efficiently.

The task is to merge both arrays into a single sorted array while following a few important rules:

Every id that appears in either array must appear exactly once in the result.
If an id exists in both arrays, its values should be added together.
If an id exists in only one array, we treat the missing value from the other array as 0.
The final result must remain sorted in ascending order by id.

For example, if nums1 contains [1,2] and nums2 contains [1,4], then the merged result should contain [1,6] because 2 + 4 = 6.

The constraints are relatively small:

1 <= nums1.length, nums2.length <= 200
Values and ids are bounded by 1000
Each array has unique ids
Both arrays are already sorted

These constraints tell us that even moderately inefficient solutions would still pass, but the sorted nature of the arrays strongly suggests a more elegant and efficient approach.

Several edge cases are worth considering upfront.

If the arrays have completely disjoint ids, the result should simply contain all entries in sorted order. If every id overlaps, we must correctly sum every pair. Another important case is when one array finishes before the other, since we still need to append the remaining elements. The problem guarantees unique ids within each array, which removes the need to handle duplicate ids inside a single list.

Approaches

Brute Force Approach

A straightforward approach is to use a hash map.

We iterate through nums1 and store each id → value pair inside a dictionary. Then, we iterate through nums2. If an id already exists, we add its value to the existing one. Otherwise, we insert it into the dictionary.

After processing both arrays, we sort the dictionary keys and reconstruct the answer array.

This works because the hash map guarantees that each id appears only once, and summing values is easy during insertion. However, the downside is that we ignore the fact that both input arrays are already sorted. We end up performing an additional sorting step.

Optimal Approach, Two Pointers

The key observation is that both arrays are already sorted by id.

Whenever two sequences are sorted, we can often process them efficiently using the same idea as the merge step in merge sort. We maintain one pointer for each array and compare the current ids.

There are three possibilities:

If the ids are equal, we sum their values and move both pointers.
If one id is smaller, we add that entry directly to the answer and move only that pointer.
After one array is exhausted, we append all remaining entries from the other array.

Because each element is processed exactly once, we avoid sorting altogether and preserve ascending order naturally.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((n + m) log(n + m))	O(n + m)	Uses a hash map, then sorts ids afterward
Optimal	O(n + m)	O(n + m)	Uses two pointers to merge already sorted arrays

Here, n = len(nums1) and m = len(nums2).

Algorithm Walkthrough

Initialize two pointers, i and j, both starting at 0.

The pointer i tracks the current position in nums1, while j tracks the current position in nums2. 2. Create an empty result array.

This will store the merged entries in sorted order. 3. Compare the current ids from both arrays.

Let id1 = nums1[i][0] and id2 = nums2[j][0].

If id1 == id2, both arrays contain the same id. Add their values together and append [id1, summed_value] to the result. Then move both pointers forward. 4. Handle the smaller id.

If id1 < id2, then the current id in nums1 does not exist in nums2 at this position, because both arrays are sorted. We can safely append nums1[i] to the result and move i forward.

Similarly, if id2 < id1, append nums2[j] and move j forward. 5. Continue until one array is fully processed.

The main comparison loop stops when either pointer reaches the end of its array. 6. Append remaining elements.

If nums1 still has unprocessed elements, append them all.

If nums2 still has unprocessed elements, append them all. 7. Return the result.

Since elements were added in ascending order during traversal, the result is already sorted.

Why it works

The correctness comes from the sorted property of both arrays. At every step, we process the smallest remaining id among the two arrays. If ids match, we combine them immediately. If one id is smaller, we know it cannot appear later in the other array because both arrays are strictly increasing. Therefore, adding it immediately preserves correctness and sorted order.

Python Solution

from typing import List

class Solution:
    def mergeArrays(
        self,
        nums1: List[List[int]],
        nums2: List[List[int]]
    ) -> List[List[int]]:
        i = 0
        j = 0
        merged = []

        while i < len(nums1) and j < len(nums2):
            id1, value1 = nums1[i]
            id2, value2 = nums2[j]

            if id1 == id2:
                merged.append([id1, value1 + value2])
                i += 1
                j += 1
            elif id1 < id2:
                merged.append([id1, value1])
                i += 1
            else:
                merged.append([id2, value2])
                j += 1

        while i < len(nums1):
            merged.append(nums1[i])
            i += 1

        while j < len(nums2):
            merged.append(nums2[j])
            j += 1

        return merged

The implementation closely follows the two-pointer algorithm.

We begin by initializing i and j, which track positions inside nums1 and nums2. The merged list stores the final answer.

The main while loop runs as long as both arrays still contain unprocessed elements. During each iteration, we extract the current id-value pairs and compare their ids.

If both ids match, we combine the values and advance both pointers. If one id is smaller, we append it immediately because the sorted property guarantees it cannot appear later in the other array.

After the main loop finishes, one array may still contain leftover elements. Since those elements are already sorted and have no matching ids left, we append them directly.

Finally, we return the completed merged array.

Go Solution

func mergeArrays(nums1 [][]int, nums2 [][]int) [][]int {
	i, j := 0, 0
	result := [][]int{}

	for i < len(nums1) && j < len(nums2) {
		id1, value1 := nums1[i][0], nums1[i][1]
		id2, value2 := nums2[j][0], nums2[j][1]

		if id1 == id2 {
			result = append(result, []int{id1, value1 + value2})
			i++
			j++
		} else if id1 < id2 {
			result = append(result, []int{id1, value1})
			i++
		} else {
			result = append(result, []int{id2, value2})
			j++
		}
	}

	for i < len(nums1) {
		result = append(result, nums1[i])
		i++
	}

	for j < len(nums2) {
		result = append(result, nums2[j])
		j++
	}

	return result
}

The Go implementation mirrors the Python logic closely. Since Go uses slices instead of dynamic Python lists, we build the answer using append.

There are no special concerns around integer overflow because the maximum possible summed value is only 2000, which easily fits within Go's int type.

Go distinguishes between nil slices and empty slices, but in this problem either representation is valid since the constraints guarantee non-empty inputs. The function naturally returns an initialized slice.

Worked Examples

Example 1

Input

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

Step	i	j	nums1[i]	nums2[j]	Action	Result
1	0	0	[1,2]	[1,4]	Same id, sum values	[[1,6]]
2	1	1	[2,3]	[3,2]	2 < 3, append nums1	[[1,6],[2,3]]
3	2	1	[4,5]	[3,2]	3 < 4, append nums2	[[1,6],[2,3],[3,2]]
4	2	2	[4,5]	[4,1]	Same id, sum values	[[1,6],[2,3],[3,2],[4,6]]

Both pointers reach the end, so the algorithm stops.

Output

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

Example 2

Input

nums1 = [[2,4],[3,6],[5,5]]
nums2 = [[1,3],[4,3]]

Step	i	j	nums1[i]	nums2[j]	Action	Result
1	0	0	[2,4]	[1,3]	1 < 2, append nums2	[[1,3]]
2	0	1	[2,4]	[4,3]	2 < 4, append nums1	[[1,3],[2,4]]
3	1	1	[3,6]	[4,3]	3 < 4, append nums1	[[1,3],[2,4],[3,6]]
4	2	1	[5,5]	[4,3]	4 < 5, append nums2	[[1,3],[2,4],[3,6],[4,3]]

nums2 is exhausted, so we append the remaining element from nums1.

Final Result

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each element from both arrays is visited exactly once
Space	O(n + m)	The output array may contain every element from both inputs

The algorithm is linear because both pointers only move forward and never revisit elements. Since every pair from both arrays is processed exactly once, the total amount of work is proportional to n + m.

The extra space complexity comes from storing the merged result. In the worst case, no ids overlap, so the output contains all n + m elements.

Test Cases

sol = Solution()

# Example 1, overlapping ids
assert sol.mergeArrays(
    [[1, 2], [2, 3], [4, 5]],
    [[1, 4], [3, 2], [4, 1]]
) == [[1, 6], [2, 3], [3, 2], [4, 6]]

# Example 2, no overlapping ids
assert sol.mergeArrays(
    [[2, 4], [3, 6], [5, 5]],
    [[1, 3], [4, 3]]
) == [[1, 3], [2, 4], [3, 6], [4, 3], [5, 5]]

# Single overlapping element
assert sol.mergeArrays(
    [[1, 5]],
    [[1, 7]]
) == [[1, 12]]  # exact id match

# No overlap with smallest inputs
assert sol.mergeArrays(
    [[2, 10]],
    [[1, 20]]
) == [[1, 20], [2, 10]]  # preserves sorting

# nums1 completely before nums2
assert sol.mergeArrays(
    [[1, 1], [2, 2]],
    [[3, 3], [4, 4]]
) == [[1, 1], [2, 2], [3, 3], [4, 4]]

# nums2 completely before nums1
assert sol.mergeArrays(
    [[5, 5], [6, 6]],
    [[1, 1], [2, 2]]
) == [[1, 1], [2, 2], [5, 5], [6, 6]]

# All ids overlap
assert sol.mergeArrays(
    [[1, 1], [2, 2], [3, 3]],
    [[1, 9], [2, 8], [3, 7]]
) == [[1, 10], [2, 10], [3, 10]]

# One array exhausted early
assert sol.mergeArrays(
    [[1, 2], [1000, 5]],
    [[1, 3]]
) == [[1, 5], [1000, 5]]

# Maximum id values
assert sol.mergeArrays(
    [[1000, 1000]],
    [[1000, 1000]]
) == [[1000, 2000]]  # upper boundary values

Test	Why
Example 1	Validates overlapping ids and summation
Example 2	Validates completely disjoint ids
Single overlapping element	Tests smallest overlapping input
No overlap with smallest inputs	Tests ordering with minimal size
nums1 completely before nums2	Ensures leftovers append correctly
nums2 completely before nums1	Verifies sorted merge from reverse ranges
All ids overlap	Confirms repeated summation logic
One array exhausted early	Tests leftover processing
Maximum id values	Verifies upper constraint handling

Edge Cases

Completely Disjoint IDs

A common source of bugs is assuming ids always overlap. For example:

nums1 = [[1,2],[2,3]]
nums2 = [[5,10]]

A naive implementation might incorrectly attempt to match unrelated ids. The two-pointer method handles this naturally by always appending the smaller id and moving forward. Since no ids match, all elements are simply merged in sorted order.

One Array Finishes Early

Another tricky case occurs when one array becomes exhausted before the other.

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

If we stop immediately after the main comparison loop, we would lose remaining elements. The implementation avoids this bug with two cleanup loops that append all remaining entries after one pointer reaches the end.

Every ID Overlaps

When every id exists in both arrays:

nums1 = [[1,1],[2,2]]
nums2 = [[1,5],[2,10]]

A buggy implementation might accidentally duplicate ids instead of summing them. Our solution explicitly checks for equality and merges both values into a single entry before advancing both pointers, guaranteeing each id appears exactly once.

Single Element Arrays

Minimal inputs are another important edge case:

nums1 = [[1,5]]
nums2 = [[1,10]]

The implementation correctly handles this because the main loop still executes once, detects matching ids, sums the values, and terminates cleanly without any special-case logic.