Minimum Operations to Make a Subsequence LeetCode solution in Python

1
# Runtime: 962 ms (Top 100.00%) | Memory: 36.9 MB (Top 93.24%)
2
from bisect import bisect_left
3

4

5
class Solution:
6
    def minOperations(self, target: List[int], arr: List[int]) -> int:
7
        dt = {num: i for i, num in enumerate(target)}
8
        stack = []
9
        for num in arr:
10
            if num not in dt:
11
                continue
12
            i = bisect_left(stack, dt[num])
13
            if i == len(stack):
14
                stack.append(dt[num])
15
            else:
16
                stack[i] = dt[num]
17
        return len(target) - len(stack)