# Minimum Operations to Make a Subsequence
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-operations-to-make-a-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-a-subsequence
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
---
## Problem
You are given an array `target` that consists of **distinct** integers and another integer array `arr` that **can** have duplicates.

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

Return _the **minimum** number of operations needed to make_ `target` _a **subsequence** of_ `arr`_._

A **subsequence** of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order. For example, `[2,7,4]` is a subsequence of `[4,2,3,7,2,1,4]` (the underlined elements), while `[2,4,2]` is not.

**Example 1:**

**Input:** target = [5,1,3], `arr` = [9,4,2,3,4]
**Output:** 2
**Explanation:** You can add 5 and 1 in such a way that makes `arr` = [5,9,4,1,2,3,4], then target will be a subsequence of `arr`.

**Example 2:**

**Input:** target = [6,4,8,1,3,2], `arr` = [4,7,6,2,3,8,6,1]
**Output:** 3

**Constraints:**

* `1 <= target.length, arr.length <= 105`
* `1 <= target[i], arr[i] <= 109`
* `target` contains no duplicates.

# Approaches
## LCS via LIS with O(N^2) Dynamic Programming
This approach correctly identifies that the problem can be transformed from finding a Longest Common Subsequence (LCS) to finding a Longest Increasing Subsequence (LIS). By mapping the values in the `target` array to their indices, we can create a new sequence from `arr` consisting only of these indices. An increasing subsequence in this new sequence corresponds to a valid common subsequence in the original arrays. This approach then uses a standard, but less efficient, dynamic programming algorithm with O(N^2) time complexity to find the length of the LIS.
**Time:** O(m + n + k^2), where `m` is `target.length`, `n` is `arr.length`, and `k` is the size of the generated `indices` list (`k <= n`). This simplifies to O(m + n^2) in the worst case. · **Space:** O(m + k), where `m` is the length of `target` and `k` is the number of elements in `arr` also present in `target`. In the worst case, this is O(m + n).
**Pros:** Correctly reduces the problem from LCS to LIS, which is a key insight.; The DP logic for LIS is relatively simple to understand and implement.
**Cons:** The O(k^2) complexity for the LIS calculation is too slow for the given constraints (k can be up to 10^5), leading to a 'Time Limit Exceeded' error on large test cases.
### Explanation
The minimum number of operations is `target.length - length(LCS(target, arr))`. Since `target` has distinct elements, we can simplify the LCS problem. We first create a map from each element in `target` to its index. Then, we iterate through `arr` and form a new list, `indices`, containing the indices of elements that are present in both `arr` and `target`. The length of the LCS is equal to the length of the Longest Increasing Subsequence (LIS) of this `indices` list. This approach calculates the LIS length using a straightforward but slow O(N^2) dynamic programming solution.

```java
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;

class Solution {
    public int minOperations(int[] target, int[] arr) {
        HashMap<Integer, Integer> targetMap = new HashMap<>();
        for (int i = 0; i < target.length; i++) {
            targetMap.put(target[i], i);
        }

        List<Integer> indices = new ArrayList<>();
        for (int num : arr) {
            if (targetMap.containsKey(num)) {
                indices.add(targetMap.get(num));
            }
        }

        if (indices.isEmpty()) {
            return target.length;
        }

        int[] dp = new int[indices.size()];
        Arrays.fill(dp, 1);
        int maxLis = 1;

        for (int i = 1; i < indices.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (indices.get(i) > indices.get(j)) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
            maxLis = Math.max(maxLis, dp[i]);
        }

        return target.length - maxLis;
    }
}
```
### Algorithm
*   The core idea is that minimizing insertions is equivalent to maximizing the number of elements from `target` that are already present in `arr` in the correct relative order. This is the definition of the Longest Common Subsequence (LCS).
*   However, a standard O(m*n) LCS algorithm is too slow. We can optimize by using the fact that `target` contains distinct elements.
*   This allows us to reframe the problem as finding the Longest Increasing Subsequence (LIS).
1.  **Map `target` values to indices:** Create a `HashMap` to store each number in `target` and its corresponding index. This lets us quickly check if a number from `arr` is in `target` and what its relative order should be.
2.  **Create an index sequence:** Iterate through `arr`. For each number that also exists in `target`, find its index from the map and add it to a new list, let's call it `indices`.
3.  **Find LIS of `indices`:** The problem is now reduced to finding the length of the LIS of this `indices` list. An increasing subsequence of these indices corresponds to elements from `target` appearing in the correct relative order within `arr`.
4.  **Calculate LIS with O(N^2) DP:**
    *   Create a `dp` array of the same size as `indices`, where `dp[i]` stores the length of the LIS ending at `indices[i]`.
    *   Initialize all `dp` values to 1.
    *   Iterate through the `indices` list from the second element (`i=1`). For each element, iterate through all preceding elements (`j < i`).
    *   If `indices[i] > indices[j]`, it means we can extend the subsequence ending at `j`. Update `dp[i]` with `max(dp[i], 1 + dp[j])`.
    *   The maximum value in the `dp` array is the length of the LIS.
