LeetCode Problem 1713

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Binary Search, Greedy

Solution

LeetCode 1713, Minimum Operations to Make a Subsequence

Problem Understanding

The problem gives us two arrays, target and arr.

The target array contains distinct integers, which is extremely important. The arr array may contain duplicates.

We are allowed to perform insert operations on arr. In a single operation, we can insert any integer at any position in the array. Our goal is to make target become a subsequence of arr using the minimum number of insertions.

A subsequence means we can delete elements from arr without changing the order of the remaining elements. Therefore, the order of elements in target must appear in arr in exactly the same relative order.

The key observation is that we do not need to make the arrays identical. We only need every element of target to appear in order somewhere inside arr.

For example:

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

Currently, only 3 appears in the correct order relative to target. We must insert 5 and 1, so the answer is 2.

The constraints are very large:

• target.length <= 10^5
• arr.length <= 10^5

This immediately tells us that quadratic solutions are too slow. Any solution close to O(n^2) will time out. We need something around O(n log n).

The problem also guarantees that target contains distinct integers. This guarantee is the foundation of the optimal solution because it allows us to map each value to a unique index.

Several edge cases are important:

• arr may contain many duplicates.
• arr may contain values not present in target.
• target may already be a subsequence of arr, giving answer 0.
• arr may contain none of the target values, meaning we must insert every target element.
• The arrays can be extremely large, so memory usage and algorithmic efficiency matter.

Approaches

Brute Force Approach

A brute force solution would attempt to compute the longest subsequence of target already present inside arr.

One way to think about this is as a Longest Common Subsequence problem between target and arr.

If we find the length of the longest common subsequence, call it L, then:

• We already have L elements in correct order.
• We must insert the remaining target.length - L elements.

So the answer becomes:

$$\text{answer} = \text{len(target)} - LCS(target, arr)$$

This approach is correct because the LCS represents the maximum number of target elements already appearing in correct relative order.

However, the classic dynamic programming solution for LCS takes:

$$O(n \times m)$$

where:

• n = len(target)
• m = len(arr)

With both lengths up to 10^5, this becomes completely infeasible.

Optimal Approach

The key insight comes from the fact that target contains distinct values.

Because every value is unique, we can map each target value to its index.

Example:

target = [6,4,8,1,3,2]

index map:
6 -> 0
4 -> 1
8 -> 2
1 -> 3
3 -> 4
2 -> 5

Now we iterate through arr.

Whenever a value exists in target, we replace it with its corresponding target index.

For the previous example:

arr = [4,7,6,2,3,8,6,1]

mapped indices:
[1,0,5,4,2,0,3]

Now the problem changes completely.

We need the longest subsequence whose indices are strictly increasing.

Why?

Because increasing indices correspond to elements appearing in the same relative order as target.

This becomes a classic Longest Increasing Subsequence problem.

Once we compute:

$$LIS = \text{length of longest increasing subsequence}$$

the answer is:

$$\text{len(target)} - LIS$$

We can compute LIS in O(n log n) using binary search.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(n × m)	Standard LCS dynamic programming
Optimal	O((n + m) log n)	O(n)	Convert to LIS using index mapping

Algorithm Walkthrough

1. Create a hash map from each value in target to its index.

This works because all values in target are distinct. The map allows constant time lookup of the desired ordering position for every value.

Example:

position = {
    6: 0,
    4: 1,
    8: 2,
    1: 3,
    3: 4,
    2: 5
}

2. Traverse through arr and build a sequence of indices.

For every value in arr:

• If it does not exist in target, ignore it.
• Otherwise, replace it with its target index.

Example:

arr = [4,7,6,2,3,8,6,1]

transformed:
[1,0,5,4,2,0,3]

3. Compute the Longest Increasing Subsequence of the transformed array.

We maintain an array called lis.

The meaning of lis[i] is:

• The smallest possible tail value of an increasing subsequence of length i + 1.

For every number:

• Use binary search to find where it belongs.
• If it is larger than all elements, append it.
• Otherwise, replace the first element greater than or equal to it.

4. The length of lis equals the length of the longest valid subsequence already present in arr.
5. Return:

len(target) - len(lis)

These are the missing elements we must insert.

Why it works

The transformed array represents the positions of target elements appearing inside arr.

Any subsequence of arr that matches the order of target must correspond to strictly increasing target indices.

Therefore:

• Finding the longest subsequence already in correct order becomes equivalent to finding the LIS.
• Every remaining target element must be inserted.

Because the LIS is maximal, the number of required insertions is minimal.

Python Solution

from typing import List
from bisect import bisect_left

class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        position = {value: index for index, value in enumerate(target)}

        lis = []

        for value in arr:
            if value not in position:
                continue

            target_index = position[value]

            insert_pos = bisect_left(lis, target_index)

            if insert_pos == len(lis):
                lis.append(target_index)
            else:
                lis[insert_pos] = target_index

        return len(target) - len(lis)

The implementation begins by building the position hash map. This gives constant time access to the index of every target value.

Next, we iterate through arr. Values not present in target cannot help form the subsequence, so they are skipped immediately.

For matching values, we convert them into their corresponding target indices.

The lis array stores the smallest possible tail values for increasing subsequences of different lengths.

We use bisect_left to find the insertion position efficiently in logarithmic time.

If the current index extends the LIS, we append it. Otherwise, we replace an existing value to maintain the smallest possible tail. Keeping tails small maximizes future extension opportunities.

Finally, the answer is computed as the number of target elements not already included in the LIS.

Go Solution

package main

import "sort"

