Leetcode 1722. Minimize Hamming Distance After Swap Operations | Daily Challenge

Añadido: 2026-05-05

[00:00:02]Hello everyone. Welcome back to the channel. I hope you all are doing pretty fine and we will do today's daily challenge on lead code and we will try to solve it together. Okay, so let's see the problem statement and try to understand it in detail.

[00:00:18]So minimize Hamming distance after swap operations. You are given two integer arrays source and target both of length n. You are also given an array allowed swaps. Okay, where each allowed swaps tells you the index number that you can swap uh at the source array. Okay, so you you are given two arrays source and target and you are allowed to make some swaps between the source target index and between which two indices you will make a swap that is given in the allowed swaps. Okay.

[00:00:49]Uh so it is a vector of pairs.

[00:00:51]So note you can swap elements at a specific pair of indices multiple times in any order. Hamming distance of two arrays of same length source and target is the number of position at which the elements are different. Okay. So number of indices I where source I is not equal to target I. So your objective should be to make this source array as equal as possible with this target array. Okay, by performing these allowed swaps. So this is your this is your whole motive for this problem. So and you want to see that minimize this Hamming distance. So if you make as many as elements of source array and target array equal, then the number of such positions where it is not equal should be minimum, right? And that will be only the minimum Hamming distance of the source and target after performing any amount of swap operation. Okay. So yeah, I hope at least the problem statement is very very much clear to you. And if you see uh this is the source array 1 2 3 4 target array is 2 1 4 5 and you are allowed to make a swap between index 0 and 1. So if you do it do that, you a 1 and 2 will become 2 and 1. You see that will match with the target array. Okay.

[00:02:11]And uh when you do a swap between 2 and 3, that will make that uh 3 4 to be 4 3 and 4 and 4 will match. 4 at this position also will become the 4 at this position.

[00:02:25]Only the 3 and 5 will not match and that that's why at one position we have an unmatching element. That is why uh we have the output to be one. Okay, I hope you do understand the problem statement very clearly as well as this example and there is no uh doubt in the question now at least.

[00:02:44]Okay.

[00:02:45]So uh what you need to do basically is you have this source array.

[00:02:53]Okay, you want to make as many corresponding elements of this source array to be equal to this target array. Okay.

[00:03:01]So how you will do it? So let's say you if you have one number one over here.

[00:03:07]Okay. And another number for target is one over here. Now you can make changes in the source array. By changes I mean that you can make swaps in the source.

[00:03:18]Okay. So let's say you swap this element and some element here. You swap between them and one becomes here. One comes here. Then again you swap between this and this and one will come here.

[00:03:32]Okay.

[00:03:33]Uh then again you make a swap and you see that one will come over here and uh it is the corresponding position of the target array also where one is present.

[00:03:44]So you are successfully able to bring this one all the way to this by a series of swaps.

[00:03:51]Okay. So uh if I ask you the question if I ask you a simple question that uh can you bring this one? So can you bring the source position one source array source array one this in this particular example if can you bring this one to the corresponding position here? Can you swap and bring this one or is it not possible or to swap and bring at all? So can you bring the source array one to the corresponding target array position?

[00:04:36]Corresponding target array position. So this is my question which I will try to answer. Okay.

[00:04:44]So the question the answer to this will lie in the allowed swaps array. Which which elements we are allowed to make a swap.

[00:04:51]Okay. So let's say in the allowed swaps there is a pair 0 {comma} 2.

[00:04:58]Then there is again a pair 2 {comma} 4. Then there is again a pair 4 {comma} 5. What does this mean? So let's say uh there is an element at position one of this uh so let's say mm the source of zero. These are indices, right? These are the nothing but index numbers. So source of zero is nothing but this element one.

[00:05:26]This example only we are dealing with.

[00:05:28]Okay.

[00:05:29]And let's say this is six.

[00:05:32]This is index number six and this is index number zero. So uh not six. Let's say this is five.

[00:05:40]So uh if you have a one over here at the source of zero, we can swap this position one zero with position two. So it mean it means that one can go with this. So if you have a zero and one you can swap a one which is present over here to this. Okay. And then you see two can also be swapped with four. Okay.

[00:06:07]So then again now one is present at the index two. So after swapping after swapping source of zero was one, now source of two is one.

[00:06:17]Now when you swap two and four, source of four will become one.

[00:06:22]Okay.

