#2570

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Merge Two 2D Arrays by Summing Values

Merge two 2D arrays by summing values with matching ids using array scanning and hash lookup efficiently.

Problem Statement

You are given two 2D integer arrays nums1 and nums2, each containing unique ids sorted in ascending order. Your task is to merge them into one array where each id appears only once and is sorted by id.

When an id exists in both arrays, sum the corresponding values. Otherwise, include the id with its original value. Return the resulting array of pairs sorted by id.

Examples

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]]

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]]

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.

Solution Approach

Hash Map Merge

Use a dictionary to record each id from both arrays, adding values if the id appears in both. After processing, extract items and sort by id.

Two Pointers Merge

Use two pointers to iterate nums1 and nums2. Compare ids and append the smaller id or sum values if ids match, moving pointers accordingly.

Array Scanning Optimization

Since arrays are sorted and have unique ids, a single scan with either pointers or a hash map ensures O(N1 + N2) time without extra nested loops.

Complexity Analysis

Metric	Value
Time	O(N1 + N2)
Space	O(N1 + N2)

Time complexity is O(N1 + N2) due to scanning each array once. Space complexity is O(N1 + N2) if storing results in a new array or using a hash map.

What Interviewers Usually Probe

Will the candidate notice the arrays are sorted and avoid unnecessary nested loops?
Does the candidate use a hash map or two-pointer approach to merge efficiently?
Is summing values correctly applied when ids overlap without losing any unique ids?

Common Pitfalls or Variants

Common pitfalls

Failing to sum values for ids appearing in both arrays.
Using nested loops which lead to O(N1 * N2) time instead of O(N1 + N2).
Not maintaining ascending order in the merged array.

Follow-up variants

Arrays with duplicate ids within themselves requiring internal aggregation first.
Arrays containing strings as values instead of integers for merging.
Merging more than two arrays in sequence using the same sum-by-id pattern.

FAQ

What is the best way to merge two 2D arrays by summing values for matching ids?

Use a hash map to track ids and their sums, then extract and sort the result to maintain ascending order.

Can I solve this problem using only two pointers?

Yes, since both arrays are sorted, two pointers allow scanning both arrays efficiently while summing matching ids.

What is the time complexity of merging two 2D arrays with this approach?

The time complexity is O(N1 + N2) because each array is scanned once with a hash map or pointers.

How does GhostInterview help with the Array scanning plus hash lookup pattern?

It identifies when to use dictionaries or two pointers to merge arrays, highlighting potential pitfalls and optimizations.

Do I need to handle duplicate ids inside a single array?

No, each array contains unique ids, so only overlapping ids between arrays need summing.

terminal

Solution

Solution 1: Counting + Enumeration

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

1

2

3

4

5

6

7

8

class 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())

Continue Practicing

#2540 minimum common value #2491 divide players into teams of equal skill #2465 number of distinct averages