Merge Similar Items - Practice Coding Problems

Merge Similar Items - Problem

You are given two 2D integer arrays, items1 and items2, representing two sets of items. Each array has the following properties:

items[i] = [value_i, weight_i] where value_i represents the value and weight_i represents the weight of the i^th item.

The value of each item in items is unique.

Return a 2D integer array ret where ret[i] = [value_i, weight_i], with weight_i being the sum of weights of all items with value value_i.

Note: ret should be returned in ascending order by value.

Input & Output

Example 1 — Basic Merge

$ Input: items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]

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

💡 Note: Value 1: weight 1 + 5 = 6. Value 3: weight 8 + 1 = 9. Value 4: weight 5. Sorted by value: [1,6], [3,9], [4,5].

Example 2 — No Overlap

$ Input: items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[4,5],[6,4]]

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

💡 Note: Only value 2 appears in both arrays: 3 + 1 = 4. All other values appear once. Final sorted result.

Example 3 — Single Items

$ Input: items1 = [[1,3]], items2 = [[2,2]]

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

💡 Note: No overlapping values, so result contains both items as-is, sorted by value.

Constraints

1 ≤ items1.length, items2.length ≤ 1000
items1[i].length == items2[i].length == 2
1 ≤ value_i, weight_i ≤ 1000
Each value_i in items1 is unique
Each value_i in items2 is unique

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two separate item arrays with [value, weight] pairs

Merge Process

Combine items with same values, sum their weights

Sorted Output

Return merged items sorted by value ascending

Key Takeaway

🎯 Key Insight: Use a hash map to efficiently group items by value and sum their weights in a single pass

Asked in

a Amazon 25 G Google 18 M Microsoft 12

The key insight is to use a hash map to efficiently group items by their values and sum their weights. The optimal approach is the Hash Map method with Time: O(n log n), Space: O(n). We process both arrays in a single pass, then sort the final result.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Concatenation	O(n²)	O(n)	Combine all items, then group by value using nested loops
Hash Map Approach	O(n log n)	O(n)	Use hash map to efficiently group items by value in single pass

Brute Force Concatenation — Algorithm Steps

Combine items1 and items2 into one array
For each unique value, scan all items to sum weights
Sort result by value

Visualization

Tap to expand

Step-by-Step Walkthrough

Combine Arrays

Merge items1 and items2 into single array

For Each Value

Scan entire array to sum weights for this value

Sort Result

Sort final pairs by value ascending

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    int *arr1 = *(int**)a;
    int *arr2 = *(int**)b;
    return arr1[0] - arr2[0];
}

int** solution(int** items1, int items1Size, int** items2, int items2Size, int* returnSize, int** returnColumnSizes) {
    int totalSize = items1Size + items2Size;
    int** allItems = (int**)malloc(totalSize * sizeof(int*));
    
    // Combine all items
    for (int i = 0; i < items1Size; i++) {
        allItems[i] = items1[i];
    }
    for (int i = 0; i < items2Size; i++) {
        allItems[items1Size + i] = items2[i];
    }
    
    // Find unique values and calculate weights
    int** result = (int**)malloc(totalSize * sizeof(int*));
    int* returnCols = (int*)malloc(totalSize * sizeof(int));
    int resultSize = 0;
    
    for (int i = 0; i < totalSize; i++) {
        int value = allItems[i][0];
        int found = 0;
        
        // Check if we already processed this value
        for (int j = 0; j < resultSize; j++) {
            if (result[j][0] == value) {
                found = 1;
                break;
            }
        }
        
        if (!found) {
            int totalWeight = 0;
            for (int j = 0; j < totalSize; j++) {
                if (allItems[j][0] == value) {
                    totalWeight += allItems[j][1];
                }
            }
            result[resultSize] = (int*)malloc(2 * sizeof(int));
            result[resultSize][0] = value;
            result[resultSize][1] = totalWeight;
            returnCols[resultSize] = 2;
            resultSize++;
        }
    }
    
    // Sort by value
    qsort(result, resultSize, sizeof(int*), compare);
    
    *returnSize = resultSize;
    *returnColumnSizes = returnCols;
    free(allItems);
    return result;
}

int main() {
    // For simplicity, using fixed test case
    int arr1[][2] = {{1,1}, {4,5}, {3,8}};
    int arr2[][2] = {{3,1}, {1,5}};
    
    int* items1[3];
    int* items2[2];
    for (int i = 0; i < 3; i++) items1[i] = arr1[i];
    for (int i = 0; i < 2; i++) items2[i] = arr2[i];
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(items1, 3, items2, 2, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("[%d,%d]", result[i][0], result[i][1]);
        free(result[i]);
    }
    printf("]\n");
    
    free(result);
    free(returnColumnSizes);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n items, we scan all n items to find matching values

⚠ Quadratic Growth

Space Complexity

O(n)

Space for concatenated array and result array

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

845 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 Concatenation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler