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.

#2570

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

合并两个二维数组 - 求和法

给你两个二维整数数组 nums1 和 nums2. nums1[i] = [id i , val i ] 表示编号为 id i 的数字对应的值等于 val i 。 nums2[i] = [id i , val i ] 表示编号为 id i 的数字对应的值等于 val i 。每个数组都包含互不…

数组哈希表双指针

题目描述

给你两个二维整数数组 nums1 和 nums2.

nums1[i] = [id_i, val_i] 表示编号为 id_i 的数字对应的值等于 val_i 。
nums2[i] = [id_i, val_i] 表示编号为 id_i 的数字对应的值等于 val_i 。

每个数组都包含 互不相同 的 id ，并按 id 以递增顺序排列。

请你将两个数组合并为一个按 id 以递增顺序排列的数组，并符合下述条件：

只有在两个数组中至少出现过一次的 id 才能包含在结果数组内。
每个 id 在结果数组中 只能出现一次 ，并且其对应的值等于两个数组中该 id 所对应的值求和。如果某个数组中不存在该 id ，则假定其对应的值等于 0 。

返回结果数组。返回的数组需要按 id 以递增顺序排列。

示例 1：

输入：nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
输出：[[1,6],[2,3],[3,2],[4,6]]
解释：结果数组中包含以下元素：
- id = 1 ，对应的值等于 2 + 4 = 6 。
- id = 2 ，对应的值等于 3 。
- id = 3 ，对应的值等于 2 。
- id = 4 ，对应的值等于 5 + 1 = 6 。

示例 2：

输入：nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
输出：[[1,3],[2,4],[3,6],[4,3],[5,5]]
解释：不存在共同 id ，在结果数组中只需要包含每个 id 和其对应的值。

提示：

1 <= nums1.length, nums2.length <= 200
nums1[i].length == nums2[j].length == 2
1 <= id_i, val_i <= 1000
数组中的 id 互不相同
数据均按 id 以严格递增顺序排列

lightbulb

解题思路

方法一：计数 + 枚举

我们可以用一个哈希表或数组 cnt 统计两个数组中每个数字出现的次数。

然后我们从小到大枚举 cnt 中的每个数字，如果该数字出现的次数大于 $0$ ，则将其加入答案数组中。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(M)$ 。其中 $n$ 和 $m$ 分别是两个数组的长度；而 $M$ 是两个数组中数字的最大值，本题中 $M = 1000$ 。

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	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.
空间	O(N1 + N2)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2540 最小公共值 #2491 划分技能点相等的团队 #2465 不同的平均值数目