801. Minimum Swaps To Make Sequences Increasing

801. Minimum Swaps To Make Sequences Increasing

 Solution:

class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B)
{
  int n = A.size();
  vector<int> X(n,0);
  vector<int> Y(n,1);

  for(int i = 1; i < n; i++){
    X[i] = Y[i] = n;


    if(A[i-1] < A[i] && B[i - 1] < B[i]){
      X[i] = X[i-1];
      Y[i] = Y[i - 1] + 1;
    }

    if(A[i - 1] < B[i] && B[i-1] < A[i]){
      X[i] = min(X[i], Y[i-1]);
      Y[i] = min(Y[i], X[i-1] + 1);
    }

  }
  return min(Y[n-1], X[n-1]);
}
};

Share: