💬 Discord
Sign In
NeetCode #182LC-2570EasyTwo Pointers
← Back to All Problems

#182 · #2570 · Merge Two 2D Arrays by Summing Values(合并两个二维数组 - 求和法)

📌 Problem Statement & Constraints

You are given two 2D integer arrays nums1 and nums2, each [id_i, val_i], sorted by id with distinct ids. Merge them by summing the values of equal ids, keeping the result sorted by id. Constraints: 1 <= nums1.length, nums2.length <= 200, 1 <= id <= 1000, 1 <= val <= 100. The result must not contain ids with a sum of zero.

💡 Core Algorithmic Approaches

  1. Because both arrays are sorted by id, a two-pointer merge handles the join directly.
  2. When the ids are equal, sum the values and advance both pointers.
  3. When one id is smaller, emit that entry alone and advance only that pointer.
  4. Finally, append any remaining tail. Since all values are positive, no sum can be zero, so no filtering is needed -- but the problem's general form asks for it, so guard anyway if values could be negative.

💻 Benchmark Python3 Implementation

class Solution:
    def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
        i = j = 0
        res = []
        while i < len(nums1) and j < len(nums2):
            a, b = nums1[i], nums2[j]
            if a[0] == b[0]:
                res.append([a[0], a[1] + b[1]])   # equal ids -> sum
                i += 1
                j += 1
            elif a[0] < b[0]:
                res.append(a)
                i += 1
            else:
                res.append(b)
                j += 1
        res.extend(nums1[i:])          # remaining tails (at most one is non-empty)
        res.extend(nums2[j:])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m + n): each entry is visited once.
💾 Space Complexity
O(m + n) for the result.

⚠️ Interview Pitfalls & Follow-ups

  • Using a hash map and then sorting: correct but O((m+n) log(m+n)); the sorted inputs make the two-pointer merge linear.
  • Advancing only one pointer when the ids are equal: both must advance.
  • Forgetting to append the tails: after the loop, one array may still have unprocessed entries.
  • Assuming the values are positive: the constraints say they are, so zero sums cannot occur -- but in a generalised version you would filter them out.