func minOperations(target []int, arr []int) int {
	position := make(map[int]int)

	for i, value := range target {
		position[value] = i
	}

	lis := []int{}

	for _, value := range arr {
		targetIndex, exists := position[value]

		if !exists {
			continue
		}

		insertPos := sort.SearchInts(lis, targetIndex)

		if insertPos == len(lis) {
			lis = append(lis, targetIndex)
		} else {
			lis[insertPos] = targetIndex
		}
	}

	return len(target) - len(lis)
}

The Go implementation follows exactly the same logic as the Python version.

Instead of Python's bisect_left, Go uses sort.SearchInts for binary search.

Slices in Go naturally support dynamic growth through append.

There are no integer overflow concerns because indices are bounded by 10^5.

The hash map lookup uses Go's two value assignment syntax:

targetIndex, exists := position[value]

which cleanly handles missing values.

Worked Examples

Example 1

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

Step 1: Build index map

Value	Index
5	0
1	1
3	2

Step 2: Transform arr

arr value	In target?	Mapped index
9	No	Skip
4	No	Skip
2	No	Skip
3	Yes	2
4	No	Skip

Transformed array:

[2]

Step 3: Compute LIS

Current Value	lis Before	Action	lis After
2	[]	Append	[2]

LIS length is 1.

Step 4: Compute answer

len(target) - LIS
= 3 - 1
= 2

Answer:

2

Example 2

target = [6,4,8,1,3,2]
arr = [4,7,6,2,3,8,6,1]

Step 1: Build index map

Value	Index
6	0
4	1
8	2
1	3
3	4
2	5

Step 2: Transform arr

arr value	In target?	Mapped index
4	Yes	1
7	No	Skip
6	Yes	0
2	Yes	5
3	Yes	4
8	Yes	2
6	Yes	0
1	Yes	3

Transformed array:

[1,0,5,4,2,0,3]

Step 3: Compute LIS

Current Value	lis Before	Action	lis After
1	[]	Append	[1]
0	[1]	Replace index 0	[0]
5	[0]	Append	[0,5]
4	[0,5]	Replace index 1	[0,4]
2	[0,4]	Replace index 1	[0,2]
0	[0,2]	Replace index 0	[0,2]
3	[0,2]	Append	[0,2,3]

LIS length is 3.

Step 4: Compute answer

6 - 3 = 3

Answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + m) log n)	Each binary search during LIS takes O(log n)
Space	O(n)	Hash map and LIS array

Let:

• n = len(target)
• m = len(arr)

Building the hash map takes O(n).

Traversing arr takes O(m).

Each LIS update performs binary search in O(log n) time, and we do this at most m times.

Therefore, the total complexity becomes:

$$O((n + m)\log n)$$

The space usage comes primarily from:

• The index hash map
• The LIS helper array

Both require at most O(n) space.

Test Cases

from typing import List

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

        position = {value: index for index, value in enumerate(target)}

        lis = []

        for value in arr:
            if value not in position:
                continue

            idx = position[value]
            pos = bisect_left(lis, idx)

            if pos == len(lis):
                lis.append(idx)
            else:
                lis[pos] = idx

        return len(target) - len(lis)

solution = Solution()

assert solution.minOperations([5,1,3], [9,4,2,3,4]) == 2
# Basic example from problem statement

assert solution.minOperations(
    [6,4,8,1,3,2],
    [4,7,6,2,3,8,6,1]
) == 3
# Second official example

assert solution.minOperations([1,2,3], [1,2,3]) == 0
# Target already exists as subsequence

assert solution.minOperations([1,2,3], []) == 3
# Empty arr requires inserting all target values

assert solution.minOperations([1], [1]) == 0
# Single matching element

assert solution.minOperations([1], [2]) == 1
# Single non matching element

assert solution.minOperations([1,2,3], [3,2,1]) == 2
# Reverse order gives LIS length 1

assert solution.minOperations([1,2,3,4], [1,1,1,1]) == 3
# Duplicates in arr

assert solution.minOperations([1,2,3,4,5], [6,7,8]) == 5
# No target values present

assert solution.minOperations([1,2,3,4], [2,4]) == 2
# Partial subsequence already exists

assert solution.minOperations(
    [1,2,3,4,5],
    [1,3,5]
) == 2
# Non contiguous valid subsequence

print("All tests passed!")

Test Summary

Test	Why
[5,1,3], [9,4,2,3,4]	Validates official example
[6,4,8,1,3,2], [4,7,6,2,3,8,6,1]	Validates complex ordering
[1,2,3], [1,2,3]	Already a subsequence
[1,2,3], []	Empty arr
[1], [1]	Smallest matching input
[1], [2]	Smallest non matching input
[1,2,3], [3,2,1]	Reverse ordering
[1,2,3,4], [1,1,1,1]	Duplicate handling
[1,2,3,4,5], [6,7,8]	No overlap
[1,2,3,4], [2,4]	Partial subsequence
[1,2,3,4,5], [1,3,5]	Sparse subsequence

Edge Cases

One important edge case occurs when arr already contains target as a subsequence. In this scenario, the transformed index sequence is already strictly increasing, so the LIS length equals len(target). The algorithm correctly returns 0, meaning no insertions are needed.

Another important case is when arr contains none of the values from target. The transformed sequence becomes empty because every value is skipped. The LIS length is therefore 0, and the algorithm correctly determines that every target element must be inserted.

Duplicates inside arr are another potential source of bugs. Since target contains unique values, duplicates in arr map to repeated indices. The LIS algorithm naturally handles this because repeated values cannot extend a strictly increasing subsequence. Using bisect_left ensures duplicates replace existing positions instead of incorrectly increasing the subsequence length.

A final subtle edge case occurs when arr contains target values but in reverse order. For example:

target = [1,2,3]
arr = [3,2,1]

The transformed sequence becomes:

[2,1,0]

The LIS length is only 1, meaning only one target element is already correctly ordered. The algorithm therefore returns 2, which is correct.