How hard is LeetCode 1713. Minimum Operations to Make a Subsequence?

LeetCode 1713. Minimum Operations to Make a Subsequence is rated Hard on LeetCode.

What is the time complexity of LeetCode 1713. Minimum Operations to Make a Subsequence?

The Python solution on this page runs in O(n \times \log m).

What is the space complexity of LeetCode 1713. Minimum Operations to Make a Subsequence?

The Python solution on this page uses O(m) auxiliary space.

What topics does LeetCode 1713. Minimum Operations to Make a Subsequence cover?

LeetCode 1713. Minimum Operations to Make a Subsequence is tagged Greedy, Array, Hash Table and Binary Search on LeetCode.

Minimum Operations to Make a Subsequence — LeetCode 1713 Python Solution

HardGreedyArrayHash TableBinary Search

Problem: #1713
Pattern: Binary Search
Reading time: 6 min
Source: leetcode.com

The problem

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.

Example

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.

Python solution

Python

class BinaryIndexedTree:
    __slots__ = "n", "c"

    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, v: int):
        while x <= self.n:
            self.c[x] = max(self.c[x], v)
            x += x & -x

    def query(self, x: int) -> int:
        res = 0
        while x:
            res = max(res, self.c[x])
            x -= x & -x
        return res


class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        d = {x: i for i, x in enumerate(target, 1)}
        nums = [d[x] for x in arr if x in d]
        m = len(target)
        tree = BinaryIndexedTree(m)
        ans = 0
        for x in nums:
            v = tree.query(x - 1) + 1
            ans = max(ans, v)
            tree.update(x, v)
        return len(target) - ans

Complexity

Measure	Complexity
Time	O(n \times \log m)
Space	O(m) auxiliary

Pattern: Binary Search

Halve the search space each step — over an array, or over the answer itself. LeetCode 1713. Minimum Operations to Make a Subsequence is filed here because LeetCode tags it Binary Search, which is the vocabulary this hub collects.

The binary search guide has the Python template for the pattern and the 254 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1713. Minimum Operations to Make a Subsequence?: LeetCode 1713. Minimum Operations to Make a Subsequence is rated Hard on LeetCode.
What is the time complexity of LeetCode 1713. Minimum Operations to Make a Subsequence?: The Python solution on this page runs in O(n \times \log m).
What is the space complexity of LeetCode 1713. Minimum Operations to Make a Subsequence?: The Python solution on this page uses O(m) auxiliary space.
What topics does LeetCode 1713. Minimum Operations to Make a Subsequence cover?: LeetCode 1713. Minimum Operations to Make a Subsequence is tagged Greedy, Array, Hash Table and Binary Search on LeetCode.