<p>You are given an array <code>target</code> that consists of <strong>distinct</strong> integers and another integer array <code>arr</code> that <strong>can</strong> have duplicates.</p>

<p>In one operation, you can insert any integer at any position in <code>arr</code>. For example, if <code>arr = [1,4,1,2]</code>, you can add <code>3</code> in the middle and make it <code>[1,4,<u>3</u>,1,2]</code>. Note that you can insert the integer at the very beginning or end of the array.</p>

<p>Return <em>the <strong>minimum</strong> number of operations needed to make </em><code>target</code><em> a <strong>subsequence</strong> of </em><code>arr</code><em>.</em></p>

<p>A <strong>subsequence</strong> of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements&#39; relative order. For example, <code>[2,7,4]</code> is a subsequence of <code>[4,<u>2</u>,3,<u>7</u>,2,1,<u>4</u>]</code> (the underlined elements), while <code>[2,4,2]</code> is not.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> target = [5,1,3], <code>arr</code> = [9,4,2,3,4]
<strong>Output:</strong> 2
<strong>Explanation:</strong> You can add 5 and 1 in such a way that makes <code>arr</code> = [<u>5</u>,9,4,<u>1</u>,2,3,4], then target will be a subsequence of <code>arr</code>.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> target = [6,4,8,1,3,2], <code>arr</code> = [4,7,6,2,3,8,6,1]
<strong>Output:</strong> 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= target.length, arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= target[i], arr[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>target</code> contains no duplicates.</li>
</ul>

class Solution {
public:
int lcs2(vector<int>& X, vector<int>& Y, int m, int n,
		vector<vector<int> >& dp)
{
	if (m == 0 || n == 0)
		return 0;
	if (X[m - 1] == Y[n - 1])
		return dp[m][n] = 1 + lcs2(X, Y, m - 1, n - 1, dp);

	if (dp[m][n] != -1) {
		return dp[m][n];
	}
	return dp[m][n] = max(lcs2(X, Y, m, n - 1, dp),
						lcs2(X, Y, m - 1, n, dp));
}


int lcs(const vector<int>& X, const vector<int>& Y, int m, int n) {
    // Initialize a 2D vector with size (m+1) x (n+1)
    vector<vector<int>> L(m + 1, vector<int>(n + 1, 0));

    // Build the L matrix in a bottom-up fashion
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (X[i - 1] == Y[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }

    // Return the length of LCS
    return L[m][n];

}    
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        if(n==0)return 0;
        vector<int> lis;  // Dynamic array to store the current ends of increasing subsequences
        vector<int>prev(n,-1);
        vector<int>prevInd;
        int lastInd=-1;
        for (int i=0;i<n;i++) {
            int num=nums[i];
            // Find the position where `num` can be inserted or should replace an existing element
            auto it = lower_bound(lis.begin(), lis.end(), num);
            
            if (it == lis.end()) {
                // If `num` is greater than all elements, append it
                lastInd=i;
                if(!lis.empty()){
                prev[i]=prevInd[lis.size()-1];}
                lis.push_back(num);
                prevInd.push_back(i);
            } else {
                // Otherwise, replace the element at the found position
                if(it-lis.begin()>0){prev[i]=prevInd[it-lis.begin()-1];}
                *it = num;
                prevInd[it-lis.begin()]=i;
            }
        }
        lastInd=prevInd[prevInd.size()-1];
        while(lastInd!=-1){
            cout<<nums[lastInd]<<' ';
            lastInd=prev[lastInd];
        }
        
        // The length of `lis` is the length of the longest increasing subsequence
        return lis.size();
    }
// int minOperations(vector<int>& target, vector<int>& arr) {
//         int m = target.size();
//         int n = arr.size();
// 	    // vector<vector<int> > dp(m + 1, vector<int>(n + 1, -1));

//         // return m-lcs2(target, arr, m, n, dp);
//         // return m-lcs(target, arr, m, n);

//     }

int minOperations(vector<int>& target, vector<int>& arr) {
    // Step 1: Create a mapping of each element in target to its index.
    unordered_map<int, int> indexMap;
    for (int i = 0; i < target.size(); ++i) {
        indexMap[target[i]] = i;
    }

    // Step 2: Replace each element in arr with its corresponding index in target.
    vector<int> transformedArr;
    for (int num : arr) {
        if (indexMap.count(num)) {
            transformedArr.push_back(indexMap[num]);
        }
    }
    return target.size()-lengthOfLIS(transformedArr);
    // Return 0 as a placeholder, since only the transformation was asked for.
    return 0;
}
};
119500