Minimize swap between same indexed elements to make given Arrays strictly increasing

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).
  • 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++

  

#include <bits/stdc++.h>

using namespace std;

  

int minSwap(int A[], int B[], int n)

{

    int swap[n], no_swap[n];

  

    swap[0] = 1;

    no_swap[0] = 0;

  

    

    for (int i = 1; i < n; ++i) {

        swap[i] = no_swap[i] = n;

  

        

        

        if (A[i] > A[i - 1] && B[i] > B[i - 1]) {

  

            

            

            swap[i] = swap[i - 1] + 1;

  

            

            

            no_swap[i] = no_swap[i - 1];

        }

  

        if (A[i] > B[i - 1] && B[i] > A[i - 1]) {

  

            

            

            swap[i] = min(swap[i],

                          no_swap[i - 1] + 1);

  

            

            

            no_swap[i] = min(no_swap[i],

                             swap[i - 1]);

        }

  

        

        

        if ((A[i] < A[i - 1] && A[i] < B[i - 1])

            || (B[i] < B[i - 1] && B[i] < A[i - 1])) {

            return -1;

        }

    }

  

    

    return min(swap[n - 1], no_swap[n - 1]);

}

  

int main()

{

    int arr1[] = { 1, 3, 5, 4 };

    int arr2[] = { 1, 2, 3, 7 };

    int N = sizeof(arr1) / sizeof(arr1[0]);

  

    

    int ans = minSwap(arr1, arr2, N);

    cout << ans << endl;

    return 0;

}

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

By Julio MarchiPosted on