Decrease swap between identical listed components to make given Arrays strictly rising

Given two arrays arr1[] and arr2[] of dimension N every, the duty is to search out the minimal variety of interchange of the identical listed components required to make each arrays strictly rising.

Be aware: Return -1 if it isn’t potential to make them strictly rising.

Examples:

Enter: arr1 = {1, 3, 5, 4}, arr2 = {1, 2, 3, 7}
Output: 1
Rationalization:  
Swap arr1[3] and arr2[3]. 
Then the sequences are:
arr1 = [1, 3, 5, 7] and arr2 = [1, 2, 3, 4] that are each strictly rising.
Due to this fact, minimal variety of swaps required =1.

Enter: arr1 = {0, 3, 5, 8, 9}, nums2 = {2, 1, 4, 6, 9}
Output: 1

Strategy: The issue might be solved primarily based on the next commentary:

For every index there are two selections: both swap the weather or not. If in each instances the prefixes of each arrays are usually not strictly rising then it isn’t potential to carry out the duty. In any other case, proceed with this strategy.

The above commentary might be applied utilizing dynamic programming idea. Create two dp[] arrays the place – 

• The i^th index of 1 will retailer the minimal steps required to make the prefixes strictly rising when the present components are swapped and 
• The opposite array will retailer the minimal steps when the present one is just not swapped.

Observe the steps talked about beneath to implement the above commentary:

• Take into account two arrays swap[] and noswap[] the place – 
  • swap[i] shops the minimal steps when arr1[i] & arr2[i] are swapped given the array is sorted from 0 to i-1.
  • noswap[i] retailer the minimal steps when no swap between arr1[i] & arr2[i] given the array is sorted from 0 to i-1.
• Iterate the array and primarily based on the relations between the array components at i^th and (i-1)^th index replace the worth of the arrays.
  • If arr1[i] and arr2[i] are each higher than the (i-1)^th components of each the arrays, then
    • If the present values are swapped, the earlier also needs to be swapped. So swap[i] = swap[i-1]+1
    • If the present components are usually not swapped the identical must be finished with the earlier components. So, noswap[i] = noswap[i-1]
  • If arr1[i] is bigger than arr2[i-1] and arr2[i] higher than arr1[i-1]:
    • If we swap i^th index components then we must always not swap (i-1)^th index components. So swap[i] = min(swap[i], noswap[i-1]).
    • As a result of identical situation noswap[i] = min(noswap[i], swap[i-1]+1).
• The required reply is the minimal among the many values on the final index of swap[] array and noswap[] array.

Under is the implementation for the above-mentioned strategy:

Time Complexity: O(N)
Auxiliary Area: O(N)