Minimum swaps to reach permuted array with at most 2 positions left swaps allowed
Given a permuted array of length N of first N natural numbers, we need to tell the minimum number of swaps required in the sorted array of first N natural number to reach given permuted array where a number can be swapped with at most 2 positions left to it. If it is not possible to reach permuted array by above swap condition then print not possible.
Examples:
Input : arr = [1, 2, 5, 3, 4] Output : 2 We can reach to above-permuted array in total 2 swaps as shown below, [1, 2, 3, 4, 5] -> [1, 2, 3, 5, 4] -> [1, 2, 5, 3, 4] Input : arr[] = [5, 1, 2, 3, 4] Output : Not Possible It is not possible to reach above array just by swapping numbers 2 positions left to it.
We can solve this problem using inversions. As we can see that if a number is at a position which is more than 2 places away from its actual position then it is not possible to reach there just by swapping with elements at 2 left positions and if all element satisfy this property (there are <=2 elements smaller than it on the right) then answer will simply be a total number of inversions in the array because that many swaps will be needed to transform the array into permuted array.
We can find the number of inversions in N log N time using merge sort technique explained here so total time complexity of solution will be O(N log N) only.
Implementation:
C++
// C++ program to find minimum number of swaps // to reach a permutation with at most 2 left // swaps allowed for every element #include <bits/stdc++.h> using namespace std; /* This function merges two sorted arrays and returns inversion count in the arrays.*/int merge(int arr[], int temp[], int left, int mid, int right) { int inv_count = 0; int i = left; /* i is index for left subarray*/ int j = mid; /* j is index for right subarray*/ int k = left; /* k is index for resultant merged subarray*/ while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } /* Copy the remaining elements of left subarray (if there are any) to temp*/ while (i <= mid - 1) temp[k++] = arr[i++]; /* Copy the remaining elements of right subarray (if there are any) to temp*/ while (j <= right) temp[k++] = arr[j++]; /*Copy back the merged elements to original array*/ for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } /* An auxiliary recursive function that sorts the input array and returns the number of inversions in the array. */int _mergeSort(int arr[], int temp[], int left, int right) { int mid, inv_count = 0; if (right > left) { /* Divide the array into two parts and call _mergeSortAndCountInv() for each of the parts */ mid = (right + left)/2; /* Inversion count will be sum of inversions in left-part, right-part and number of inversions in merging */ inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid+1, right); /*Merge the two parts*/ inv_count += merge(arr, temp, left, mid+1, right); } return inv_count; } /* This function sorts the input array and returns the number of inversions in the array */int mergeSort(int arr[], int array_size) { int *temp = (int *)malloc(sizeof(int)*array_size); return _mergeSort(arr, temp, 0, array_size - 1); } // method returns minimum number of swaps to reach // permuted array 'arr' int minSwapToReachArr(int arr[], int N) { // loop over all elements to check Invalid // permutation condition for (int i = 0; i < N; i++) { /* if an element is at distance more than 2 from its actual position then it is not possible to reach permuted array just by swapping with 2 positions left elements so returning -1 */ if ((arr[i] - 1) - i > 2) return -1; } /* If permuted array is not Invalid, then number of Inversion in array will be our final answer */ int numOfInversion = mergeSort(arr, N); return numOfInversion; } // Driver code to test above methods int main() { // change below example int arr[] = {1, 2, 5, 3, 4}; int N = sizeof(arr) / sizeof(int); int res = minSwapToReachArr(arr, N); if (res == -1) cout << "Not Possible\n"; else cout << res << endl; return 0; } |
Java
// Java program to find minimum // number of swaps to reach a // permutation with at most 2 left // swaps allowed for every element import java.io.*; public class GFG { /* This function merges two sorted arrays and returns inversion count in the arrays.*/ static int merge(int arr[], int temp[], int left, int mid, int right) { int inv_count = 0; int i = left; /* i is index for left subarray*/ int j = mid; /* j is index for right subarray*/ int k = left; /* k is index for resultant merged subarray*/ while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } /* Copy the remaining elements of left subarray (if there are any) to temp*/ while (i <= mid - 1) { temp[k++] = arr[i++]; } /* Copy the remaining elements of right subarray (if there are any) to temp*/ while (j <= right) { temp[k++] = arr[j++]; } /* Copy back the merged elements to original array*/ for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } /* An auxiliary recursive function that sorts the input array and returns the number of inversions in the array. */ static int _mergeSort(int arr[], int temp[], int left, int right) { int mid, inv_count = 0; if (right > left) { /* Divide the array into two parts and call _mergeSortAndCountInv() for each of the parts */ mid = (right + left) / 2; /* Inversion count will be sum of inversions in left-part, right-part and number of inversions in merging */ inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); /* Merge the two parts*/ inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } /* This function sorts the input array and returns the number of inversions in the array */ static int mergeSort(int arr[], int array_size) { int[] temp = new int[array_size]; return _mergeSort(arr, temp, 0, array_size - 1); } // method returns minimum number of // swaps to reach permuted array 'arr' static int minSwapToReachArr(int arr[], int N) { // loop over all elements to check Invalid // permutation condition for (int i = 0; i < N; i++) { /* if an element is at distance more than 2 from its actual position then it is not possible to reach permuted array just by swapping with 2 positions left elements so returning -1 */ if ((arr[i] - 1) - i > 2) { return -1; } } /* If permuted array is not Invalid, then number of Inversion in array will be our final answer */ int numOfInversion = mergeSort(arr, N); return numOfInversion; } // Driver code public static void main(String[] args) { // change below example int arr[] = {1, 2, 5, 3, 4}; int N = arr.length; int res = minSwapToReachArr(arr, N); System.out.println(res == -1 ? "Not Possible\n" : res); } } // This code contributed by Rajput-Ji |
Python3
# Python3 program to find minimum number of # swaps to reach a permutation with at most # 2 left swaps allowed for every element # This function merges two sorted arrays and # returns inversion count in the arrays. def merge(arr, temp, left, mid, right): inv_count = 0 i = left # i is index for left subarray j = mid # j is index for right subarray k = left # k is index for resultant merged subarray while (i <= mid - 1) and (j <= right): if arr[i] <= arr[j]: temp[k] = arr[i] k, i = k + 1, i + 1 else: temp[k] = arr[j] k, j = k + 1, j + 1 inv_count = inv_count + (mid - i) # Copy the remaining elements of left # subarray (if there are any) to temp while i <= mid - 1: temp[k] = arr[i] k, i = k + 1, i + 1 # Copy the remaining elements of right # subarray (if there are any) to temp while j <= right: temp[k] = arr[j] k, j = k + 1, j + 1 # Copy back the merged elements to original array for i in range(left, right + 1): arr[i] = temp[i] return inv_count # An auxiliary recursive function that # sorts the input array and returns the # number of inversions in the array. def _mergeSort(arr, temp, left, right): inv_count = 0 if right > left: # Divide the array into two parts # and call _mergeSortAndCountInv() # for each of the parts mid = (right + left) // 2 # Inversion count will be sum of # inversions in left-part, right-part # and number of inversions in merging inv_count = _mergeSort(arr, temp, left, mid) inv_count += _mergeSort(arr, temp, mid + 1, right) # Merge the two parts inv_count += merge(arr, temp, left, mid + 1, right) return inv_count # This function sorts the input array and # returns the number of inversions in the array def mergeSort(arr, array_size): temp = [None] * array_size return _mergeSort(arr, temp, 0, array_size - 1) # method returns minimum number of # swaps to reach permuted array 'arr' def minSwapToReachArr(arr, N): # loop over all elements to check # Invalid permutation condition for i in range(0, N): # if an element is at distance more than 2 # from its actual position then it is not # possible to reach permuted array just # by swapping with 2 positions left elements # so returning -1 if (arr[i] - 1) - i > 2: return -1 # If permuted array is not Invalid, then number # of Inversion in array will be our final answer numOfInversion = mergeSort(arr, N) return numOfInversion # Driver code to test above methods if __name__ == "__main__": # change below example arr = [1, 2, 5, 3, 4] N = len(arr) res = minSwapToReachArr(arr, N) if res == -1: print("Not Possible") else: print(res) # This code is contributed by Rituraj Jain |
C#
// C# program to find minimum // number of swaps to reach a // permutation with at most 2 left // swaps allowed for every element using System; class GFG { /* This function merges two sorted arrays and returns inversion count in the arrays.*/ static int merge(int []arr, int []temp, int left, int mid, int right) { int inv_count = 0; int i = left; /* i is index for left subarray*/ int j = mid; /* j is index for right subarray*/ int k = left; /* k is index for resultant merged subarray*/ while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } /* Copy the remaining elements of left subarray (if there are any) to temp*/ while (i <= mid - 1) { temp[k++] = arr[i++]; } /* Copy the remaining elements of right subarray (if there are any) to temp*/ while (j <= right) { temp[k++] = arr[j++]; } /* Copy back the merged elements to original array*/ for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } /* An auxiliary recursive function that sorts the input array and returns the number of inversions in the array. */ static int _mergeSort(int []arr, int []temp, int left, int right) { int mid, inv_count = 0; if (right > left) { /* Divide the array into two parts and call _mergeSortAndCountInv() for each of the parts */ mid = (right + left) / 2; /* Inversion count will be sum of inversions in left-part, right-part and number of inversions in merging */ inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); /* Merge the two parts*/ inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } /* This function sorts the input array and returns the number of inversions in the array */ static int mergeSort(int []arr, int array_size) { int[] temp = new int[array_size]; return _mergeSort(arr, temp, 0, array_size - 1); } // method returns minimum number of // swaps to reach permuted array 'arr' static int minSwapToReachArr(int []arr, int N) { // loop over all elements to check Invalid // permutation condition for (int i = 0; i < N; i++) { /* if an element is at distance more than 2 from its actual position then it is not possible to reach permuted array just by swapping with 2 positions left elements so returning -1 */ if ((arr[i] - 1) - i > 2) { return -1; } } /* If permuted array is not Invalid, then number of Inversion in array will be our final answer */ int numOfInversion = mergeSort(arr, N); return numOfInversion; } // Driver code static void Main() { // change below example int []arr = {1, 2, 5, 3, 4}; int N = arr.Length; int res = minSwapToReachArr(arr, N); if(res == -1) Console.WriteLine("Not Possible"); else Console.WriteLine(res); } } // This code is contributed by mits |
Javascript
<script> // JavaScript program to find minimum // number of swaps to reach a // permutation with at most 2 left // swaps allowed for every element /* This function merges two sorted arrays and returns inversion count in the arrays.*/ function merge(arr, temp, left, mid, right) { let inv_count = 0; let i = left; /* i is index for left subarray*/ let j = mid; /* j is index for right subarray*/ let k = left; /* k is index for resultant merged subarray*/ while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } /* Copy the remaining elements of left subarray (if there are any) to temp*/ while (i <= mid - 1) { temp[k++] = arr[i++]; } /* Copy the remaining elements of right subarray (if there are any) to temp*/ while (j <= right) { temp[k++] = arr[j++]; } /* Copy back the merged elements to original array*/ for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } /* An auxiliary recursive function that sorts the input array and returns the number of inversions in the array. */ function _mergeSort(arr, temp, left, right) { let mid, inv_count = 0; if (right > left) { /* Divide the array into two parts and call _mergeSortAndCountInv() for each of the parts */ mid = (right + left) / 2; /* Inversion count will be sum of inversions in left-part, right-part and number of inversions in merging */ inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); /* Merge the two parts*/ inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } /* This function sorts the input array and returns the number of inversions in the array */ function mergeSort(arr, array_size) { let temp = Array.from({length: array_size}, (_, i) => 0); return _mergeSort(arr, temp, 0, array_size - 1); } // method returns minimum number of // swaps to reach permuted array 'arr' function minSwapToReachArr(arr, N) { // loop over all elements to check Invalid // permutation condition for (let i = 0; i < N; i++) { /* if an element is at distance more than 2 from its actual position then it is not possible to reach permuted array just by swapping with 2 positions left elements so returning -1 */ if ((arr[i] - 1) - i > 2) { return -1; } } /* If permuted array is not Invalid, then number of Inversion in array will be our final answer */ let numOfInversion = mergeSort(arr, N); return numOfInversion; } // Driver Code // change below example let arr = [1, 2, 5, 3, 4]; let N = arr.length; let res = minSwapToReachArr(arr, N); document.write(res == -1 ? "Not Possible\n" : res); </script> |
Output
2
Time Complexity: O(N*logN)
Auxiliary Space: O(logN)
This article is contributed by Utkarsh Trivedi. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
