Skip to main content
Talentd

Merge Two 2D Arrays by Summing Values - Solution & Explanation

EasyArrayHash TableTwo Pointers13 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

You are given two 2D integer arrays nums1 and nums2.

  • nums1[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.
  • nums2[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.

Each array contains unique ids and is sorted in ascending order by id.

Merge the two arrays into one array that is sorted in ascending order by id, respecting the following conditions:

  • Only ids that appear in at least one of the two arrays should be included in the resulting array.
  • Each id should be included only once and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays then its value in that array is considered to be 0.

Return the resulting array. The returned array must be sorted in ascending order 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: The resulting array contains the following:
- id = 1, the value of this id is 2 + 4 = 6.
- id = 2, the value of this id is 3.
- id = 3, the value of this id is 2.
- id = 4, the value of this id is 5 + 1 = 6.

Example 2:

Input: nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
Output: [[1,3],[2,4],[3,6],[4,3],[5,5]]
Explanation: There are no common ids, so we just include each id with its value in the resulting list.

 

Constraints:

  • 1 <= nums1.length, nums2.length <= 200
  • nums1[i].length == nums2[j].length == 2
  • 1 <= idi, vali <= 1000
  • Both arrays contain unique ids.
  • Both arrays are in strictly ascending order by id.

Approach Overview

Problem Overview: You are given two 2D arrays where each element is [id, value]. Both arrays are sorted by id. The goal is to merge them into a single sorted array where matching IDs have their values summed, and unique IDs appear as-is.

Approach 1: Hash Map / Dictionary (O(n + m) time, O(n + m) space)

This approach treats the problem as a frequency aggregation task. Iterate through both arrays and store values in a hash map keyed by id. For each pair, perform a constant-time hash lookup and add the value to the existing total. After processing both arrays, convert the map into a sorted list of [id, value] pairs.

The key insight: hash tables allow fast updates when the same ID appears in both arrays. This makes the logic simple and easy to implement. The tradeoff is extra memory proportional to the number of unique IDs. This solution heavily relies on the properties of a hash table for O(1) average updates.

Approach 2: Two Pointers Technique (O(n + m) time, O(1) extra space)

Since both arrays are already sorted by ID, you can merge them similarly to the merge step of merge sort. Use two pointers, one for each array. Compare the current IDs and append the smaller one to the result. If the IDs match, sum their values and move both pointers forward.

This avoids the extra memory used by a dictionary. Each element is processed exactly once, producing linear time complexity. The approach relies on sequential scanning and pointer movement across sorted data. This is a classic pattern when working with sorted arrays and appears frequently in two pointers problems.

The algorithm continues until one array is exhausted, then appends the remaining elements from the other array. Because the arrays are already sorted, the merged output remains sorted automatically.

Recommended for interviews: The two pointers solution is usually the expected answer. It demonstrates that you recognized the sorted property and avoided unnecessary memory. The hash map solution still shows correct reasoning and is often the fastest to implement during a timed interview. Understanding both approaches is useful when working with array merging problems and data aggregation tasks.

Approach 1: Using a Hash Map or Dictionary

This method involves utilizing a hash map (or dictionary) to store the sums of values associated with each id. As you iterate through both arrays, you'll update the map with the sums. After processing both, you can convert the map to the desired output format.

The solution uses a default dictionary to keep track of summed values by id. First, it traverses nums1, updating the dictionary. Then, it does the same for nums2. Finally, it constructs a list of lists from the sorted keys of the dictionary, each containing the id and its corresponding summed value.

Code

PythonJavaC#

Python

Java

C#

Complexity

Time Complexity: O(n + m), where n is the length of nums1 and m is the length of nums2, as we iterate through both arrays once.
Space Complexity: O(n + m) for the dictionary storing ids and summed values.

Try this approach in the editor →

Approach 2: Two Pointers Technique

Given that both arrays are sorted by id, we can effectively use a two pointers technique to traverse both arrays simultaneously. This allows us to merge them in a single pass by comparing the ids at the current pointer positions.

This C++ solution employs two pointers to traverse both arrays. It compares the ids at current positions and adds the appropriate result to the output. If ids match, their values are summed; otherwise, the entry from the array with the smaller id is added. Remaining elements are added after one array is exhausted.

Code

C++JavaScriptC

C++

JavaScript

C

Complexity

Time Complexity: O(n + m), where n and m are the lengths of the arrays.
Space Complexity: O(1), aside from the output storage.

Try this approach in the editor →

Approach 3: Counting + Enumeration

We can use a hash table or an array cnt to count the frequency of each number in the two arrays.

Then we enumerate each number in cnt from small to large. If the frequency of a number is greater than 0, we add it to the answer array.

The time complexity is O(n + m), and the space complexity is O(M). Where n and m are the lengths of the two arrays respectively; and M is the maximum value in the two arrays, in this problem, M = 1000.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using a Hash Map or Dictionary

Time Complexity: O(n + m), where n is the length of nums1 and m is the length of nums2, as we iterate through both arrays once.
Space Complexity: O(n + m) for the dictionary storing ids and summed values.

Two Pointers Technique

Time Complexity: O(n + m), where n and m are the lengths of the arrays.
Space Complexity: O(1), aside from the output storage.

Counting + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map / DictionaryO(n + m)O(n + m)General case when simplicity matters and extra memory is acceptable
Two Pointers (Sorted Merge)O(n + m)O(1)Best when arrays are already sorted and memory efficiency is required

Video Solution

Merge Two 2D Arrays by Summing Values - Leetcode 2570 - Python • NeetCodeIO • 6,187 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Merge Two 2D Arrays by Summing Values easy or hard?
Merge Two 2D Arrays by Summing Values is classified as an Easy problem on LeetCode with a high acceptance rate above 80%. The challenge mainly tests familiarity with array merging, hash maps, and the two pointers pattern.
Merge Two 2D Arrays by Summing Values Python/Java solution
Python and Java implementations typically use either a dictionary/hash map or a two-pointer merge strategy. The hash map version is concise and easy to write, while the two-pointer solution is more memory efficient and often preferred in interviews.
How to solve Merge Two 2D Arrays by Summing Values in O(n)?
Use a two pointers merge technique. Start with pointers at the beginning of both sorted arrays. Compare IDs, append the smaller one to the result, and move that pointer. When IDs match, sum their values and move both pointers. This processes each element once, giving O(n + m) time complexity.
What is the best approach for Merge Two 2D Arrays by Summing Values?
The two pointers approach is typically the best solution. Because both arrays are already sorted by ID, you can iterate through them simultaneously and merge values in O(n + m) time while using O(1) extra space. This avoids the additional memory required by a hash map.
Is Merge Two 2D Arrays by Summing Values asked at Google/Amazon/Meta?
Problems involving merging sorted arrays and aggregating values appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying patterns—two pointers and hash map aggregation—are common interview topics.
What data structure is used in Merge Two 2D Arrays by Summing Values?
Two main data structures are commonly used: arrays and hash maps. The two pointers approach works directly on sorted arrays, while the alternative approach uses a hash map (dictionary) to accumulate values for each ID.
What is the time complexity of Merge Two 2D Arrays by Summing Values?
The optimal time complexity is O(n + m), where n and m are the lengths of the two arrays. Each element is processed exactly once during the merge. Space complexity can be O(1) with the two pointers method or O(n + m) when using a hash map.

Ready to solve this problem?

Practice Merge Two 2D Arrays by Summing Values with our built-in code editor and test cases.

Practice on FleetCode
Previous

Meeting Scheduler

Next

Merge Similar Items