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.
34+ registered 
