How do you solve Join Two Arrays by ID on LeetCode?

Join Two Arrays by ID (LeetCode #2722) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a HashMap allows for efficient merging of objects by id.

What is the brute force solution for Join Two Arrays by ID?

The brute force approach for Join Two Arrays by ID is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we will iterate through both arrays and check for each object in arr1 if it exists in arr2 based on the id. If it does, we will merge them; if not, we will add the object from arr1 or arr2 directly to the result. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Join Two Arrays by ID?

Clearly explain your thought process and how you handle merging. Consider edge cases, such as empty arrays or arrays with only one object. Practice writing clean and efficient code.

What are common mistakes when solving Join Two Arrays by ID?

Not handling the case where an id exists in both arrays correctly. Forgetting to sort the final output.

#2722

Join Two Arrays by ID

Medium

Hash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

In this approach, we use a HashMap to store objects from both arrays based on their id. This allows us to merge them efficiently in a single pass, reducing the time complexity significantly.

⚙️

Algorithm

5 steps

1Step 1: Create a HashMap to store merged objects by id.
2Step 2: Loop through arr1 and add each object to the HashMap using its id as the key.
3Step 3: Loop through arr2 and for each object, merge it with the existing object in the HashMap if the id exists.
4Step 4: Convert the HashMap values to an array.
5Step 5: Sort the array based on the id.

solution.py10 lines

1def join_arrays(arr1, arr2):
2    merged_map = {}
3    for obj in arr1:
4        merged_map[obj['id']] = obj
5    for obj in arr2:
6        if obj['id'] in merged_map:
7            merged_map[obj['id']].update(obj)
8        else:
9            merged_map[obj['id']] = obj
10    return sorted(merged_map.values(), key=lambda x: x['id'])

ℹ

Complexity note: The time complexity is O(n) because we make a single pass through both arrays to build the HashMap, and then another pass to sort the results.

1Using a HashMap allows for efficient merging of objects by id.
2Sorting the final result ensures the output is in the desired order.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.