We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Merge Two 2D Arrays by Summing Values

Number: 2707

Difficulty: Easy

Paid? No

Companies: Google, Yandex

Problem Description

Given two 2D integer arrays, each holding unique ids sorted in ascending order along with their corresponding values, merge them into a single sorted 2D array. If an id appears in both arrays, the resulting value is the sum of values from both arrays. If an id appears in only one array, its value remains unchanged.

Key Insights

  • Both input arrays are sorted by id, which allows for an efficient merge using the two pointers technique.
  • Since the arrays are sorted, we can iterate over both simultaneously without additional data structures.
  • A hash table (or dictionary) approach is an alternative, but the two pointers method leverages the sorted property for O(n) merging.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the lengths of nums1 and nums2. Space Complexity: O(n + m), accounting for the space needed for the resulting merged array.

Solution

We use the two pointers approach:

  1. Initialize two pointers, one for each array.
  2. Compare the current id from each array:
    • If the ids match, sum their values and add the pair to the result, then advance both pointers.
    • If one id is smaller, add that pair to the result and advance its pointer.
  3. Append any remaining pairs from either array once the other pointer has reached the end. This approach leverages the fact that both arrays are already sorted, ensuring a linear time merge with constant extra space (besides the output storage).

Code Solutions

# Python solution for merging two sorted 2D arrays by summing values
def mergeArrays(nums1, nums2):
    # Initialize pointers for each array
    i, j = 0, 0
    merged = []
    # Loop until one array is exhausted
    while i < len(nums1) and j < len(nums2):
        id1, val1 = nums1[i]
        id2, val2 = nums2[j]
        # If ids are equal, sum the values and append
        if id1 == id2:
            merged.append([id1, val1 + val2])
            i += 1
            j += 1
        # If id1 is smaller, append from nums1
        elif id1 < id2:
            merged.append([id1, val1])
            i += 1
        # If id2 is smaller, append from nums2
        else:
            merged.append([id2, val2])
            j += 1
    # Append remaining elements if any
    while i < len(nums1):
        merged.append(nums1[i])
        i += 1
    while j < len(nums2):
        merged.append(nums2[j])
        j += 1
    return merged

# Example usage:
# print(mergeArrays([[1,2],[2,3],[4,5]], [[1,4],[3,2],[4,1]]))
← Back to All Questions