algoadvance

You are given two 2D arrays arr1 and arr2, where each array is a list of lists. Each sublist contains exactly two integers where:

• The first integer is the index.
• The second integer is a value corresponding to that index.

Your goal is to merge these two arrays such that at each index, the values from both arrays are summed together.

Return the merged result as a 2D array sorted by index in ascending order. If an index does not exist in one of the input arrays, simply copy the existing value from the other array.

Clarifying Questions

1. Input Constraints:
   • What are the constraints on the values inside the arrays (both for index and value)?
   • Are the indices unique within each array?
2. Output Format:
   • Should the merged result be sorted by index?

Answers to Clarifying Questions

1. Input Constraints:
   • Indices are guaranteed to be unique within each array.
   • Values can be any integers.
2. Output Format:
   • Yes, the merged result should be sorted by index in ascending order.

Strategy

1. Parsing the Inputs:
   • Use a dictionary to store the index-value pairs while summing the values when indices are the same.
2. Merge the Arrays:
   • Traverse both arrays and update the dictionary with sums.
3. Sorting the Dictionary:
   • Convert the dictionary back to a list of lists and sort by the index.

Code

def mergeArrays(arr1, arr2):
    from collections import defaultdict

    # defaultdict to store the sum at each index
    merged_dict = defaultdict(int)

    # Process arr1
    for idx, value in arr1:
        merged_dict[idx] += value

    # Process arr2
    for idx, value in arr2:
        merged_dict[idx] += value

    # Convert to 2D array and sort by index
    result = [[idx, value] for idx, value in merged_dict.items()]
    result.sort(key=lambda x: x[0])

    return result

# Example usage:
arr1 = [[1, 2], [2, 3], [4, 5]]
arr2 = [[1, 4], [3, 2], [4, 1]]

print(mergeArrays(arr1, arr2))

Time Complexity

• Inserting into the dictionary: Both arrays are traversed exactly once, which is O(n) where n is the number of elements in both arrays combined.
• Sorting the results: Sorting a list of size m (where m is the number of unique indices) takes O(m log m).

Overall, the time complexity is: [ O(n + m \log m) ]

Where:

• n is the total number of elements in both input arrays.
• m is the number of unique indices in the merged result.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?