/* Given two integer arrays, A and B of size N and M, respectively. Your task is to find all the common elements in both the array.
NOTE: Each element in the result should appear as many times as it appears in both arrays. The result can be in any order.
        Problem Constraints
            1 <= N, M <= 10^5
            1 <= A[i] <= 10^9   */

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    
    public static int[] commonElements(int[] A, int[] B) {
        // Create a HashMap to store elements from array A and their frequencies
        HashMap<Integer, Integer> mapA = new HashMap<>();

        // Add elements from array A to the HashMap and count their frequencies
        for (int i = 0; i < A.length; i++) {
            int ele = A[i];
            mapA.put(ele, mapA.getOrDefault(ele, 0) + 1);
        }

        // Initialize a list to store common elements
        List<Integer> comList = new ArrayList<>();

        // Iterate over array B and check if each element exists in the HashMap
        for (int i = 0; i < B.length; i++) {
            int ele = B[i];
            if (mapA.containsKey(ele)) {
                // Add the element to the common elements list
                comList.add(ele);

                // Decrement the frequency in the HashMap to account for duplicates
                int freq = mapA.get(ele);
                if (freq > 1) {
                    mapA.put(ele, freq - 1);
                } else {
                    mapA.remove(ele);
                }
            }
        }

        // Convert the common elements list to an integer array
        int[] result = new int[comList.size()];
        for (int i = 0; i < comList.size(); i++) {
            result[i] = comList.get(i);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] A1 = {1, 2, 2, 1};
        int[] B1 = {2, 3, 1, 2};
        int[] result1 = commonElements(A1, B1);
        System.out.println(Arrays.toString(result1)); // Output: [1, 2, 2]

        int[] A2 = {2, 1, 4, 10};
        int[] B2 = {3, 6, 2, 10, 10};
        int[] result2 = commonElements(A2, B2);
        System.out.println(Arrays.toString(result2)); // Output: [2, 10]
    }
}