Skip to main content
Talentd

Join Two Arrays by ID - Solution & Explanation

Medium8 min read
Practice this problem

Problem Statement

Given two arrays arr1 and arr2, return a new array joinedArray. All the objects in each of the two inputs arrays will contain an id field that has an integer value. 

joinedArray is an array formed by merging arr1 and arr2 based on their id key. The length of joinedArray should be the length of unique values of id. The returned array should be sorted in ascending order based on the id key.

If a given id exists in one array but not the other, the single object with that id should be included in the result array without modification.

If two objects share an id, their properties should be merged into a single object:

  • If a key only exists in one object, that single key-value pair should be included in the object.
  • If a key is included in both objects, the value in the object from arr2 should override the value from arr1.

 

Example 1:

Input: 
arr1 = [
    {"id": 1, "x": 1},
    {"id": 2, "x": 9}
], 
arr2 = [
    {"id": 3, "x": 5}
]
Output: 
[
    {"id": 1, "x": 1},
    {"id": 2, "x": 9},
    {"id": 3, "x": 5}
]
Explanation: There are no duplicate ids so arr1 is simply concatenated with arr2.

Example 2:

Input: 
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}
]
Output: 
[
    {"id": 1, "x": 2, "y": 3},
    {"id": 2, "x": 10, "y": 20},
    {"id": 3, "x": 0, "y": 0}
]
Explanation: The two objects with id=1 and id=3 are included in the result array without modifiction. The two objects with id=2 are merged together. The keys from arr2 override the values in arr1.

Example 3:

Input: 
arr1 = [
    {"id": 1, "b": {"b": 94},"v": [4, 3], "y": 48}
]
arr2 = [
    {"id": 1, "b": {"c": 84}, "v": [1, 3]}
]
Output: [
    {"id": 1, "b": {"c": 84}, "v": [1, 3], "y": 48}
]
Explanation: The two objects with id=1 are merged together. For the keys "b" and "v" the values from arr2 are used. Since the key "y" only exists in arr1, that value is taken form arr1.

 

Constraints:

  • arr1 and arr2 are valid JSON arrays
  • Each object in arr1 and arr2 has a unique integer id key
  • 2 <= JSON.stringify(arr1).length <= 106
  • 2 <= JSON.stringify(arr2).length <= 106

Approach Overview

Problem Overview: You receive two arrays of objects where each object contains an id and additional properties. The task is to join both arrays by matching id values. If the same id appears in both arrays, merge their properties into one object. The final result must contain unique ids with merged values.

Approach 1: Map-Based Merging (O(n + m) time, O(n + m) space)

This approach uses a hash map keyed by id. Iterate through the first array and insert each object into the map. Then iterate through the second array. For each element, perform a constant-time hash lookup. If the id already exists, merge the fields so the second array’s values overwrite duplicates. If the id does not exist, insert it directly. After processing both arrays, convert the map values into a result list and sort by id if required by the problem. The key insight is that hash lookups make merging efficient without nested iteration. This approach relies on concepts from hash map usage and array traversal.

Approach 2: Combined Sorting and Merging (O((n + m) log(n + m)) time, O(1)–O(n + m) space)

This method treats the task like merging two sorted datasets. First combine the arrays and sort them by id. Once sorted, iterate sequentially and merge adjacent objects that share the same id. Because identical ids become neighbors after sorting, you can combine them while scanning with a single pointer. Another variation sorts both arrays individually and uses a two-pointer merge process similar to merge sort. The advantage is predictable ordering and no hash map dependency. This method highlights patterns from sorting and two-pointer merging techniques.

Recommended for interviews: The map-based approach is usually the expected solution. It runs in linear time and clearly demonstrates your ability to use hash-based indexing to eliminate nested loops. Sorting-based merging is still valid and useful when input data is already sorted or when deterministic ordering is required without additional data structures.

Approach 1: Map-Based Merging

This approach utilizes a map or dictionary to streamline the merging process. By iterating over the two input arrays, we can store each object in a map with its id as the key. This allows constant-time access when merging objects sharing the same id. After processing both arrays, the map's entries can be retrieved and sorted by id to form the final result.

We start by creating an empty dictionary merged_dict to serve as our map. Traverse through arr1, inserting each object into the dictionary using its id as the key. We then iterate over arr2, and for any id already present in the dictionary, we update the respective object, allowing the properties of arr2 to override those in arr1. Finally, we convert the map's values to a list and sort them by id before returning.

Code

PythonC

Python

C

Complexity

Time Complexity: O((n + m) log(n + m)) where n and m are the lengths of arr1 and arr2, due to the sorting operation.
Space Complexity: O(n + m) for the storage of objects in the dictionary.

Try this approach in the editor →

Approach 2: Combined Sorting and Merging

This method involves sorting both arrays prior to merging. After sorting, we can employ a two-pointer technique to iterate through the arrays simultaneously, aligning ids and merging objects as necessary. By maintaining an additional list, the sorted and merged result can be constructed efficiently.

We first sort arr1 and arr2 in ascending order of their id. Using two pointers, we walk through both lists, merging objects with matching ids using a hashmap (caused by the call to putAll() for objects with the same id), and appending the results to our list.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n log n + m log m) due to sorting each array.
Space Complexity: O(n + m) for the merged results.

Try this approach in the editor →

Approach 3: Default Approach

Code

TypeScript

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Map-Based Merging

Time Complexity: O((n + m) log(n + m)) where n and m are the lengths of arr1 and arr2, due to the sorting operation.
Space Complexity: O(n + m) for the storage of objects in the dictionary.

Combined Sorting and Merging

Time Complexity: O(n log n + m log m) due to sorting each array.
Space Complexity: O(n + m) for the merged results.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Map-Based MergingO(n + m)O(n + m)General case. Best performance when arrays are unsorted and fast lookups are needed.
Combined Sorting and MergingO((n + m) log(n + m))O(1)–O(n + m)Useful when deterministic ordering is required or when arrays are already sorted.

Video Solution

Join Two Arrays by ID | Leetcode 2722 | JSON | 30 Days of JavaScript #javascript #leetcode • Learn With Chirag • 2,202 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Join Two Arrays by ID easy or hard?
Join Two Arrays by ID is considered a Medium-level problem. The challenge lies in recognizing that a hash map eliminates the need for nested loops and enables linear-time merging of the arrays.
Join Two Arrays by ID Python/Java solution
Python solutions typically use a dictionary keyed by id to store and merge objects. Java implementations use a HashMap<Integer, Map<String, Object>> or similar structure. Both approaches follow the same O(n + m) hash map merging strategy.
How to solve Join Two Arrays by ID in O(n)?
Store objects from the first array in a hash map using id as the key. Iterate through the second array and perform a lookup for each id. If the id exists, merge the properties; otherwise insert a new entry. This processes each element once, giving O(n + m) time complexity.
What is the best approach for Join Two Arrays by ID?
The best approach uses a hash map keyed by id. Insert objects from the first array into the map, then iterate through the second array and merge values when the id already exists. This reduces the complexity to O(n + m) time with O(n + m) extra space and avoids nested loops.
Is Join Two Arrays by ID asked at Google/Amazon/Meta?
Problems involving merging datasets by a unique key frequently appear in interviews at companies like Amazon, Google, and Meta. They test understanding of hash maps, object merging, and efficient data processing patterns.
What data structure is used in Join Two Arrays by ID?
The primary data structure is a hash map (dictionary). It allows constant-time lookups by id, which makes merging objects from two arrays efficient. Sorting and two-pointer techniques are alternative strategies when ordering constraints exist.
What is the time complexity of Join Two Arrays by ID?
The optimal solution runs in O(n + m) time where n and m are the lengths of the two arrays. Each element is processed once with constant-time hash map lookups. A sorting-based alternative takes O((n + m) log(n + m)) due to the sorting step.

Ready to solve this problem?

Practice Join Two Arrays by ID with our built-in code editor and test cases.

Practice on FleetCode