#1713

Minimum Operations to Make a Subsequence

candidate master · 1430 · lc hard +32 · verified · 49.7% accepted · 765 likes · top 37%

Description

You are given a target array of distinct integers and an arr array that may contain duplicates. In one operation you may insert any integer anywhere in arr. Return the minimum insertions required to make target a subsequence of arr.

For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4], but [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

Code

1

2

3

class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:

class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int: