Merge Two 2D Arrays by Summing Values - Practice Coding Problems

Merge Two 2D Arrays by Summing Values - Problem

You are given two 2D integer arrays nums1 and nums2.

nums1[i] = [id_i, val_i] indicate that the number with the id id_i has a value equal to val_i.

nums2[i] = [id_i, val_i] indicate that the number with the id id_i has a value equal to val_i.

Each array contains unique ids and is sorted in ascending order by id.

Merge the two arrays into one array that is sorted in ascending order by id, respecting the following conditions:

Only ids that appear in at least one of the two arrays should be included in the resulting array.
Each id should be included only once and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays, then assume its value in that array to be 0.

Return the resulting array. The returned array must be sorted in ascending order by id.

Input & Output

Example 1 — Basic Merge

$ Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]

› Output: [[1,6],[2,3],[3,2],[4,6]]

💡 Note: ID 1 appears in both arrays: 2+4=6. ID 2 only in nums1: value 3. ID 3 only in nums2: value 2. ID 4 appears in both: 5+1=6.

Example 2 — No Common IDs

$ Input: nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,2],[6,1]]

› Output: [[1,3],[2,4],[3,6],[4,2],[5,5],[6,1]]

💡 Note: No common IDs, so we merge all pairs and sort by ID: 1,2,3,4,5,6.

Example 3 — Single Elements

$ Input: nums1 = [[1,5]], nums2 = [[1,3]]

› Output: [[1,8]]

💡 Note: Both arrays contain only ID 1, so we sum the values: 5+3=8.

Constraints

1 ≤ nums1.length, nums2.length ≤ 1000
nums1[i].length == nums2[i].length == 2
1 ≤ id_i, val_i ≤ 1000
Both arrays contain unique ids and are sorted in ascending order by id

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two sorted arrays with [id,value] pairs

Merge Process

Combine arrays, summing values for matching IDs

Sorted Output

Result array sorted by ID with summed values

Key Takeaway

🎯 Key Insight: Use two pointers to merge sorted arrays in O(n+m) time, like merging two sorted lists

Asked in

a Amazon 25 M Microsoft 18 G Google 15

The key insight is leveraging the fact that both arrays are sorted by ID to use a two-pointer approach. Best approach is Two Pointers with Time: O(n+m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Hash Map	O(n log n)	O(n)	Store all id-value pairs in a hash map, then convert back to sorted array
Two Pointers (Optimal)	O(n + m)	O(1)	Use two pointers to merge sorted arrays in one pass

Brute Force with Hash Map — Algorithm Steps

Step 1: Create empty hash map
Step 2: Add all pairs from nums1 to map
Step 3: Add all pairs from nums2, summing if id exists
Step 4: Convert map to sorted array

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Map

Initialize empty hash map

Add First Array

Store all id-value pairs from nums1

Add Second Array

Add nums2 pairs, summing values for existing IDs

Sort Result

Convert map to sorted array by ID

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int id;
    int val;
} IdVal;

int compare(const void *a, const void *b) {
    IdVal *ia = (IdVal *)a;
    IdVal *ib = (IdVal *)b;
    return ia->id - ib->id;
}

int** solution(int** nums1, int nums1Size, int* nums1ColSize, int** nums2, int nums2Size, int* nums2ColSize, int* returnSize, int** returnColumnSizes) {
    IdVal temp[2000]; // Assuming max 1000 elements in each array
    int count = 0;
    
    // Add all from nums1
    for (int i = 0; i < nums1Size; i++) {
        temp[count].id = nums1[i][0];
        temp[count].val = nums1[i][1];
        count++;
    }
    
    // Add all from nums2, check for duplicates
    for (int i = 0; i < nums2Size; i++) {
        int found = -1;
        for (int j = 0; j < count; j++) {
            if (temp[j].id == nums2[i][0]) {
                found = j;
                break;
            }
        }
        if (found != -1) {
            temp[found].val += nums2[i][1];
        } else {
            temp[count].id = nums2[i][0];
            temp[count].val = nums2[i][1];
            count++;
        }
    }
    
    // Sort by id
    qsort(temp, count, sizeof(IdVal), compare);
    
    // Prepare result
    *returnSize = count;
    *returnColumnSizes = (int*)malloc(count * sizeof(int));
    int** result = (int**)malloc(count * sizeof(int*));
    
    for (int i = 0; i < count; i++) {
        (*returnColumnSizes)[i] = 2;
        result[i] = (int*)malloc(2 * sizeof(int));
        result[i][0] = temp[i].id;
        result[i][1] = temp[i].val;
    }
    
    return result;
}

int main() {
    // For simplicity, using fixed input parsing
    printf("[[1,6],[3,3]]");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n) to process arrays + O(n log n) to sort the result

⚡ Linearithmic

Space Complexity

O(n)

Hash map stores up to n unique ids

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 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

Brute Force with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler