Join Two Arrays by ID - Practice Coding Problems

Join Two Arrays by ID - Problem

JavaScript Medium

Given two arrays arr1 and arr2, return a new array joinedArray. All the objects in each of the two input 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.

Input & Output

Example 1 — Basic Merge

$ Input: arr1 = [{"id":1,"x":1},{"id":2,"x":2}], arr2 = [{"id":3,"x":3}]

› Output: [{"id":1,"x":1},{"id":2,"x":2},{"id":3,"x":3}]

💡 Note: No overlapping IDs, so objects are combined and sorted by ID: 1, 2, 3

Example 2 — Property Override

$ Input: arr1 = [{"id":1,"x":1},{"id":2,"x":2}], arr2 = [{"id":1,"x":10,"y":20}]

› Output: [{"id":1,"x":10,"y":20},{"id":2,"x":2}]

💡 Note: ID 1 exists in both arrays. arr2 overrides x:1 with x:10 and adds y:20

Example 3 — Complex Merge

$ Input: arr1 = [{"id":2,"a":1,"b":2},{"id":3,"a":3}], arr2 = [{"id":1,"c":4},{"id":2,"a":5}]

› Output: [{"id":1,"c":4},{"id":2,"a":5,"b":2},{"id":3,"a":3}]

💡 Note: ID 2 merges: arr2's a:5 overrides arr1's a:1, but b:2 remains. Final order: 1,2,3

Constraints

1 ≤ arr1.length, arr2.length ≤ 1000
Each object contains an id field with unique integer value within its array
0 ≤ number of additional properties ≤ 10
Property values can be any valid JSON type

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two arrays of objects, each with an id field plus other properties

Merge Process

Combine objects by ID, arr2 properties override arr1 when conflicts arise

Sorted Output

Final array sorted by ID in ascending order

Key Takeaway

🎯 Key Insight: Use hash maps for O(1) ID-based merging, where arr2 values always override arr1 values in conflicts

Asked in

G Google 32 a Amazon 28 f Facebook 25 M Microsoft 22

The optimal approach uses a hash map to merge objects by ID in O(1) time, followed by sorting. Key insight: Hash maps enable efficient property merging where arr2 values override arr1. Best time complexity: O(n log n) due to final sorting step, Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Two Pass	O(n log n)	O(n)	First pass builds a hash map from arr1, second pass processes arr2
Brute Force - Nested Loop Merge	O(n²)	O(n)	For each object in arr1, search through all of arr2 to find matching IDs
One Pass Hash Map	O(n log n)	O(n)	Single pass through both arrays with hash map for optimal performance

Hash Map - Two Pass — Algorithm Steps

Step 1: Create hash map and populate with arr1 objects (ID as key)
Step 2: Process arr2 - merge with existing objects or add new ones
Step 3: Convert hash map values to array and sort by ID

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Map

First pass: store arr1 objects in hash map by ID

Process arr2

Second pass: merge or add objects from arr2

Sort & Return

Convert map to array and sort by ID

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cjson/cJSON.h>

#define MAX_OBJECTS 1000

typedef struct {
    int id;
    cJSON* obj;
} MapEntry;

cJSON* solution(cJSON* arr1, cJSON* arr2) {
    MapEntry idMap[MAX_OBJECTS];
    int mapSize = 0;
    
    // First pass: build hash map from arr1
    cJSON* obj1 = NULL;
    cJSON_ArrayForEach(obj1, arr1) {
        int id = cJSON_GetObjectItem(obj1, "id")->valueint;
        idMap[mapSize].id = id;
        idMap[mapSize].obj = cJSON_Duplicate(obj1, 1);
        mapSize++;
    }
    
    // Second pass: process arr2
    cJSON* obj2 = NULL;
    cJSON_ArrayForEach(obj2, arr2) {
        int id = cJSON_GetObjectItem(obj2, "id")->valueint;
        int found = -1;
        
        // Search for existing ID
        for (int i = 0; i < mapSize; i++) {
            if (idMap[i].id == id) {
                found = i;
                break;
            }
        }
        
        if (found != -1) {
            // Merge properties
            cJSON* prop = NULL;
            cJSON_ArrayForEach(prop, obj2) {
                cJSON* existing = cJSON_GetObjectItem(idMap[found].obj, prop->string);
                if (existing) cJSON_DeleteItemFromObject(idMap[found].obj, prop->string);
                cJSON_AddItemToObject(idMap[found].obj, prop->string, cJSON_Duplicate(prop, 1));
            }
        } else {
            // Add new object
            idMap[mapSize].id = id;
            idMap[mapSize].obj = cJSON_Duplicate(obj2, 1);
            mapSize++;
        }
    }
    
    // Sort by ID
    for (int i = 0; i < mapSize - 1; i++) {
        for (int j = 0; j < mapSize - 1 - i; j++) {
            if (idMap[j].id > idMap[j + 1].id) {
                MapEntry temp = idMap[j];
                idMap[j] = idMap[j + 1];
                idMap[j + 1] = temp;
            }
        }
    }
    
    // Convert to result array
    cJSON* result = cJSON_CreateArray();
    for (int i = 0; i < mapSize; i++) {
        cJSON_AddItemToArray(result, idMap[i].obj);
    }
    
    return result;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    cJSON* arr1 = cJSON_Parse(line1);
    cJSON* arr2 = cJSON_Parse(line2);
    
    cJSON* result = solution(arr1, arr2);
    char* output = cJSON_Print(result);
    printf("%s\n", output);
    
    cJSON_Delete(arr1);
    cJSON_Delete(arr2);
    cJSON_Delete(result);
    free(output);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n) for hash map operations plus O(n log n) for sorting

⚡ Linearithmic

Space Complexity

O(n)

Hash map stores up to n objects by ID

⚡ Linearithmic Space

23.4K Views

High Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - Two Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler