*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #1713 (*Hard*): Minimum Operations to Make a Subsequence

*Description:*

*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], while [2,4,2] is not.*

*Examples:*

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 <= 10^5
- 1 <= target[i], arr[i] <= 10^9
- target contains no duplicates

*Idea:*

Normally, we'd solve this problem by identifying the **longest common subsequence**, as that would also indicate how many elements would therefore need to be inserted to make the target array (**T**) a possible match. LCS algorithms have an **O(m * n)** time complexity, however, which is far too long in this case.

This solution is actually much more straightforward once we realize that **T** has *distinct* elements. That means that instead of an LCS approach, we can instead treat the elements of **T** as their index and solve this using a **largest increasing subsequence** approach instead, with a time complexity of **O(n * log n)**.

In a LIS solution, we first need to create an index map (**imap**) to use a reference. Since we only need the length of the larest subsequence rather than needing to be able to reconstruct it, we just need to use an array (**lis**) where **lis[i]** will keep track of the last number in the most efficient **(i-1)**-length subsequence.

In other words, **lis[4]** would be the last number in the lexicographically smallest three-number subsequence. Because each of these subsequences must be increasing by definition, and because each entry in **lis** represents the best possible version of each length of subsequence, then **lis** is by its very nature an ordered array.

This means that any new number we come across while iterating through **A** (and referencing **A[i]** through **imap**) can be used to replace the first available entry of lis that is larger. And since **lis** is ordered, we can use a simple **binary search** to **find** the appropriate replacement index of **lis**.

Once we're done iterating through **A**, the length of the longest increasing susbequence will be equal to the length of **lis**, which is likewise then the length of the longest common subsequence between **T** and **A**. All we need to do at that point is **return** its difference from **T**'s length to find out how many operations it would take to complete **T**.

*Javascript Code:*

```
var minOperations = function(T, A) {
let imap = new Map(), lis = []
for (let i = 0; i < T.length; i++) imap.set(T[i], i)
for (let i = 0; i < A.length; i++) {
let index = imap.get(A[i])
if (index !== undefined)
lis[find(index, lis)] = index
}
return T.length - lis.length
};
const find = (target, arr, left=0, right=arr.length) => {
while (left <= right) {
let mid = left + right >> 1
if (arr[mid] < target) left = mid + 1
else right = mid - 1
}
return left
}
```

## Discussion (0)