using System;

using System.Linq;

using System.Collections.Generic;

using System.Text;

​

/*

​

****************This is optimized Solution - UNDER CONSTRUCTION TLE *****************

​

Link: [https://www.scaler.com/academy/mentee-dashboard/class/23423/assignment/problems/10203?navref=cl_tt_lst_nm]

Problem Description

​

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 <= 105

​

1 <= A[i] <= 109

​

​

​

Input Format

First argument is an integer array A of size N.

​

Second argument is an integer array B of size M.

​

​

​

Output Format

Return an integer array denoting the common elements.

​

​

​

Example Input

Input 1:

​

 A = [1, 2, 2, 1]

 B = [2, 3, 1, 2]

Input 2:

​

 A = [2, 1, 4, 10]

 B = [3, 6, 2, 10, 10]

​

​

Example Output

Output 1:

​

 [1, 2, 2]

Output 2:

​

 [2, 10]

​

​

Example Explanation

Explanation 1:

​

 Elements (1, 2, 2) appears in both the array. Note 2 appears twice in both the array.

Explantion 2:

​

 Elements (2, 10) appears in both the array.

*/                  

public class Program

{

    private static List<int> getCommonElem(Dictionary<long, long> atmpDict, Dictionary<long, long> btmpDict){

        List<int> resultantCommonElem = new List<int>();

        int aDictCount = atmpDict.Count();

        int bDictCount = btmpDict.Count();

        Console.WriteLine("Length of Dictionary A and B is {0} and {1}", aDictCount, bDictCount);

        for(var j = 0; j < aDictCount; j++){

            if(btmpDict.ContainsKey(atmpDict.ElementAt(j).Key)){

                long curr_ADictValue = atmpDict.ElementAt(j).Value;

                long curr_BDictValue = btmpDict[atmpDict.ElementAt(j).Key];

                long min_DictValue = (curr_ADictValue <= curr_BDictValue) ? curr_ADictValue : curr_BDictValue;

                for(var k = 0; k < min_DictValue; k++){

                        resultantCommonElem.Add((int)atmpDict.ElementAt(j).Key);

                }

            }

        }

        return resultantCommonElem;

    }

    private static List<int> Solve_CommElem(List<int> A, List<int> B)

    {

        Dictionary<long, long> aDict = new Dictionary<long, long>();

        Dictionary<long, long> bDict = new Dictionary<long, long>();

        List<int> resultantCommonElem = new List<int>();

        int aCount = A.Count - 1; int bCount = B.Count - 1;

        while(aCount >= 0 || bCount >= 0)

        {

            //Ensure A is wihtin the index boundary

            if(aCount >= 0){

                if(aDict.ContainsKey(A[aCount])) {

                    long tmp = aDict[A[aCount]] + 1;

                    aDict[A[aCount]] = tmp;

                }else{

                    aDict[A[aCount]] = 1;

                }

            }

            //Ensure A is wihtin the index boundary

            if(bCount >= 0){

                if(bDict.ContainsKey(B[bCount])) {

                    long tmp = bDict[B[bCount]] + 1;

                    bDict[B[bCount]] = tmp;

                }else{

                    bDict[B[bCount]] = 1;

                }

            }

            aCount--;

            bCount--;

        }

        //Dictionary Area

        resultantCommonElem = Program.getCommonElem(aDict, bDict);

        return resultantCommonElem;

    }

    public static void Main()

    {

        //List<int> A = new List<int>() { 1, 2, 2, 1 };

        //List<int> B = new List<int>() { 2, 3, 1, 2 };

        //List<int> A = new List<int>() { 2, 1, 4, 10 };

        //List<int> B = new List<int>() { 3, 6, 2, 10, 10 };

        List<int> A = new List<int>() { 8, 15 };

        List<int> B = new List<int>() { 10 };

        List<int> commElem = Program.Solve_CommElem(A, B);

        Console.WriteLine("Common Elements are: " + string.Join(" ", commElem));

    }

}