[00:06:23]Source of four will become one.

[00:06:26]Okay. So you are able to bring this one all the way till four and if four and five can also be swapped, then we see that we can bring the one all the way till five. So we can see that this get an idea of a graph over here.

[00:06:44]This allowed swaps is nothing but the edges of the graph. And if a one is present at two or at four or at zero, it can be brought to five.

[00:06:56]Or if it is a present at four, it can be brought at zero.

[00:07:01]Can be brought at two. It can be brought at five. So you want to see that if So answer to what?

[00:07:09]Answer to this question. Can you bring the source array to the corresponding target array to the target position? Okay.

[00:07:15]If the one lies in the same component of the graph in the same component of the graph formed by allowed swaps array. Okay.

[00:07:34]Formed by uh graph which is formed by this uh allowed swaps. Whatever that array is. If you form a graph graph with that and if one lies in the same connected component of the graph as the source and target positions source and target positions, then they can be definitely brought. Okay. So I might mean to say that if this zero which is in the source target source position.

[00:08:02]Okay.

[00:08:03]This zero which is in the source position is also and the five which is in the target position. This zero and five both of them belong to the same component in the graph then definitely they can uh the any anything can be moved within any pair. Okay. And let's say your graph looks complicated something like this.

[00:08:25]So let's say zero. Let's say two. Let's say some seven comes over here.

[00:08:31]Can be a four over here. Can be a five over here. Can be a eight over here. So eight can also be brought to uh zero. Seven can also be brought to eight. Seven you swap with two, then you swap with four, then you swap with eight. So an an element present at the position seven. Let's say that element is 100. So that 100 can be brought all the way back to any position in this component of the graph. So I hope that is very clear. So uh what you need to check what you need to check is that another way of saying it is that uh in a in a connected component of graph, okay, in a connected component of graph, you need to check that out of these indices, how many So they they belong to a particular group. So let's say I will call them group one.

[00:09:19]Or I will call them these zeros group.

[00:09:21]Okay. I will call them a zeros group or I will name the group anyway. Okay.

[00:09:25]So in a particular group, I will check that see and now in this particular group, which elements are present? 0 2 4 5 7 8.

[00:09:35]So in this particular group number one or zeros group or whatever, this all of these elements are present. Okay.

[00:09:42]Now these these elements are nothing but the index index numbers. Okay. Now we know that within these index number, we can swap anything with anywhere. Okay.

[00:09:51]Now I want to check that how many uh numbers which are present in these indices are also present in the source and target both of them, okay? So, let's say at position zero we have in the source array we have a five 50, let's say. At position zero we have a 50 which is present. At position five, let's say in the target array we have a 50. So, that five and zero can be brought to each other, okay? So, this is all I want to check that in a particular group in a particular group uh how many equal elements are there within the source and the target in a particular group? If those elements are there, they can be brought to the same index, no matter what. And some elements which are not there uh some things some elements which are not matching. So, let's say you have a 49 in a source added, okay? Let's say in the source of four okay? You have a 49 present.

[00:10:51]And that 49 is not present anywhere in the target array. So, that 49 will only contribute to the Hamming distance, okay? Because they cannot match match with each other. Or let's say this 49 is present in some different component. So, let's say it is present in three, which is three four, let's say another component is there of the same graph.

[00:11:12]Uh not four.

[00:11:14]Three six. Because four is over here.

[00:11:18]So three and six, if they are in a different component, they cannot be brought into this component as they're not connected by any edges. Okay, guys?

[00:11:27]So, I hope you the approach is very much clear to you now and you can also try to solve this on your own first.

[00:11:34]Yeah. Um this can be solved with definitely in a better manner with DSU, but yeah, I do not want to cover the background of DSU right now. So, I will try to go with uh simple solution of normal graph. So, I would like to change these variable names as these are very long.

[00:11:57]Right? So, I will call them just source target.

[00:12:02]And allowed swaps, I will call them AS, okay?

[00:12:07]So, this will be nothing but S.size.

[00:12:10]Uh This is nothing S.size is nothing but the number of components in the graph.

[00:12:17]Not not the components, number of nodes in the graph.

[00:12:20]And we will try to make the graph, which is nothing but an adjacency list. I hope you all at least know how to make a graph. And that much I'm assuming, okay?

[00:12:30]So, while this adjacency list, it shouldn't be not at all difficult to make this graph, okay?

