Solution: Minimum Operations to Make a Subsequence
Tags: algorithms, javascript, leetcode
Published: 2021-02-04 01:24:35

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/discuss/1048691/Javascript-or-Longest-Increasing-Subsequence-Solution-w-Explanation-or-beats-100-100).*

---

####[Leetcode Problem #1713 (*Hard*): Minimum Operations to Make a Subsequence](https://leetcode.com/problems/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<br>that makes arr = [5,9,4,1,2,3,4],<br>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:***
```javascript
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
}
```