#1713

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Operations to Make a Subsequence

Compute the minimum insertions required to transform arr so that target becomes its subsequence using array scanning and hash lookup.

array hash table binary search greedy

Problem Statement

You are given two integer arrays: target, containing distinct integers, and arr, which may contain duplicates. Your goal is to modify arr so that target appears as a subsequence by inserting elements at any positions, including the start or end of arr.

In one operation, you can insert any integer at any index of arr. Return the minimum number of insertions needed to make target a subsequence of arr. For example, if target = [5,1,3] and arr = [9,4,2,3,4], you need two insertions to achieve the subsequence.

Examples

Example 1

Input: target = [5,1,3], arr = [9,4,2,3,4]

Output: 2

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

Example details omitted.

Constraints

1 <= target.length, arr.length <= 105
1 <= target[i], arr[i] <= 109
target contains no duplicates.

Solution Approach

Map target values to indices

Create a hash map that assigns each element of target to its index. This allows quick conversion of arr elements into positions relative to target, turning the problem into a sequence of indices.

Compute Longest Increasing Subsequence (LIS)

Transform arr into a list of target indices where elements exist. The LIS of this list represents the largest subsequence already in order. Use binary search to maintain the LIS efficiently for O(n log n) time.

Calculate minimum insertions

Subtract the length of the LIS from target.length. This difference equals the minimal number of insertions required to make target a subsequence of arr. Insertions correspond to elements in target not present in LIS.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) using binary search for LIS computation, where n is arr.length. Space complexity is O(m) for the hash map, where m is target.length. These bounds reflect the pattern of mapping target to arr indices and maintaining increasing sequences efficiently.

What Interviewers Usually Probe

Expecting hash map usage for index lookup rather than naive scanning.
Look for LIS or patience sorting approach on mapped indices.
Clarify edge cases where arr has duplicates or missing elements from target.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle elements in arr that are not in target, which should be skipped.
Using naive O(n*m) LCS instead of LIS-based optimization on indices.
Miscounting insertions when LIS covers only a partial subsequence of target.

Follow-up variants

Compute minimum deletions in arr to match target subsequence.
Find minimal operations when both insertion and deletion are allowed.
Handle repeated elements in target instead of assuming distinct values.

FAQ

What is the main pattern used in Minimum Operations to Make a Subsequence?

The problem follows an array scanning plus hash lookup pattern, mapping target elements to indices and computing a longest increasing subsequence.

How do I handle duplicates in arr when computing the solution?

Ignore arr elements not present in target and map each valid element to its target index; duplicates do not affect LIS computation.

Can this problem be solved without binary search?

Yes, but naive approaches lead to O(n*m) time. Binary search on LIS indices reduces it to O(n log n), suitable for large arrays.

Why do we subtract LIS length from target length?

LIS length represents the subsequence already in order; the difference shows the number of insertions needed to complete target as a subsequence.

What is an example of minimal operations for target = [5,1,3] and arr = [9,4,2,3,4]?

You need two insertions, adding 5 and 1 in positions that allow arr to include [5,1,3] as a subsequence.

terminal

Solution

Solution 1: Longest Increasing Subsequence + Binary Indexed Tree

According to the problem statement, the longer the common subsequence between `target` and `arr`, the fewer elements need to be added. Therefore, the minimum number of elements to be added equals the length of `target` minus the length of the longest common subsequence between `target` and `arr`.

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

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

Continue Practicing

#1488 avoid flood in the city #2554 maximum number of integers to choose from a range i #1733 minimum number of people to teach