[00:12:37]So you can just cover through all the edges. So, these are the edges of the graph. So, you just go through all the edges.

[00:12:44]So uh int i equals to zero, i less than edges.size, i plus plus, and adjacency list of source to uh see these are the pairs which are there in AS, okay?

[00:13:02]So, AS of i zero is one element uh So, this push back of uh AS i one, okay? So, I hope you do understand what I mean to do.

[00:13:22]Uh the u and v I'm just pushing them.

[00:13:28]So for better convenience you could have also made this as the first edge So, u {comma} v, let u {comma} v be the edge of the graph.

[00:13:41]And you just want to connect u with v and v with u. That's all you need to do.

[00:13:47]So, yeah.

[00:13:51]And do it together.

[00:13:55]Uh it's nothing but v. And this whole thing will be u.

[00:14:00]Okay?

[00:14:01]So, yeah. That is all That is all.

[00:14:04]Uh the graph is just made. And definitely you need a visited array when you are traversing through a particular uh graph you need to see that which elements you have already visited or not. I hope these things are pretty standard. And uh as I told you you need to see which group, okay? So, this like say this is group number one.

[00:14:26]And you see that in group number one these elements are present. So, I definitely I will not use some different marker. I will pick the first edge uh as the name of the group. This is zero group, I will tell, okay?

[00:14:39]So this is the group number uh So uh what I'm making is basically a map.

[00:14:51]So, each element will map that which group I'm part of. So uh zero will say that I'm belonging to zero's group. Two will say that I'm in zero's group. Four will say that I'm in zero's group. So, if this group is zero every element will map to zero, okay?

[00:15:07]So, so group number I will get very easily from each and every element. That is why I'm making this group mapping.

[00:15:17]Group mapping element to group number.

[00:15:23]Okay? This is the map which I'm making in this.

[00:15:27]So, initially I will say that each element is mapping to itself only.

[00:15:33]Or anything you might do, right? You can say that this is mapping to all are mapping to zero or all are mapping to one, whatever whatever you can do. Initially I will do that uh every group is mapping to itself only, so this thing I will just do it. And uh I will perform a DFS traversal with uh the knowledge of component.

[00:15:57]So, yeah.

[00:16:00]I will iterate through all the nodes.

[00:16:04]I'll see that if this node is not visited.

[00:16:08]Okay?

[00:16:09]So, if this node is not visited uh then I will call a DFS.

[00:16:16]Now, in this DFS function only I will assign this group numbers and everything.

[00:16:21]So, I need this starting vertex of my traversal. This is my starting vertex of the traversal.

[00:16:29]Uh I have the adjacency list, that is the graph. I need the visited array. I need this group array because I need to change uh Another thing which I need is the group number. When I'm calling this, I'm telling that starting vertex is i. So, I will let's say pass this again. See, starting vertex will change again and again due to this recursive call.

[00:16:51]So, uh I need to pass an i once again because the starting vertex will only be the group number. So, I will say that this is the i's group, okay?

[00:17:01]So, last index I give i because this is the i's group.

[00:17:05]And I just say that that element is my group name, okay? This is my group name.

[00:17:11]So, I will while assigning the group name I will be using that.

[00:17:15]So, let's look into the DFS function.

[00:17:19]So we have uh void DFS and this is our starting vertex, okay?

[00:17:28]And we have this vector of vector as the adjacency list.

[00:17:33]Okay?

[00:17:34]And then we have visited also, so vector of int uh we'll pass everything by reference.

[00:17:43]And vector of group also we have. We even want to mark the group numbers, okay?

[00:17:48]And let's say this let's call this as a top element, okay?

[00:17:53]Group number or whatever. Let's call this as the top element, okay?

[00:17:57]And uh what we want to do initially is that mark that the group of this starting vertex is nothing but uh this top element. This is what I want to mark. And visited of this starting vertex is also one uh which I must mark, okay? That I have visited this particular cell. And now I want to do is that I want to recursively uh traverse through all the connected components, okay?

[00:18:27]So, this particular What are the adjacent vertices of this particular starting vertex? I first need to see.

[00:18:35]So uh adjacent of this starting vertex.size. So, this is These are all the neighbors of the starting vertex, you can tell, okay? That particular node uh these are all the neighbors of them.

[00:18:50]So, uh I want to iterate through the neighbors, okay? And I want to call them recursively.

