<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>

#include <vector>
#include <unordered_map>
#include <algorithm>

// O(n^2) for if we solve this using lcs but we can solve this using lis(using binary search) which
 // will take aroung O(nlogn) time complexity

class Solution {
public:
    int minOperations(std::vector<int>& target, std::vector<int>& arr) {
        unordered_map<int, int> mp;
        int n = target.size();
        for(int i=0; i<n; i++)mp[target[i]] = i;

        vector<int>indices;
        for(int j=0; j<arr.size(); j++){
            if(mp.find(arr[j]) != mp.end()){
                indices.push_back(mp[arr[j]]);
            }
        }

        vector<int> lis;
        int l = indices.size();
        for(int i=0; i<l; i++){
            auto it = lower_bound(lis.begin(), lis.end(), indices[i]);
            if(it == lis.end()){
                lis.push_back(indices[i]);
            }else{
                *it = indices[i];
            }
        }

        int comm_len = lis.size();

        return n - comm_len;
    }
};


// class Solution {
// public:
//     int minOperations(std::vector<int>& target, std::vector<int>& arr) {
//         // Step 1: Map elements of target to their indices
//         std::unordered_map<int, int> mp;
//         int n = target.size();
//         for (int i = 0; i < n; i++) {
//             mp[target[i]] = i;
//         }

//         // Step 2: Create a list of valid indices from arr that exist in target
//         std::vector<int> indices;
//         for (int j = 0; j < arr.size(); j++) {
//             if (mp.find(arr[j]) != mp.end()) {
//                 indices.push_back(mp[arr[j]]);
//             }
//         }

//         // Step 3: Find the length of the Longest Increasing Subsequence (LIS) in indices
//         std::vector<int> lis;
//         int l = indices.size();
//         for (int i = 0; i < l; i++) {
//             // Use the value at indices[i], not i itself
//             auto it = std::lower_bound(lis.begin(), lis.end(), indices[i]);
//             if (it == lis.end()) {
//                 lis.push_back(indices[i]);  // Append if no valid position found
//             } else {
//                 *it = indices[i];  // Replace the element to maintain LIS
//             }
//         }

//         // Step 4: Calculate the minimum number of operations
//         int lisLength = lis.size();
//         return n - lisLength;
//     }
// };

117000