Given two arrays arr1[] and arr2[] of size N each, the task is to find the minimum number of interchange of the same indexed elements required to make both arrays strictly increasing.
Note: Return -1 if it is not possible to make them strictly increasing.
Examples:
Input: arr1 = {1, 3, 5, 4}, arr2 = {1, 2, 3, 7}
Output: 1
Explanation:
Swap arr1[3] and arr2[3].
Then the sequences are:
arr1 = [1, 3, 5, 7] and arr2 = [1, 2, 3, 4] which are both strictly increasing.
Therefore, minimum number of swaps required =1.Input: arr1 = {0, 3, 5, 8, 9}, nums2 = {2, 1, 4, 6, 9}
Output: 1
Approach: The problem can be solved based on the following observation:
For each index there are two choices: either swap the elements or not. If in both cases the prefixes of both arrays are not strictly increasing then it is not possible to perform the task. Otherwise, continue with this approach.
The above observation can be implemented using dynamic programming concept. Create two dp[] arrays where –
- The ith index of one will store the minimum steps required to make the prefixes strictly increasing when the current elements are swapped and
- The other array will store the minimum steps when the current one is not swapped.
Follow the steps mentioned below to implement the above observation:
- Consider two arrays swap[] and noswap[] where –
- swap[i] stores the minimum steps when arr1[i] & arr2[i] are swapped given the array is sorted from 0 to i-1.
- noswap[i] store the minimum steps when no swap between arr1[i] & arr2[i] given the array is sorted from 0 to i-1.
- Iterate the array and based on the relations between the array elements at ith and (i-1)th index update the value of the arrays.
- If arr1[i] and arr2[i] are both greater than the (i-1)th elements of both the arrays, then
- If the current values are swapped, the previous should also be swapped. So swap[i] = swap[i-1]+1
- If the current elements are not swapped the same should be done with the previous elements. So, noswap[i] = noswap[i-1]
- If arr1[i] is greater than arr2[i-1] and arr2[i] greater than arr1[i-1]:
- If we swap ith index elements then we should not swap (i-1)th index elements. So swap[i] = min(swap[i], noswap[i-1]).
- Due to the same condition noswap[i] = min(noswap[i], swap[i-1]+1).
- If arr1[i] and arr2[i] are both greater than the (i-1)th elements of both the arrays, then
- The required answer is the minimum among the values at the last index of swap[] array and noswap[] array.
Below is the implementation for the above-mentioned approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate// the minimum swaps required or// it is not possibleint minSwap(int A[], int B[], int n){ int swap[n], no_swap[n]; swap[0] = 1; no_swap[0] = 0; // Loop to implement the dynamic programming for (int i = 1; i < n; ++i) { swap[i] = no_swap[i] = n; // assigning n to both of these // so that they can be compared easily if (A[i] > A[i - 1] && B[i] > B[i - 1]) { // If we swap position i, // we need to swap position i - 1. swap[i] = swap[i - 1] + 1; // If we don't swap position i, // we should not swap position i - 1. no_swap[i] = no_swap[i - 1]; } if (A[i] > B[i - 1] && B[i] > A[i - 1]) { // If we swap position i, // we should not swap position i - 1. swap[i] = min(swap[i], no_swap[i - 1] + 1); // If we don't swap position i, // we should swap position i - 1. no_swap[i] = min(no_swap[i], swap[i - 1]); } // If any one the array is not possible // to be made strictly increasing if ((A[i] < A[i - 1] && A[i] < B[i - 1]) || (B[i] < B[i - 1] && B[i] < A[i - 1])) { return -1; } } // Return the answer return min(swap[n - 1], no_swap[n - 1]);}// Driver Codeint main(){ int arr1[] = { 1, 3, 5, 4 }; int arr2[] = { 1, 2, 3, 7 }; int N = sizeof(arr1) / sizeof(arr1[0]); // Function call int ans = minSwap(arr1, arr2, N); cout << ans << endl; return 0;} |
Java
// Java program for above approachimport java.util.ArrayList;class GFG {// Function to calculate// the minimum swaps required or// it is not possiblestatic int minSwap(int A[], int B[], int n){ int swap[] = new int[n], no_swap[] = new int[n]; swap[0] = 1; no_swap[0] = 0; // Loop to implement the dynamic programming for (int i = 1; i < n; ++i) { swap[i] = no_swap[i] = n; // assigning n to both of these // so that they can be compared easily if (A[i] > A[i - 1] && B[i] > B[i - 1]) { // If we swap position i, // we need to swap position i - 1. swap[i] = swap[i - 1] + 1; // If we don't swap position i, // we should not swap position i - 1. no_swap[i] = no_swap[i - 1]; } if (A[i] > B[i - 1] && B[i] > A[i - 1]) { // If we swap position i, // we should not swap position i - 1. swap[i] = Math.min(swap[i], no_swap[i - 1] + 1); // If we don't swap position i, // we should swap position i - 1. no_swap[i] = Math.min(no_swap[i], swap[i - 1]); } // If any one the array is not possible // to be made strictly increasing if ((A[i] < A[i - 1] && A[i] < B[i - 1]) || (B[i] < B[i - 1] && B[i] < A[i - 1])) { return -1; } } // Return the answer return Math.min(swap[n - 1], no_swap[n - 1]);}// Driver codepublic static void main(String args[]) { int arr1[] = { 1, 3, 5, 4 }; int arr2[] = { 1, 2, 3, 7 }; int N = arr1.length; // Function call int ans = minSwap(arr1, arr2, N); System.out.print(ans);}}// This code is contributed by code_hunt. |
Python3
# Python code to implement the approach# Function to calculate# the minimum swaps required or# it is not possibledef minSwap(A, B, n): swap = [0] * n no_swap = [0] * n swap[0] = 1 no_swap[0] = 0 # Loop to implement the dynamic programming for i in range(1, n): swap[i] = no_swap[i] = n # assigning n to both of these # so that they can be compared easily if A[i] > A[i - 1] and B[i] > B[i - 1]: # If we swap position i, # we need to swap position i - 1. swap[i] = swap[i - 1] + 1 # If we don't swap position i, # we should not swap position i - 1. no_swap[i] = no_swap[i - 1] if A[i] > B[i - 1] and B[i] > A[i - 1]: # If we swap position i, # we should not swap position i - 1. swap[i] = min(swap[i], no_swap[i - 1] + 1) # If we don't swap position i, # we should swap position i - 1. no_swap[i] = min(no_swap[i], swap[i - 1]) # If any one the array is not possible # to be made strictly increasing if (A[i] < A[i - 1] and A[i] < B[i - 1]) or (B[i] < B[i - 1] and B[i] < A[i - 1]): return -1 # Return the answer return min(swap[n-1], no_swap[n-1])# Driver Codeif __name__ == '__main__': arr1 = [1, 3, 5, 4] arr2 = [1, 2, 3, 7] N = len(arr1) # Function call ans = minSwap(arr1, arr2, N) print(ans)# This code is contributed by Tapesh(tapeshdua420) |
C#
// C# program for above approachusing System;public class GFG { // Function to calculate // the minimum swaps required or // it is not possible static int minSwap(int []A, int []B, int n) { int []swap = new int[n]; int []no_swap = new int[n]; swap[0] = 1; no_swap[0] = 0; // Loop to implement the dynamic programming for (int i = 1; i < n; ++i) { swap[i] = no_swap[i] = n; // assigning n to both of these // so that they can be compared easily if (A[i] > A[i - 1] && B[i] > B[i - 1]) { // If we swap position i, // we need to swap position i - 1. swap[i] = swap[i - 1] + 1; // If we don't swap position i, // we should not swap position i - 1. no_swap[i] = no_swap[i - 1]; } if (A[i] > B[i - 1] && B[i] > A[i - 1]) { // If we swap position i, // we should not swap position i - 1. swap[i] = Math.Min(swap[i], no_swap[i - 1] + 1); // If we don't swap position i, // we should swap position i - 1. no_swap[i] = Math.Min(no_swap[i],swap[i - 1]); } // If any one the array is not possible // to be made strictly increasing if ((A[i] < A[i - 1] && A[i] < B[i - 1])|| (B[i] < B[i - 1] && B[i] < A[i - 1])) { return -1; } } // Return the answer return Math.Min(swap[n - 1], no_swap[n - 1]); } // Driver code static public void Main(string []args) { int []arr1 = {1,3,5,4}; int []arr2 = {1,2,3,7}; int N = arr1.Length; // Function call int ans = minSwap(arr1, arr2, N); Console.WriteLine(ans); }}// This code is contributed by AnkThon |
Javascript
<script>// Javascript code to implement the approach// Function to calculate// the minimum swaps required or// it is not possiblefunction minSwap(A,B,n){ let swap = []; let no_swap = []; swap[0] = 1; no_swap[0] = 0; // Loop to implement the dynamic programming for (let i = 1; i < n; ++i) { swap[i] = no_swap[i] = n; // assigning n to both of these // so that they can be compared easily if (A[i] > A[i - 1] && B[i] > B[i - 1]) { // If we swap position i, // we need to swap position i - 1. swap[i] = swap[i - 1] + 1; // If we don't swap position i, // we should not swap position i - 1. no_swap[i] = no_swap[i - 1]; } if (A[i] > B[i - 1] && B[i] > A[i - 1]) { // If we swap position i, // we should not swap position i - 1. swap[i] = Math.min(swap[i], no_swap[i - 1] + 1); // If we don't swap position i, // we should swap position i - 1. no_swap[i] = Math.min(no_swap[i], swap[i - 1]); } // If any one the array is not possible // to be made strictly increasing if ((A[i] < A[i - 1] && A[i] < B[i - 1]) || (B[i] < B[i - 1] && B[i] < A[i - 1])) { return -1; } } // Return the answer return Math.min(swap[n - 1], no_swap[n - 1]);}// Driver Codelet arr1 = [ 1, 3, 5, 4 ];let arr2 = [ 1, 2, 3, 7 ];let N = arr1.length;// Function calllet ans = minSwap(arr1, arr2, N);console.log(ans);// This code is contributed by akashish__</script> |
Output
1
Time Complexity: O(N)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
