Merge Two 2D Arrays by Summing Values

Easy

#2350Time: O((N + M) * log(K)), where N and M are the lengths of the input arrays and K is the number of unique IDs (K <= N + M). Each insertion/update operation in a `TreeMap` takes O(log K) time.Space: O(N + M), where N and M are the lengths of `nums1` and `nums2` respectively. This space is required to store the entries in the `TreeMap` and the resulting list.

Patterns

Two Pointers

Data structures

Array Hash Table

Prompt

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

nums1[i] = [id_i, val_i] indicate that the number with the id id_i has a value equal to val_i.
nums2[i] = [id_i, val_i] indicate that the number with the id id_i has a value equal to val_i.

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 assume its value in that array 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 <= id_i, val_i <= 1000
Both arrays contain unique ids.
Both arrays are in strictly ascending order by id.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a TreeMap to aggregate the values for each ID. A TreeMap is a sorted map data structure that maintains its entries in ascending order of keys. We can iterate through both input arrays and populate the TreeMap, using the ID as the key and the sum of values as the value. The TreeMap naturally handles the sorting requirement, making the final conversion to a sorted 2D array straightforward.

Algorithm

Initialize a TreeMap<Integer, Integer> to store ID-to-value mappings. A TreeMap is used because it automatically keeps the keys (IDs) in sorted order.
Iterate through the first array, nums1. For each pair [id, val], add it to the map.
Iterate through the second array, nums2. For each pair [id, val], update the map. If the ID already exists, add the new value to the existing value. If it doesn't exist, insert it. The map.put(id, map.getOrDefault(id, 0) + val) operation handles both cases efficiently.
After processing both arrays, the TreeMap will contain all the unique IDs from both arrays, sorted, with their corresponding summed values.
Create a new list to store the result in the required int[] format.
Iterate through the entries of the TreeMap and add each [id, value] pair to the result list.
Convert the result list to a 2D integer array and return it.

Walkthrough

The core idea is to use a data structure that can both store key-value pairs and keep them sorted by the key. A TreeMap in Java is perfect for this.