5.  **Calculate result:** The number of required insertions is `target.length - length(LIS)`.

## LCS via LIS with Binary Search (Patience Sorting)
This optimal approach uses the same problem reduction as the previous one, transforming the LCS problem into an LIS problem. However, it employs a highly efficient O(N log N) algorithm to find the length of the Longest Increasing Subsequence. This algorithm, sometimes known as Patience Sorting, uses a helper list and binary search. For each element of the generated index sequence, it either extends the LIS or updates the list to allow for a future LIS with a smaller tail element. This avoids the O(N^2) complexity and is fast enough to pass all test cases within the given constraints.
**Time:** O(m + n log k), where `m` is `target.length`, `n` is `arr.length`, and `k` is the length of the LIS (`k <= m`). Since `k <= n`, the complexity is bounded by O(m + n log n). · **Space:** O(m + k), where `m` is `target.length` and `k` is the length of the LIS. In the worst case, this is O(m + min(m, n)).
**Pros:** Highly efficient with O(m + n log n) time complexity, which is optimal for this problem.; Effectively handles the large constraints of the problem.
**Cons:** The logic for the O(N log N) LIS algorithm is more complex and less intuitive than the O(N^2) DP approach.
### Explanation
This solution refines the previous approach by using a much faster algorithm for finding the LIS length. The initial steps of mapping `target` elements to indices are the same. The core improvement is in the LIS calculation. We maintain a list, `sub`, that represents the tails of potential increasing subsequences. For each index from `arr`, we use binary search to find its place in `sub`. If the index is larger than any tail in `sub`, it extends the LIS. Otherwise, it replaces the smallest tail that is greater than or equal to it, creating a new potential LIS of the same length with a more favorable (smaller) tail.

```java
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int minOperations(int[] target, int[] arr) {
        HashMap<Integer, Integer> targetMap = new HashMap<>();
        for (int i = 0; i < target.length; i++) {
            targetMap.put(target[i], i);
        }

        List<Integer> sub = new ArrayList<>();
        for (int num : arr) {
            if (!targetMap.containsKey(num)) {
                continue;
            }
            int index = targetMap.get(num);
            
            // Binary search to find the insertion point for 'index' in 'sub'
            int left = 0, right = sub.size();
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (sub.get(mid) < index) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            if (left == sub.size()) {
                // If index is greater than all elements in sub, extend the subsequence
                sub.add(index);
            } else {
                // Replace the element at 'left' to potentially form a better subsequence
                sub.set(left, index);
            }
        }

        return target.length - sub.size();
    }
}
```
### Algorithm
1.  **Map `target` values to indices:** Just like the previous approach, create a `HashMap` to store each number in `target` and its corresponding index. This takes O(m) time.
2.  **Process `arr` to find LIS directly:** Instead of creating an intermediate `indices` list, we can compute the LIS on the fly. We use an efficient O(N log N) algorithm.
3.  **Find LIS with Binary Search (Patience Sorting):**
    *   Initialize an empty list, `sub`, which will store the smallest tail of all increasing subsequences of a certain length. The length of `sub` will be the length of the LIS.
    *   Iterate through each number `num` in `arr`.
    *   If `num` is not in the `targetMap`, ignore it.
    *   Get the index `idx = targetMap.get(num)`.
    *   Perform a binary search on the `sub` list to find the first element that is greater than or equal to `idx`. This is the position where `idx` can replace an existing element to form an increasing subsequence of the same length but with a smaller tail, or where it can be inserted to extend the LIS.
    *   If the binary search finds that `idx` is larger than all elements in `sub`, it means we can extend the longest subsequence found so far. Append `idx` to `sub`.
    *   Otherwise, replace the element at the found position with `idx`.