[00:18:55]So, let's say um neighbor is what? Adjacent to uh this particular starting vertex and i. So, this is my i'th neighbor, okay?

[00:19:10]And if my i'th neighbor is not visited okay?

[00:19:17]I will uh call a DFS function again. So, this DFS function is just to group all the elements to assign every element to its particular group uh so that we can easily access that whether these two components are belonging to the same group or not. So, this thing we can easily do it. So, uh this is nothing but neighbor and adjacency list visited and in this group we have also we have this top element. So, yeah.

[00:19:51]That is all with the DFS function. Now, we once I have this group naming, I want to see that for the this zero, group number zero, these many elements are there. So, I can try to use a map for that. So, map the key value of the map will be zero.

[00:20:09]I will tell that this is the group and these are the elements which are in the group, okay? So, zero contains zero, two, four, five, seven, eight.

[00:20:19]Okay?

[00:20:20]And if this is another graph, three, six, so we can mark that also.

[00:20:26]So, we can call this three's group. So, three's group consists of three and six.

[00:20:34]Something like this, okay? So, we need a map.

[00:20:37]We need a map.

[00:20:39]Integer {comma} vector of integer.

[00:20:41]Okay, I hope you are not getting confused.

[00:20:44]So, I need this particular map to see this, okay?

[00:20:50]So, uh in order to do that, what should I use? Definitely, I will use an unordered map and not a normal map because unordered map generally gives a better time complexity.

[00:21:07]It has an amortized of one. So, uh we have this map where we will store this integer {comma} vector of integer.

[00:21:15]And how can I just group all the elements? So, we'll just iterate through all the index, okay? And I will just say that map of this group of I. So, whichever group number this I is belonging to, you just push back that in that particular group, you just push back I. Okay?

[00:21:37]So, whichever group number, so let's say this I is belonging to group number zero, in corresponding to the zero, you push me, you push myself, okay? Push this particular I. That is what uh is happening here and yeah.

[00:21:53]Once we Now, we are See, we are also having this map ready. Now, it is very easy. Now, everything becomes very easy.

[00:22:00]I can just check uh what all is there with the source and what all is there in the destination, okay? Source and target. And whichever element is present in the source and not in the target, I can count that element towards my uh Hamming distance, okay?

[00:22:21]So, So, now what I will do, traverse in each group, okay?

[00:22:33]And we have the groups already, right?

[00:22:34]So, we can simply traverse in each group and check how many elements are common, right? Are common in each uh connected components.

[00:22:50]Traverse in each group and check how many elements are common to both this source and target. I hope that you understand. Uh I need connected components.

[00:22:59]Rest of the non-common element form the rest of the non uh common element form the Hamming distance result.

[00:23:13]Hamming distance result, okay? So, yeah, that is it. That is what I wanted to say. Uh this is an important thing, so I just wrote it down. This is the Hamming distance answer which we will return it after updating. And now, we want to iterate through this map, okay? So, what we will do is iterate through this map.

[00:23:33]So, auto I on this map, okay? So, I Because I have group-wise iteration I need to do, okay?

[00:23:42]So, uh I am extracting the second element of the map, okay? So, positions at which these elements are present. So, second element of the vector, as you know, is a vector of the map is a vector, right? And this is the group number, so in this group number, these many elements are there, these many positions of the elements are there because they are index numbers, right? So, I can do I.second, okay?

[00:24:11]So, if you know, map stores as a pair of key {comma} values, okay? So, this is nothing but a value. So, uh we have this and we will keep another unordered map check, okay?

[00:24:30]Now, why Why exactly is this map is that I will check in this map that uh this particular element which is present in the source and the target, okay? How many times it occurred? Now, there can be multiple elements also, right? So, let's say a two occurs.

[00:24:48]So, in some positions, see See, the positions we are having, we are iterating according to the groups. That is all fine. But in the source array, let's say there are two In in in actual array I'm telling, okay? In the actual source array, in some positions, there are two twos and in other positions, there are let's say three twos. And by grouping and all, you see that they all belong to the same group somehow. So, they can be swapped with each other, okay? So, you can bring two of the twos into this. And the And the remaining two will still be contributing to the Hamming distance, So, this thing we need to take care of this.

[00:25:26]That is why this check becomes important. I need to check that how many times this two occurs in this in this source array. So, this check value uh will store check map will store that two occurs two times here and two occurs three times here.

