algoadvance

Leetcode 2363. Merge Similar Items

Problem Statement

You are given two 2D integer arrays items1 and items2 representing items, where each item is represented by a pair of integers: [value, weight]. The value of the item denotes its type, and the weight denotes its quantity of that type.

• items1 and items2 contain distinct values, i.e., no two items will have the same value within the same array.
• Merge the two items lists in such a way that any items with the same value are combined by summing their weights.

Return the merged list in ascending order of the value.

Clarifying Questions

1. Q: Can an item have a negative weight?
   • A: No, all weights will be non-negative integers.
2. Q: Can an item have a zero weight?
   • A: Yes, it is possible for an item to have a zero weight, although practically unlikely.
3. Q: What should be the format of the returned list?
   • A: The returned list should be a list of lists, where each inner list contains two integers: [value, weight].
4. Q: How are the items sorted in the final list?
   • A: The items in the final list should be sorted in ascending order based on value.

Strategy

1. Use a hash map to store the combined weights for each unique item type (value).
2. Iterate through items1 and add each item’s weight to the corresponding entry in the hash map.
3. Do the same for items2.
4. Convert the hash map to a list of lists.
5. Sort the list of lists by the value.
6. Return the sorted list.

Code

import java.util.*;

public class MergeSimilarItems {
    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
        // HashMap to store the combined weights for each item type
        HashMap<Integer, Integer> itemMap = new HashMap<>();
        
        // Add items from items1 to the hash map
        for (int[] item : items1) {
            int value = item[0];
            int weight = item[1];
            itemMap.put(value, itemMap.getOrDefault(value, 0) + weight);
        }
        
        // Add items from items2 to the hash map
        for (int[] item : items2) {
            int value = item[0];
            int weight = item[1];
            itemMap.put(value, itemMap.getOrDefault(value, 0) + weight);
        }
        
        // Convert the hash map to a list of lists
        List<List<Integer>> mergedItems = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : itemMap.entrySet()) {
            List<Integer> mergedItem = Arrays.asList(entry.getKey(), entry.getValue());
            mergedItems.add(mergedItem);
        }
        
        // Sort the list by the value
        mergedItems.sort((a, b) -> Integer.compare(a.get(0), b.get(0)));
        
        return mergedItems;
    }

    public static void main(String[] args) {
        MergeSimilarItems solution = new MergeSimilarItems();
        int[][] items1 = \ use example from above
        int[][] items2 = \ use example from above
        List<List<Integer>> result = solution.mergeSimilarItems(items1, items2);
        System.out.println(result); // [[1, 3], [2, 3], [3, 5]]
    }
}

Time Complexity

• HashMap Operations: Inserting into the hash map and searching for keys are average O(1) operations.
  • Processing items1 and items2 is O(n1 + n2), where n1 is the length of items1 and n2 is the length of items2.

• Converting to List: Converting the hash map to a list is O(n), where n is the number of unique keys in the hash map.

• Sorting: Sorting the list of merged items is O(n log n).

Overall, assuming a sorted output list of unique items, the time complexity is:

• O(n log n), where n is the number of unique values in the merged items.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?