Minimum Operations to Make a Subsequence: LIS Reduction

You are given an array target of distinct integers and another array arr. In one operation, you can insert any integer at any position in arr. Return the minimum number of operations needed to make target a subsequence of arr.

This is LeetCode 1713: Minimum Operations to Make a Subsequence, and it is one of those hard problems that looks intimidating at first glance but becomes elegant once you see the reduction. The trick is recognizing that this is really a Longest Increasing Subsequence problem in disguise.

Why this problem matters

This problem tests whether you can reduce an unfamiliar problem to a well-known one. The naive approach (trying all possible insertions) is far too slow. Even a direct subsequence-matching DP would be O(n * m), which is too expensive given the constraints (both arrays can have up to 10^5 elements).

The real skill here is recognizing the connection to LIS. Once you see that connection, the solution writes itself using the O(n log n) binary search LIS algorithm. This kind of problem reduction is a pattern that shows up across many hard LeetCode problems.

The key insight

Think about what it means to make target a subsequence of arr. You need every element of target to appear in arr in order. Some elements of target might already appear in arr in the right relative order. Those elements do not need to be inserted. You only need to insert the ones that are missing or out of order.

So the question becomes: what is the longest subsequence of target that already appears as a subsequence of arr? The elements you do not need to insert are exactly those that already match in order. The rest need to be inserted.

Here is the trick: since target has all distinct values, you can assign each value an index based on its position in target. Then you filter arr to only include elements that exist in target, and replace each with its target index. Now you have a sequence of numbers, and you want the longest increasing subsequence of that sequence. Why? Because an increasing sequence of target indices means those elements appear in the correct relative order with respect to target.

The answer is len(target) - LIS_length.

The solution

from bisect import bisect_left

def min_operations(target: list[int], arr: list[int]) -> int:
    index_map = {val: i for i, val in enumerate(target)}
    mapped = [index_map[x] for x in arr if x in index_map]

    tails = []
    for num in mapped:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num

    return len(target) - len(tails)

Let's break down each part.

Building the index map. You create a dictionary that maps each value in target to its index. For target = [6, 4, 8, 1, 3, 2], this gives you {6: 0, 4: 1, 8: 2, 1: 3, 3: 4, 2: 5}. This runs in O(n) time where n is the length of target.

Mapping arr. You walk through arr and, for each element that appears in target, replace it with its target index. Elements not in target are skipped entirely because they can never contribute to making target a subsequence. For arr = [4, 7, 6, 2, 3, 8, 6, 1], the element 7 is not in target, so you skip it. The mapped result is [1, 0, 5, 4, 2, 0, 3].

Finding the LIS. You run the standard O(n log n) patience sorting algorithm on the mapped array. You maintain a tails array where tails[i] is the smallest possible last element of an increasing subsequence of length i + 1. For each number, you binary search for its position and either extend tails or replace an existing entry.

Computing the answer. The LIS length tells you how many elements of target are already present in arr in the correct relative order. The remaining elements need to be inserted.

Visual walkthrough

Let's trace through the full example step by step.

The patience sorting trace shows how tails evolves as you process each mapped value. After processing all seven values, tails = [0, 2, 3] with length 3. That means 3 elements of target are already in the right relative order within arr. You need to insert the remaining 6 - 3 = 3 elements.

Complexity analysis

Time: O(n log n + m). Building the index map takes O(n) where n is len(target). Mapping arr takes O(m) where m is len(arr). The LIS computation processes at most m elements, each requiring a binary search over tails which has at most n elements, giving O(m log n). The total is O(n + m log n), which simplifies to O((n + m) log n). For the typical case where n and m are similar in size, this is O(n log n).

Space: O(n). The index map stores n entries. The mapped array has at most m entries (but only elements present in target). The tails array has at most n entries. Overall O(n + m), which simplifies to O(n) when considering that mapped is bounded by n distinct target values.

Building blocks

This problem combines two reusable patterns that you will see in many other problems.

1. Value-to-index mapping. When a problem involves matching elements between two arrays based on relative order, mapping values to indices is a powerful technique. It converts a "does this value appear in the right order?" question into a simple numeric comparison. You will see this same trick in problems like Russian Doll Envelopes where you sort by one dimension and find LIS in the other.

2. Patience sorting (binary search LIS). The O(n log n) LIS algorithm using bisect_left and a tails array is one of the most versatile building blocks in competitive programming. It shows up whenever you need the length of the longest increasing subsequence and the array is too large for the O(n^2) DP approach. The key idea is that by always keeping the smallest possible tail for each subsequence length, you maximize your chances of extending the subsequence later.

Once you internalize these two building blocks, you can snap them together whenever you see a problem that asks about preserving relative order between sequences.

Edge cases

• Target is already a subsequence of arr. The LIS of the mapped array equals len(target), so the answer is 0. No insertions needed.
• No common elements. If arr shares no values with target, the mapped array is empty, the LIS length is 0, and you need to insert all of target. The answer is len(target).
• Single element target. If target = [x], you need 0 insertions if x appears in arr, and 1 insertion otherwise.
• arr is a permutation of target. The mapped array contains all indices 0 through n-1 in some order. The LIS of this permutation determines how many are already in order.
• arr has many elements not in target. These are simply filtered out during the mapping step. They do not affect the LIS computation at all.

From understanding to recall

You have just walked through a hard LeetCode problem that reduces to a well-known algorithm. The reduction step (value-to-index mapping) is the creative part. The LIS computation is mechanical once you know the patience sorting technique.

But understanding this reduction right now does not mean you will spot it in an interview next month. The skill you need is pattern recognition: seeing "make X a subsequence of Y with minimum insertions" and immediately thinking "LIS reduction." That kind of recognition comes from repeated practice, not just reading through the solution once.

Spaced repetition is the most efficient way to build that muscle. You revisit this problem at increasing intervals, and each time you practice the full chain: recognize the reduction, build the index map, run patience sorting, compute the answer. After a few reps, the entire approach becomes automatic.

Related posts

• Longest Increasing Subsequence - The core algorithm used in this problem, explained with both O(n^2) DP and O(n log n) binary search
• Russian Doll Envelopes - Another hard problem that reduces to LIS after a sorting step
• Is Subsequence - A simpler subsequence problem that builds intuition for what "subsequence" means