Intersection of Two Arrays (C++) | Data Structures & Algorithms | Top Interview Question Explained

Hello, hello, hello. So, today we are solving data structure and algorithm questions which are asked in companies interview or interview questions. So, before starting the video and before explaining you the problem and we will talk about how the problem works, what the structure of the function is. Before doing all that, I just I just want to tell you that if you want to watch the same video in Hindi, the Hindi version of this video, the link for that video will be provided in the description. If you want to read about this code and understand for yourself, the link for that will be provided in the the description below. The explanation for the code is written in English, Hindi and English. So, whatever language you are comfortable in, English is a combination of Hindi and English. So, you can read it for yourself. So, let's start the question and let's first read the question and understand what the function structure how the function structure is and I will in this video tell you about the pairs and the map because to solve this question you have to know the know about pairs, what pairs means and what map is. So, we will go step-by-step. So, the problem states that you have given a two arrays or a list. So, problem says, okay, we have a two arrays here. So, this is an array and this is an array. So, somewhere something like this, array one and array two. So, we are given a two array and as I can see we have given a length of an array and an M. So, consisting of N and M integers. So, let's say array one is of size N and array two is of size M. Okay. So, what we have to do? Your task is to return the number of element common in array one and array two and the number of element in the union of array one and array two. So, let me break this down. So, what it's it is actually saying that there is some element which are common in array one and array two. Let's say um this five, six, one two and it is five one eight nine. So, the common element in array one and array two is five and one. So, we have to return the common element. And what we have to return? We have to return the union of array one and array two. So, the union of an array one. So, we have to then like say that array one The union is basically combination of array one and array two minus the common element. So, we can say the combination of array one is we the size of array one plus combination of array two is the size of array two minus union. So, union is basically the common elements. Okay, I will like I will make you understand. So, you or you can say not union but interaction intersection. Well, that would be a good term. So, the intersection interacting because these two elements are common. So, if we don't minus the intersection element, then these elements will repeat in the like uh in the output. So, let's now understand the structure of this problem. So, I told you that this problem have a array one which is this, array two which is this, the size of array one which is this and if I like scroll this there just a second. Struggling with this. So, if I scroll this uh right side, so we have array M, the size of array two. Okay. So, this will take these elements. What is this? What is pair int int? So, we have to and then as I said in every video that this is a function name. You can write any function name but because I'm doing an ID, I would not change because this function name would have been injected in the main function of this ID which runs the code. So, let me first explain what is pair and let me explain maps because pair and maps are important for this problem to understand. So, what is a pair? So, if we say let's say this is a vector. This is a whole vector and this is let's say I will take three index. So, this is index zero, this is index one and this is index two. So, pair is nothing but let's say at index zero here we have a pair. So, let's say we have a pair of element. It is saying we have a pair of element of int int. So, at index zero let's say we have stored one, two. Then at index uh one we have a stored three five at index two we have a stored eight, nine. So, when we say that array at I-th index and if that I-th index is zero, what is the value at that index in form of pair, then the value which is stored at zero-th index is our one and two. This is known as pair. Right? We have stored integers, we have stored strings, we have stored boolean and everything. And this is how pairs are stored. And then what is map? Then just a sec. Let me first erase this. What is map then? So, map is nothing but as but the value I won't say pair because you will get get confused but key value pair. Key value pair, what is key value pair? So, here the value will be stored and here the key will be stored. The best example to understand map like everyone in the school has their roll call or roll number. So, when a teacher say a particular roll call or a roll number, a particular students raise up and say present or absent or anything. Then the roll call which you are assigned is is your key because let's say I have given a roll call of 10. And if my teacher says, okay, roll number 10 or roll call 10 present or not, I will go ahead and say present or abs- absent. That means that 10 is a key which is assigned to me. So, whenever a 10 key is called, the value which is me is uh present or not. Yeah, so it is a basically key value pair uh which stores values. So, map is used in that way. So, let me write the code and I will break it down as we write the code, right? So, I hope you understand. We have to return a pair. We have given two arrays and an M is there. And now let's write the code. So, we have to have something which can store the inter- intersection because we have to minus the intersection and as the problem states we have to have a uh union array. So, how we assign a array? How we assign a map? So, we go ahead and say un- o r d e r e d unordered map. And because it takes key value pair, then we will use this arrow. And we know we want a uh key to be integer and we want our this value to be integer, right? And we will name this map as map, very original. So, we have a unordered map of type integer and integer and then we're assigning that map a name of map. Okay. Now, what we have to do? So, we have to store the values and the keys for array one and array two. So, how we can do that? So, we have given an So, we can do that, okay, go through all the elements array array one traverse all the element till N. The size of an array one is N. So, go through this this this and this. Go through this and do what? Store the element of array I. Let's say we are saying we are assigning integer pointer to be I. So, I will go from zero, one, two and three. So, go through all this and because we are traversing we will say plus plus. And store this value in our map. So, how we will store? So, this is how our traversal will work and I will say store it into the map. So, we will say array I and plus plus. So, go through the array I like a uh our array and store all the elements which is at I index. Let's say I the element at I index is zero or one or two any element. Uh store it into the map and move the I index uh I pointer ahead. So, this is how you store an element in a map. And we have said that we need an intersection. So, we will say int inter section and we will assign that as zero because we don't have any intersection yet. So, we have assigned the intersection zero. Okay. So, this is how our all the elements of our this array one will get stored. Okay. Now, the part for array two. So, all the elements which are stored in it our map, so how it will look? So, after doing this uh map will have value of array one here and the key here. So, all the keys for values at array index I the value will be stored here and the key will be assigned here. Let's say zero, one, two. Right? And we will say go through all the element at array two. So, we'll say okay, now the array one part is done. So, let me erase this. Now, go through array two which is our second array. Go through array two which is of size M. Go through array two and if array two is greater than zero like if map because initially the map would be zero. So, when the map is made initially, all the key and value here. Value is zero. All the values is here zero because there is no repetition. Let's say I index is here. Then the value of I index is zero because it has occurred one time, then this and then this. So, if after this map array I plus plus, all the values are stored in this and the key at the key part and the value for that is zero. But, uh when we go through all the elements in array one, this all zero becomes one because that element occurred one time. Then the second element occurred in the array one two time. Then the second element array occurred in array one third time. What I'm saying? No, no, no. Scratch scratch that. So, let me write this down because I'm uh I myself is getting confused in the trail of thoughts. So, initially all the values are zero. So, when the element at array of array I array one array one at I index is stored here, this value will change it to one because the value now is stored here and now this count will be one. The value of second index is stored here, then this zero will become one because the count has increased to one. Then this value has been stored, then this zero will become one because now the element is present. So, this is how the map will work, right? And then when we go through all the element at array two and we will check if any element of array two is greater than zero which means one. That means that element of array two which is present. Let's say five is present in array two and five is present in our map which is now one because the count is one. If it is greater than zero, that means this element is common in array one and array two. Right? Then we will go ahead and say intersection plus plus because we got one intersection here. And we will deduct that element from array two. So, we will deduct the element from array This is array two. This is index at that element is present and we will say minus minus. So, we will do that. So, let me just write the code and I will try to make things clear while writing the code. So, what we have said first we have assigned the map. Okay, we have assigned our map. Then we will say okay, go through array one. So, go through all the element at array one and make a map. Let's say five uh one three two. So, when the map is assigned it is assigned like this. Here the count is zero, zero, zero and zero. Wait. Zero. And five, one, three, two. But, this will be plugged after we go through the loop. So, this will be the initial thing. Then we will go ahead and say okay, we have assigned a value, then we will say for I it starts with index zero. It will go the size of array one which is N. And then I plus plus. It will go through all the elements and the index of array one and we will make this count one because this element is present in this array one uh array or vector. So, every time you will go through it we will make it one. So, let's make this one. So, after traversal the five will become the count for five will become one. The count for one will become one. The count for one will three will become one and count for two will become one. So, okay. Let's do that. So, then we will say okay, we we have to store it in map. What we have to do? We have to store array one at I. The element I of array one we have to store in map and we will say plus plus because the pointer will move ahead. Okay. So, we did that. Now, the array second part will come. Okay. Let's assign a variable which will track the intersection thing. So, we have said int intersection. Okay. We have assigned that. So, we'll say that for we will go through all the elements in array two. So, for int J is equals to or we can say I because we are outside the loop. We can also say this is I. So, the I think I can write this as J A K anything. But, I'm writing this as I because I want to there is a confusion that if if uh we have used I we can't use I like few students have confusion that if you have used I, you can't use I again. But, that's not the case. If you the the for loop ends here, you can use I again because this I is applicable for this for loop. This I will be applicable for the this array two for loop. So, I is equals to equal to zero, then I would go to M the size of array two, then I plus plus. And while we we go through array two, we will check whether this element is present in our map or not. So, we will go ahead and say if array two uh I is greater than one. But, this will not work because we are checking of checking array two I but not in a map. So, we have to do this because we have to check that element in map is greater than zero. Then what we have to do? We have to say okay, this is an intersection. Because these elements are common, so we will say intersection plus plus. Okay. So, we found our intersecting element and then we will remove our intersecting element from array two. So, map array two I minus minus. So, we removed that element. So, we found our intersection. We found which uh array uh we don't want. Okay. Now, the second part of the question is we need a union of array one and array two. So, that's easy. The union for that, as I told you, is n plus m, the combination of array uh element of array one and the combination of uh the element of array two and uh minus intersection. So, after this loop, after this loop, we will say int uh union n size union size is equals to n plus m minus minus inter- section. So, the size of array m, the size of array one, and the size of array two minus intersection. And because we have to return a pair, because we need have to return a pair here, so we will say return we will make a new pair, and I will name it as make pair. So, what we have to return? We have to return two integers, and we are getting two integers. Make pair. Int intersection is a integer, and union size is an integer. So, we'll we will uh return a pair here. So, I'm making a pair because this is an integer, and this is an integer, and I'm returning a pair uh which holds two integers. So, let's run this. And as you can see, all the test cases pass are passed here. And this is how you can solve this question. But if you want to read this code uh in detail, the link will be in description. I know this is a little complicated code because we are using maps, then we are using pairs, uh and we are going through all this, and we are making an intersection and union, and everything. But uh when once you get the hold of pair and map, it is easy. But if you want to read about this, go ahead, and the link is in the description. And if you want to watch this same video in Hindi to explain it more clearly, so that link is also in the description. You can go ahead and watch the Hindi version of this video. I will see you in the next video. Bye-bye.