Shared Inventory Identifiers

🎯 Level: Easy ⭐ Score: 30 ⏱️ Estimated Time: 30 mins
📜 Problem Description

Zoblik International, a sprawling global manufacturing company, manages a vast network of warehouses. Each warehouse meticulously maintains its inventory records, specifically a sorted list of unique product identifiers (SKUs) currently in stock.

For an upcoming company-wide sales event, the marketing and logistics teams need to identify all products that are simultaneously available in two specific major warehouses. This means finding the common SKUs that exist in both inventory lists. If a particular SKU, say 'Product A', appears three times in Warehouse A's list and twice in Warehouse B's list, it indicates that three units are in Warehouse A and two units in Warehouse B. In this scenario, the 'intersection' would include two occurrences of 'Product A', as those are the units that are common to both stocks.

Your task is to write a program that takes two sorted lists of product SKUs (representing the inventories of two warehouses) and returns a new sorted list containing all the SKUs that are present in both. The resulting list should maintain the count of common duplicates.

Input Format

The first line contains an integer 'T' denoting the number of independent test cases.

For each test case:

  • The first line contains two integers 'n' and 'm' denoting the number of SKUs in Warehouse A's list and Warehouse B's list, respectively.
  • The second line contains 'n' space-separated integers, representing the sorted list of SKUs from Warehouse A.
  • The third line contains 'm' space-separated integers, representing the sorted list of SKUs from Warehouse B.

Output Format

For each test case, print the space-separated numbers denoting the common SKUs (intersection) found in both warehouse inventories. If there are no common SKUs, print an empty line.

Constraints

  • 1 <= T <= 100
  • 1 <= n, m <= 104
  • 1 <= Ai, Bi <= 105 (SKUs are positive integers)
📌 Constraints
1 <= T <= 100; 1 <= n, m <= 10^4; 1 <= Ai, Bi<= 10^5
📝 Sample Input/Output

  
Sample 1: Basic Intersection

  
Input:
4 4
1 2 3 4
1 3 4 5
Output:
1 3 4


  
Explanation: Warehouse A has SKUs [1, 2, 3, 4] and Warehouse B has [1, 3, 4, 5]. SKUs 1, 3, and 4 are present in both lists. SKU 2 is only in A, and SKU 5 is only in B.


  
Sample 2: Intersection with Duplicates

  
Input:
4 5
1 1 3 3
3 3 4 5 6
Output:
3 3


  
Explanation: Warehouse A has two units of SKU 1 and two units of SKU 3. Warehouse B has two units of SKU 3, one of SKU 4, one of SKU 5, and one of SKU 6. Both warehouses share two units of SKU 3, so [3, 3] is the intersection.


  
Sample 3: General Case with Multiple Duplicates

  
Input:
8 6
1 3 4 5 5 6 6 7
2 5 6 6 7 8
Output:
5 6 6 7


  
Explanation: Warehouse A has SKUs 1, 3, 4, two units of 5 (5, 5), two units of 6 (6, 6), and 7. Warehouse B has SKU 2, one unit of 5 (5), two units of 6 (6, 6), 7, and 8. The common SKUs are one unit of 5 (since B only has one), two units of 6 (since both have two), and one unit of 7 (since both have one). Therefore, the intersection is [5, 6, 6, 7].
💡 Hints
  • 💡 Consider using a two-pointer approach, as both input arrays are already sorted. This allows for an efficient single-pass solution.
  • 💡 Think about how to handle duplicate elements. If an element appears multiple times in both arrays, each common occurrence should be included in the intersection.
  • 💡 Ensure your algorithm correctly advances the pointers when elements are not equal, and when an element is added to the intersection. One pointer should only advance if its current element is 'too small' or if it matches an element in the other array.
📚 Topics

Two Pointers

🏢 Asked By Companies

Facebook, Google

😕 No submissions found

Start coding and your submissions will appear here.