[00:25:42]So, that is what, right? So, if it if it was three times here, you you will store three over here.

[00:25:49]And yeah, that I hope you can understand and we will Whenever See, we got this two and we will try to decrement this value of two because one time we have used and then again, we will decrement and we will see that if it is zero or not. If it is zero, it means that we have all matched or it is not present, so uh that is basically the use of check. So, I hope that you do get it.

[00:26:13]So, this check thing we try to utilize, so J value will be nothing but pos.size and J plus plus. We are iterating now to these elements. So, for a particular group, we are now iterating through the these elements, okay?

[00:26:35]And uh I just store all of them in this check map. So, source of position of J, I will just increment the count, plus plus, okay? Uh means that I just checked whether the source array has this particular and I just incremented the count for this.

[00:26:57]While checking the target, I will decrement the count, okay? Same thing, I will same elements I will go through, iterate through for target also.

[00:27:06]And uh I will just check that if pos this check of this position of J is greater than zero, okay?

[00:27:17]So, not source, this will be target. So, now I'm entering to the target, so I will again go to the position A and just check that if it this thing. So, what does this check store? That this element already occurs in the source array. Now, for the target array, I'm seeing that is this element actually occurring a finite number of times in the source array? If it occurs, I want to use it up. I want to swap it up, okay? I want to swap it to my current position and target of pos J minus minus means that I just now swapped it, so uh the decrement the count by one. And otherwise, answer plus plus. What does this mean? So, if if else if it goes in the else, it means that this check of target of pos J is zero, right? If any if it is zero, it means that either you have used all of them or it is not present in the source only. So, something which is not present in the source, but is present in the target, it means that that is that element is not becoming equal and that is contributing to the Hamming distance and that is why we increment an answer plus plus in this case and return answer. So, that is all you see. That is all for this particular problem.

[00:28:30]If you submit this, I hope this will work fine. So, yeah. Uh Uh I changed the source to S and T, but used this source source everywhere, so yeah, let me change that back again and uh source, target.

[00:28:53]So, in order to make it small only I did, but I used this source and target everywhere, so that is why.

[00:29:00]Let's see if any more bugs are there or not. Yeah, we get the accepted thing. If you try to submit it now and see, I hope it will work just fine.

[00:29:11]So, yeah, it does work fine. It gives you an accepted value. Uh this is not a very good run time complexity, but yeah.

[00:29:18]Uh I guess you do understand the method.

[00:29:21]It is optimal only in one DFS path only.

[00:29:24]You are just uh dividing all the graph nodes into groups, okay? And for each node, you are making it remember which group you belong to. With that, you created the uh map which tells you that this group has these these these elements and you iterate through those elements and do uh store that that value is present in the source, okay? And if it is present in the target and you just try to decrement that and if it is not present you just increment the Hamming distance answer.

[00:30:02]So, that is all that is all we do. If you know uh disjoint set union DSU, you can definitely try this problem. You don't have to do anything of these at all.

[00:30:13]Okay, that needs a little bit of background. That is why I did not show that, but it will the code will become much much shorter than this. You do not need to even create the graph.

[00:30:22]Uh What you need to do is that you have the edges, you iterate through the edges, and you just union keep union the edges, and your group number will be your ultimate parent, okay? So, you can just do find of I. That will be your ultimate parent and push back of I.

[00:30:40]Directly this step you can write.

[00:30:42]So, while iterating through this as.size, we just do union of So, basically uh instead of all this, you just do union by find or union by rank, whatever you do, union of U and V.

[00:30:57]Okay?

[00:30:58]And uh directly you can jump to this step and write that something like this.

[00:31:04]Map of find of I.

[00:31:07]It means that find the ultimate parent of this I and dot push back this I. So, the ultimate parent only you can use as a marker for the group name. That is why uh the disjoint set union option becomes a very good thing here, and this thing will be this this loop will be the same as it is.

[00:31:27]So, this whole DFS function also you don't need to write.

[00:31:31]These things visited and all you do not need to write at all. So, yeah, that will become a very good alternative for that. So, you should definitely go with the DSU approach also. So, yeah, that is all for this video. I hope uh you are able to understand this solution at least. If you have any doubt, you can ask me in the comment section also. So, I will meet you in the next video.

[00:31:53]That's all for this problem.

[00:31:55]Uh yeah, that that is all.

[00:31:59]Thank you.