Merge Two 2D Arrays by Summing Values

The problem asks us to merge two 2D arrays based on unique IDs, summing the values of common IDs.

Here’s a detailed explanation and the code for the solution:

  1. Create a Dictionary to Store IDs and Values: We’ll use a dictionary to store the IDs as keys and the values as the corresponding values. This allows for quick access to the value for a given ID.

  2. Iterate Through nums1 and nums2 and Store IDs and Values: Iterate through both arrays, and for each ID, either add the value to the dictionary if the ID already exists or insert a new key-value pair if it doesn’t.

  3. Convert the Dictionary to the Required Format: Convert the dictionary to a list of lists, where each inner list contains the ID and its corresponding value.

  4. Sort the Result by ID: Sort the resulting list of lists by ID to ensure the result is in ascending order by ID.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
        # Create a dictionary to store the IDs and their corresponding values
        id_values = {}

        # Iterate through nums1 and add the IDs and values to the dictionary
        for id_val in nums1:
            id_values[id_val[0]] = id_val[1]

        # Iterate through nums2 and either add the value to the existing ID or insert a new key-value pair
        for id_val in nums2:
            id = id_val[0]
            value = id_val[1]
            if id in id_values:
                id_values[id] += value
            else:
                id_values[id] = value

        # Convert the dictionary to the required format and sort it by ID
        result = [[k, v] for k, v in id_values.items()]
        result.sort(key=lambda x: x[0])

        return result

Explanation:

  • By using a dictionary, we efficiently handle the IDs, avoiding unnecessary searches for existing IDs.
  • We iterate through both nums1 and nums2, summing the values of common IDs, and handle IDs that only exist in one of the arrays.
  • We then convert the dictionary to the required format and sort it by ID, ensuring that the result meets the problem’s requirements.

This solution has a time complexity of (O(n \log n)), where (n) is the total number of elements in nums1 and nums2, and a space complexity of (O(n)).