algoadvance

Leetcode 2363. Merge Similar Items

Problem Statement

You are given two 2D integer arrays items1 and items2, each of which contains item[i] = [value, weight] representing the value and weight of the i-th item.

  1. Merge the two arrays, and sum the weights of items with the same value.
  2. Return the merged array in ascending order based on the value of the items.

Clarifying Questions

  1. Input Constraints:
    • What is the range of possible values for value and weight?
    • Are the values guaranteed to be positive integers?
    • What is the maximum length of items1 and items2?
  2. Output Format:
    • Should the output be sorted in ascending order based on the value?
    • Is there any additional formatting required beyond a 2D array representation?
  3. Duplicates:
    • Are the items within each input array guaranteed to be unique based on their value?

Code

Let’s write a C++ solution for merging the items and summing the weights for items with the same value.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
    unordered_map<int, int> itemMap;

    // Process the first array
    for (const auto& item : items1) {
        itemMap[item[0]] += item[1];
    }

    // Process the second array
    for (const auto& item : items2) {
        itemMap[item[0]] += item[1];
    }

    // Collect the results
    vector<vector<int>> result;
    for (const auto& [value, weight] : itemMap) {
        result.push_back({value, weight});
    }

    // Sort the result based on the value
    sort(result.begin(), result.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });

    return result;
}

// Helper function for demonstrating the output
void printItems(const vector<vector<int>>& items) {
    for (const auto& item : items) {
        cout << "[" << item[0] << ", " << item[1] << "] ";
    }
    cout << endl;
}

int main() {
    vector<vector<int>> items1 = \{\{1, 3}, {2, 2}, {3, 1}};
    vector<vector<int>> items2 = \{\{2, 3}, {3, 2}, {4, 1}};

    vector<vector<int>> mergedItems = mergeSimilarItems(items1, items2);
    printItems(mergedItems);

    return 0;
}

Strategy

  1. Use a Hash Table (unordered_map):
    • Store the cumulative weights for each unique value.
    • This will allow us to quickly look up and update the weights.
  2. Process Both Arrays:
    • Iterate through items1 and items2, updating the hash table.
  3. Collect and Sort the Results:
    • Convert the hash table entries back into a 2D array.
    • Sort the array by value before returning it.

Time Complexity

Overall, the time complexity is (O(n + m + k \log k)).

Feel free to ask any further questions or for additional modifications!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI