Dynamic Programming: Minimum Number of swaps to make array increasing

Problem Statement:

You are given 2 arrays, you are allowed to swap arr1[i] and arr2[i]. Elements from the same index.

You need to return minimum number of swaps such that they are increasing.

Example

Input: arr1 = [1,3,5,4], arr2 = [1,2,3,7]
Output: 1

swap arr1[3] and arr2[3], then the new sequence will be arr1 = [1,3,5,7], arr2 = [1,2,3,4]

Solution

This problem can be solved by using DP.

At every index of “i” we can choose to swap or not.

As we want two sorted arrays at each position, whether to swap or not depends on the previous element.

So at every index of “i”,

1. If both are still sorted at the index”i” A[i] > A[i-1] and B[i] > B[i-1]
2. If both not sorted at the index “i”, in this case we need to swap to make it sorted. i.e A[i] > B[i-1] and B[i] > A[i-1]

So we take 2 arrays of size “i”,
1. no_swap[i] will hold the minimum number without swapping A[i] B[i]
2. swap[i] will hold the minimum number with swapping A[i] B[i]

So:

Case 1: A[i] > A[i -1] && B[i] > B[i – 1],
if we choose to keep, we should keep the previous i – 1 elements. So no_swap[i] = no_swap[i – 1]
If we choose to swap, in order to maintain the sequencing order, we must swap the previous i – 1 th element. So swap[i] = swap[i – 1] + 1;

Case 2: A[i] > B[i – 1] && B[i] > A[i – 1]
If we choose to keep, no_swap[i] = Math.min(no_swap[i], swap[i – 1])
If we choose to swap, swap[i] = Math.min(swap[i], no_swap[i – 1] + 1)

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;

int get_min_swap(vector<int>& A, vector<int>& B) 
{
    const size_t n = A.size();
    vector<int> swap(n, n), no_swap(n, n);
    swap[0] = 1;
    no_swap[0] = 0;
    for (size_t i = 1; i < n; ++i) {
        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] = std::min(swap[i], no_swap[i - 1] + 1);
            
            // If we don't swap position i, we should swap position i - 1.
            no_swap[i] = std::min(no_swap[i], swap[i - 1]);
        }
    }
    
    return std::min(swap.back(), no_swap.back());
}

int main()
{
  vector<int> A = {1,3,5,4};
  vector<int> B = {1,2,3,7};

    cout << "The minimum swap required is  " << get_min_swap(A, B)<<endl;
 
    return 0;
}

Output:

The minimum swap required is 1