Minimum operations to convert array A to B

Given two Arrays A[] and B[] of length N and M respectively. Find the minimum number of insertions and deletions on the array A[], required to make both the arrays identical.

Note: Array B[] is sorted and all its elements are distinct, operations can be performed at any index not necessarily at end.

• Time : O(nlogn)
• Space : O(min(n,m))

c++

class Solution { //lis solution
public:
    int minInsAndDel(int A[], int B[], int N, int M) {
        unordered_set<int> us(B, B + M);
        vector<int> lis;
        
        for(int i = 0; i < N; i++) {
            if(!us.count(A[i])) continue;
            if(lis.empty() or lis.back() < A[i]) lis.push_back(A[i]);
            else {
                auto lb = lower_bound(begin(lis),end(lis),A[i]);
                *lb = A[i];
            }
        }
        
        return N + M - 2 * lis.size();
    }
};

• Time : O(nm)
• Space : O(nm)

c++

class Solution { // lcs solution
public:
    int minInsAndDel(int A[], int B[], int N, int M) {
        vector<vector<int>> dp(N + 1, vector<int>(M + 1));

        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                if(A[i-1] == B[j-1]) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        return N + M - 2 * dp[N][M];
    }
};