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

Join Two Arrays by ID

Number: 2858

Difficulty: Medium

Paid? No

Companies: Apple, Google

Problem Description

Given two arrays arr1 and arr2 where each element is an object with a unique integer id and additional properties, merge the two arrays by id into a single sorted array. For objects with the same id, merge the key-value pairs such that keys present in both objects use the value from arr2. If an id exists in only one array, include that object unchanged. Finally, return the result array sorted in ascending order by id.

Key Insights

  • Identify objects by their unique id.
  • Use a hash map (or similar dictionary structure) to consolidate objects.
  • For overlapping objects with the same id, merge properties with arr2 overriding arr1.
  • Sort the resulting objects based on id in ascending order.

Space and Time Complexity

Time Complexity: O(n + m + k log k) where n and m are the lengths of arr1 and arr2, and k is the number of unique ids. Space Complexity: O(n + m) due to the additional data structure used to store merged objects.

Solution

Use a hash map keyed by id to store the merged objects. First, iterate over arr1 and add each object to the map. Next, iterate over arr2 and check if the object's id exists in the map; if it does, merge the two objects by updating the key-value pairs (with arr2’s values taking precedence), otherwise add the new object. Finally, extract the objects from the map into an array and sort by id in ascending order before returning the result. This approach ensures efficient merging and meets the sorting requirement.

Code Solutions

# Function to merge two arrays based on id
def join_arrays_by_id(arr1, arr2):
    # Dictionary to store merged objects using id as key
    merged = {}

    # Add all objects from arr1 into the merged dictionary
    for obj in arr1:
        merged[obj["id"]] = obj.copy()

    # Process arr2 and merge with arr1 if id exists
    for obj in arr2:
        obj_id = obj["id"]
        if obj_id in merged:
            # For matching id, update the object with arr2's key-value pairs
            merged[obj_id].update(obj)
        else:
            merged[obj_id] = obj.copy()

    # Return the sorted list of merged objects based on id in ascending order
    return sorted(merged.values(), key=lambda x: x["id"])

# Example usage
if __name__ == "__main__":
    arr1 = [{"id": 1, "x": 2, "y": 3}, {"id": 2, "x": 3, "y": 6}]
    arr2 = [{"id": 2, "x": 10, "y": 20}, {"id": 3, "x": 0, "y": 0}]
    result = join_arrays_by_id(arr1, arr2)
    print(result)  # Expected merged and sorted array by id
← Back to All Questions