Formatted question description: https://leetcode.ca/all/1713.html

# 1713. Minimum Operations to Make a Subsequence

## Level

Hard

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

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

## Solution

The idea is quite straightforward. Find the length of the longest common subsequence of `target`

and `arr`

, and calculate the difference between the length of `target`

and the length of the longest common subsequence. However, an approach of O(n^2) will cause time limit exceeded.

Use a map to store the elements and the corresponding indices in `target`

. Then loop over `arr`

and use a list to store indices. If an element in `arr`

is in `target`

(which means the element is a key in the map), then add the element’s index in `target`

to the list. This problem is converted to finding the length of the longest increasing subsequence of `list`

. Use binary search to find the length of the longest increasing subsequence, which is the length of the longest common subsequence of `target`

and `arr`

. Then the minimum operations can be calculated.

```
class Solution {
public int minOperations(int[] target, int[] arr) {
int length1 = target.length, length2 = arr.length;
Map<Integer, Integer> targetMap = new HashMap<Integer, Integer>();
for (int i = 0; i < length1; i++)
targetMap.put(target[i], i);
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < length2; i++) {
int num = arr[i];
if (targetMap.containsKey(num))
list.add(targetMap.get(num));
}
int longestIncreasing = lengthOfLIS(list);
return target.length - longestIncreasing;
}
public int lengthOfLIS(List<Integer> list) {
int length = 1, size = list.size();
if (size == 0)
return 0;
int[] d = new int[size + 1];
d[length] = list.get(0);
for (int i = 1; i < size; ++i) {
if (list.get(i) > d[length]) {
d[++length] = list.get(i);
} else {
int left = 1, right = length, pos = 0;
while (left <= right) {
int mid = (left + right) >> 1;
if (d[mid] < list.get(i)) {
pos = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
d[pos + 1] = list.get(i);
}
}
return length;
}
}
```