4.  **Calculate result:** After iterating through `arr`, the size of the `sub` list is the length of the LCS. The final answer is `target.length - sub.size()`.

# Solutions
### Java

```java
class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; this . c = new int [ n + 1 ]; } public static int lowbit ( int x ) { return x & - x ; } public void update ( int x , int val ) { while ( x <= n ) { c [ x ] = Math . max ( c [ x ], val ); x += lowbit ( x ); } } public int query ( int x ) { int s = 0 ; while ( x > 0 ) { s = Math . max ( s , c [ x ]); x -= lowbit ( x ); } return s ; } } class Solution { public int minOperations ( int [] target , int [] arr ) { Map < Integer , Integer > d = new HashMap <>(); for ( int i = 0 ; i < target . length ; ++ i ) { d . put ( target [ i ], i ); } List < Integer > nums = new ArrayList <>(); for ( int i = 0 ; i < arr . length ; ++ i ) { if ( d . containsKey ( arr [ i ])) { nums . add ( d . get ( arr [ i ])); } } return target . length - lengthOfLIS ( nums ); } private int lengthOfLIS ( List < Integer > nums ) { TreeSet < Integer > ts = new TreeSet (); for ( int v : nums ) { ts . add ( v ); } int idx = 1 ; Map < Integer , Integer > d = new HashMap <>(); for ( int v : ts ) { d . put ( v , idx ++); } int ans = 0 ; BinaryIndexedTree tree = new BinaryIndexedTree ( nums . size ()); for ( int v : nums ) { int x = d . get ( v ); int t = tree . query ( x - 1 ) + 1 ; ans = Math . max ( ans , t ); tree . update ( x , t ); } return ans ; } }
```

### CPP

```cpp
class BinaryIndexedTree { public: int n ; vector < int > c ; BinaryIndexedTree ( int _n ) : n ( _n ) , c ( _n + 1 ) {} void update ( int x , int val ) { while ( x <= n ) { c [ x ] = max ( c [ x ], val ); x += lowbit ( x ); } } int query ( int x ) { int s = 0 ; while ( x > 0 ) { s = max ( s , c [ x ]); x -= lowbit ( x ); } return s ; } int lowbit ( int x ) { return x & - x ; } }; class Solution { public: int minOperations ( vector < int >& target , vector < int >& arr ) { unordered_map < int , int > d ; for ( int i = 0 ; i < target . size (); ++ i ) d [ target [ i ]] = i ; vector < int > nums ; for ( int i = 0 ; i < arr . size (); ++ i ) { if ( d . count ( arr [ i ])) { nums . push_back ( d [ arr [ i ]]); } } return target . size () - lengthOfLIS ( nums ); } int lengthOfLIS ( vector < int >& nums ) { set < int > s ( nums . begin (), nums . end ()); int idx = 1 ; unordered_map < int , int > d ; for ( int v : s ) d [ v ] = idx ++ ; BinaryIndexedTree * tree = new BinaryIndexedTree ( d . size ()); int ans = 0 ; for ( int v : nums ) { int x = d [ v ]; int t = tree -> query ( x - 1 ) + 1 ; ans = max ( ans , t ); tree -> update ( x , t ); } return ans ; } };
```

### Python

```python
class BinaryIndexedTree : def __init__ ( self , n ): self . n = n self . c = [ 0 ] * ( n + 1 ) @ staticmethod def lowbit ( x ): return x & - x def update ( self , x , val ): while x <= self . n : self . c [ x ] = max ( self . c [ x ], val ) x += BinaryIndexedTree . lowbit ( x ) def query ( self , x ): s = 0 while x : s = max ( s , self . c [ x ]) x -= BinaryIndexedTree . lowbit ( x ) return s class Solution : def minOperations ( self , target : List [ int ], arr : List [ int ]) -> int : d = { v : i for i , v in enumerate ( target )} nums = [ d [ v ] for v in arr if v in d ] return len ( target ) - self . lengthOfLIS ( nums ) def lengthOfLIS ( self , nums ): s = sorted ( set ( nums )) m = { v : i for i , v in enumerate ( s , 1 )} tree = BinaryIndexedTree ( len ( m )) ans = 0 for v in nums : x = m [ v ] t = tree . query ( x - 1 ) + 1 ans = max ( ans , t ) tree . update ( x , t ) return ans
```