Permutation Swaps

Introduction:

You are given the permutation of unique numbers from 1 to N in the initial array(a) and the final array(b). You want to check if you can convert the initial array to the final array by applying a few operations.

You are given a 2D array(c) of size (M * 2) which contains pairs (c[i][0], c[i][1]) which tells you that you can swap the values present in the initial array(a) at the c[i][0] and c[i][1]th index. Both c[i][0] and c[i][1] are 1-based index. You can apply as many swapping operations as you want.

 

Return true if you can convert the initial array to the final array else, false.

 

Let us see a few examples:

 

Input:

a : {1, 2, 3, 4, 5}

b : {1, 3, 4, 2, 5}

c : {(3, 4) ; (2, 3)}

 

Output:

True

 

Explanation:

First, we can swap the values at the 2nd and 3rd place, making the ‘a’ array to be {1, 3, 2, 4, 5}. Now we can swap values at the 3rd and 4th place, making the ‘a’ array to be {1, 3, 4, 2, 5}. We can see that we have transformed the ‘a’ array’s permutation to the ‘b’ array; hence we returned true.

 

Input:

a : {1, 2, 3, 4, 5}

b : {5, 3, 4, 2, 1}

c : {(3, 4) ; (2, 3)}

 

Output:

False

 

Explanation:

You can not convert the ‘a’ array to the ‘b’ array by applying any number of swap operations.

 

Approach:

 

This question can be solved using graphs. We can swap the values at any pair of indices if that pair is present in the ‘c’ array. We can graph by adding an edge between all the pairs present in the ‘c’ array.

Now, we can swap the values at all the indices which are part of the same connected components.

 

We will use the concept of Disjoin Set Union to solve this question. We will join all the values in a single component in which we can do the swapping and then iterate the entire ‘a’ and ‘b’ array, and if the values at any ith index are not the same in both the arrays, we will check if both the values are the part of the same component or not. If the two values are not part of the same component at any point, we will return false.

 

Refer to the below implementation of the above approach.

 

public class Solution {          //par arry to implement DSU     int par[];          //size array to implement DSU     int size[];     public boolean solve(int[] a, int[] b, int[][] c) {         int n = a.length;         par = new int[n + 1];         size = new int[n + 1];                  for(int i = 0; i <= n; i++){             par[i] = i;             size[i] = 1;         }         /*           Joining the values           which we can swap         */         for(int cur[] : c){             join(a[cur[0] - 1], a[cur[1] - 1]);         }         /*           checking if we can           convert 'a' to 'b'         */         for(int i = 0; i < n; i++){             if(a[i] != b[i] && findPar(a[i]) != findPar(b[i])){                 return false;             }         }         return true;     }          // function to fing the par of a node.     int findPar(int u){         if(u == par[u]){             return u;         }         return par[u] = findPar(par[u]);     }          //function to join two nodes     void join(int u, int v){         int pu = findPar(u);         int pv = findPar(v);         if(pu!=pv){             if(size[pu]>size[pv]){                 par[pv] = pu;                 size[pu] += size[pv];             }             else{                 par[pu] = pv;                 size[pv] += size[pu];             }         }     }  }

 

Time Complexity: The time complexity of the above approach is O(N). First, we are making the connected components, and then we are iterating the entire array of length ‘N’ and calling the findPar() function, which works in almost constant time.

 

Space Complexity: The space complexity of the above approach is O(N) because we are maintaining a ‘par’ and ‘size’ array.

 

FAQs:

1. How do we get to know that the Permutation Swaps question can be solved using Graphs?

• Suppose we have two pairs in the ‘c’ array (1, 2) ; (1, 3). Suppose we are given these two pairs for swapping. We can see that we can swap the values at 2nd and 3rd place. Hence, we saw that the indices that are part of the same component could swap the values among them, and the graph is the best way to implement the Permutation Swaps question.

 

1. What is the time complexity for the approach we used for the Permutation Swaps question?

• The time complexity of the approach we used for the Permutation Swaps question is O(N). First, we are making the connected components, and then we are iterating the entire array of length ‘N’ and calling the findPar() function, which works in almost constant time.

 

Key Takeaways: 

In this blog, we have covered the following things:

1. We first discussed how we could solve the Permutation Swaps question using graphs.
2. Then we saw how we could implement the Permutation Swaps question using D.S.U(Disjoint Set Union).

 

If you want to learn more about Graphs and want to practice some questions which require you to take your basic knowledge on Graphs a notch higher, then you can visit our Guided Path for Graphs. 

 

Until then, All the best for your future endeavors, and Keep Coding.