LeetCode 2363: Merge Similar Items

Explanation

To solve this problem, we need to iterate through both arrays items1 and items2, combine items with the same value, and calculate the total weight for each unique value. We can achieve this by using a HashMap to store the value as the key and the total weight as the value. After iterating through both arrays, we can construct the final result array by iterating through the HashMap and adding the key-value pairs to the result.

• Algorithm:

  1. Create a HashMap map to store the value as the key and the total weight as the value.
  2. Iterate through items1 and items2 and update the total weight for each value in the map.
  3. Construct the final result array by iterating through the HashMap and adding key-value pairs to the result.

• Time Complexity: O(n), where n is the total number of items in both arrays.

• Space Complexity: O(n), to store the unique values and their total weights.

import java.util.*;

class Solution {
    public int[][] mergeSimilarItems(int[][] items1, int[][] items2) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int[] item : items1) {
            map.put(item[0], map.getOrDefault(item[0], 0) + item[1]);
        }
        
        for (int[] item : items2) {
            map.put(item[0], map.getOrDefault(item[0], 0) + item[1]);
        }
        
        int[][] result = new int[map.size()][2];
        int index = 0;
        
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            result[index][0] = entry.getKey();
            result[index][1] = entry.getValue();
            index++;
        }
        
        Arrays.sort(result, (a, b) -> a[0] - b[0]);
        
        return result;
    }
}