LCS and LIS: LC 1713 Minimum Operations to Make a Subsequence

Problem

1713. Minimum Operations to Make a Subsequence

LCS O(nm) TLE

class Solution {
public:
    int minOperations(vector<int>& a, vector<int>& b) {
        const int N = a.size(), M = b.size();
        vector<vector<int> > dp(N + 1, vector<int>(M + 1, 0)); 
        for(int i = 0; i <= N; i++)
            for(int j = 0; j <= M; j++) {
                if(i == 0 || j ==0) dp[i][j] = 0;
                else {
                    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 a.size() - dp[N][M];
    }
};

LIS O(n log k)

From [1]

Important observation 1: We need to find the minimum number of integers missing in arr such that target can be a subsequence of arr. Or in other words, we need to find the maximum number of integers in target such that they already form a subsequence of arr. Then we’ll know that the remaining integers will have to be inserted in arr. Or in simpler words, we need to find the length of longest common subsequence between target and arr.

Important observation 2: Normally finding the longest common subsequence is an O(n * m) problem. But here, we have additional information, which is that target has distinct integers. This allows us to create a reverse index, in which we can store the index at which an integer appears in target. Now the problem becomes finding the longest subsequence in arr such that the corresponding indices of those integers in target are strictly increasing. This is the longest increasing subsequence problem that can be solved in O(nlogn). We can ignore the integers that do not occur in the target array.

class Solution {
public:
    int minOperations(vector<int>& a, vector<int>& b) {
        unordered_map<int, int> m;
        const int n = a.size();
        for (int i = 0; i < n; ++i) m[a[i]] = i;
        vector<int> indexes;
        for (auto x: b) {
            if (m.find(x) != m.end()) indexes.push_back(m[x]);
        }
        vector<int> lis;
        for (auto x : indexes) {
            auto it = lower_bound(lis.begin(), lis.end(), x);
            if (it == lis.end()) lis.push_back(x); 
            else *it = x; 
        }
        return n - lis.size();  
    }
};

Reference