aboutsummaryrefslogtreecommitdiff
path: root/min_operations_subseq.py
blob: 241daf199881dd99ed584206bb81a66313587adb (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 1713. Minimum Operations to Make a Subsequence
from bisect import bisect_left

"""
given an array 'target' that consists of distinct integers and another
integer array 'arr' that can have duplicates. in one operatioin, you can
insert any integer at any position in 'arr'. note that you can inser 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 anarray is a new array generated from the original array by deleting some
elements (possibly none) without changing the remaining elements.
"""


class Solution(object):
    def minOperations(self, target, arr):
        """
        :type target: List[int]
        :type arr: List[int]
        :rtype: int
        """
        dic = {num: i for i, num in enumerate(target)}
        a = []
        for num in arr:
            if num in dic:
                a.append(dic[num])
        return len(target) - self.len_list(self, nums)

    def len_list(self, nums):
        if not nums:
            return 0
        piles = []
        for n in nums:
            idx = bisect_left(piles, n)
            if idx == len(piles):
                piles.append(num)
            else:
                piles[idx] = n
        return len(piles)


if __name__ == "__main__":
    obj = Solution()
    print(obj.minOperations(target=[5, 1, 3], arr=[9, 4, 2, 3, 4]))
    print(obj.minOperations(target=[6, 4, 8, 1, 3, 2], arr=[4, 7, 6, 2, 3, 8, 6, 1]))