We first declare a TreeMap<Integer, Integer>.
We iterate through nums1 and put each [id, value] pair into the map.
Then, we iterate through nums2. For each [id, value] pair, we update the map. The getOrDefault method is particularly useful here. map.put(id, map.getOrDefault(id, 0) + value) will fetch the current value for the given id (or 0 if it's not present), add the new value to it, and put the result back into the map. This correctly handles both new IDs and existing IDs.
Because we used a TreeMap, the entries are already sorted by ID. The final step is to iterate through the map's entries and construct the final 2D array.

1import java.util.ArrayList;2import java.util.List;3import java.util.Map;4import java.util.TreeMap;5 6class Solution {7    public int[][] mergeArrays(int[][] nums1, int[][] nums2) {8        Map<Integer, Integer> map = new TreeMap<>();9 10        // Process the first array11        for (int[] item : nums1) {12            map.put(item[0], item[1]);13        }14 15        // Process the second array, summing values for common IDs16        for (int[] item : nums2) {17            map.put(item[0], map.getOrDefault(item[0], 0) + item[1]);18        }19 20        // Convert the map to the result 2D array21        List<int[]> resultList = new ArrayList<>();22        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {23            resultList.add(new int[]{entry.getKey(), entry.getValue()});24        }25 26        return resultList.toArray(new int[resultList.size()][]);27    }28}

Complexity

Time

O((N + M) * log(K)), where N and M are the lengths of the input arrays and K is the number of unique IDs (K <= N + M). Each insertion/update operation in a `TreeMap` takes O(log K) time.

Space

O(N + M), where N and M are the lengths of `nums1` and `nums2` respectively. This space is required to store the entries in the `TreeMap` and the resulting list.

Trade-offs

Pros

The logic is straightforward and easy to implement.
The use of TreeMap automatically handles the sorting of IDs, simplifying the code.
This approach would work correctly even if the input arrays were not sorted.

Cons

Less efficient in terms of time complexity compared to the two-pointer approach due to the logarithmic cost of map operations.
It does not leverage the pre-sorted nature of the input arrays, which is a key property of the problem.

This approach leverages the fact that both input arrays are already sorted by ID. We can use a two-pointer technique, similar to the merge step in merge sort, to build the final merged array in a single pass. This is the most efficient method as it avoids the overhead of map data structures or explicit sorting.

Algorithm

Initialize two pointers, i for nums1 and j for nums2, both starting at 0.
Initialize an empty list, result, to store the merged [id, value] pairs.
Loop while both pointers i and j are within the bounds of their respective arrays.
In each iteration, compare nums1[i][0] and nums2[j][0]:
- If nums1[i][0] == nums2[j][0]: The IDs are the same. Add a new entry [id, sum_of_values] to the result list. Increment both i and j.
- If nums1[i][0] < nums2[j][0]: The ID from nums1 is smaller. Add the entry nums1[i] to the result list. Increment only i.
- If nums1[i][0] > nums2[j][0]: The ID from nums2 is smaller. Add the entry nums2[j] to the result list. Increment only j.
After the main loop, one of the arrays might have remaining elements. Append all remaining elements from nums1 (if any) to the result.
Append all remaining elements from nums2 (if any) to the result.
Convert the result list to a 2D array and return it.

Walkthrough

By maintaining a pointer for each array, we can iterate through them simultaneously. We compare the IDs at the current pointers and decide which element to add to our result list. This ensures that the result list is built in sorted order from the beginning.

We start with pointers i = 0 for nums1 and j = 0 for nums2.
We compare id1 = nums1[i][0] and id2 = nums2[j][0].
If they are equal, we've found a common ID. We sum their values and add the new pair to our result. Since we've processed both elements, we advance both pointers i and j.
If id1 is smaller, it means id1 comes first in the sorted merged list. We add the pair from nums1 to our result and advance only pointer i to consider the next element in nums1.
If id2 is smaller, we do the opposite: add the pair from nums2 and advance j.
This process continues until we exhaust one of the arrays. Any remaining elements in the other array must have IDs greater than all processed IDs, so we can simply append them to the result.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int[][] mergeArrays(int[][] nums1, int[][] nums2) {6        List<int[]> result = new ArrayList<>();7        int i = 0, j = 0;8        int n1 = nums1.length;9        int n2 = nums2.length;10 11        while (i < n1 && j < n2) {12            if (nums1[i][0] == nums2[j][0]) {13                result.add(new int[]{nums1[i][0], nums1[i][1] + nums2[j][1]});14                i++;15                j++;16            } else if (nums1[i][0] < nums2[j][0]) {17                result.add(nums1[i]);18                i++;19            } else {20                result.add(nums2[j]);21                j++;22            }23        }24 25        // Add remaining elements from nums126        while (i < n1) {27            result.add(nums1[i]);28            i++;29        }30 31        // Add remaining elements from nums232        while (j < n2) {33            result.add(nums2[j]);34            j++;35        }36 37        return result.toArray(new int[result.size()][]);38    }39}

Complexity

Time

O(N + M), where N and M are the lengths of the input arrays. This is because we iterate through both arrays with two pointers in a single pass.

Space

O(N + M), where N and M are the lengths of `nums1` and `nums2`. This space is used for the result list. If the output array is not considered extra space, the complexity is O(1).

Trade-offs

Pros

Optimal time complexity, as it processes each element from both arrays only once.
Efficiently uses the sorted property of the input arrays.
Low overhead compared to map-based solutions.

Cons

This approach relies heavily on the input arrays being sorted. It would not work correctly for unsorted inputs without a pre-sorting step.

Solutions

Solution

1class Solution { public int [][] mergeArrays ( int [][] nums1 , int [][] nums2 ) { int [] cnt = new int [ 1001 ]; for ( var x : nums1 ) { cnt [ x [ 0 ]] += x [ 1 ]; } for ( var x : nums2 ) { cnt [ x [ 0 ]] += x [ 1 ]; } int n = 0 ; for ( int i = 0 ; i < 1001 ; ++ i ) { if ( cnt [ i ] > 0 ) { ++ n ; } } int [][] ans = new int [ n ][ 2 ]; for ( int i = 0 , j = 0 ; i < 1001 ; ++ i ) { if ( cnt [ i ] > 0 ) { ans [ j ++] = new int [] { i , cnt [ i ]}; } } return ans ; } }

1class Solution { public: vector < vector < int >> mergeArrays ( vector < vector < int >>& nums1 , vector < vector < int >>& nums2 ) { int cnt [ 1001 ]{}; for ( auto & x : nums1 ) { cnt [ x [ 0 ]] += x [ 1 ]; } for ( auto & x : nums2 ) { cnt [ x [ 0 ]] += x [ 1 ]; } vector < vector < int >> ans ; for ( int i = 0 ; i < 1001 ; ++ i ) { if ( cnt [ i ]) { ans . push_back ({ i , cnt [ i ]}); } } return ans ; } };

1class Solution : def mergeArrays ( self , nums1 : List [ List [ int ]], nums2 : List [ List [ int ]] ) -> List [ List [ int ]]: cnt = Counter () for i , v in nums1 + nums2 : cnt [ i ] += v return sorted ( cnt . items ())

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem