Minimum Operations to Make a Subsequence

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. For example, if arr = [1,4,1,2], you can add 3 in the middle and make it [1,4,3,1,2]. Note that you can insert 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 an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

Example 1:

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.

Example 2:

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

1. Understanding the Problem

We are given two arrays:

• target: A distinct integer array.

• arr: An integer array that may contain duplicates.

We need to make target a subsequence of arr using the minimum number of insert operations.
An element in a subsequence maintains its relative order in arr but does not need to be contiguous.

Operations allowed:
We can insert any integer at any position in arr.
The goal is to find the minimum number of insertions required.

---

2. Key Insights

1. Finding the Longest Common Subsequence (LCS)

   • Instead of inserting elements, we can think of this as maximizing how much of target is already in arr in order.

   • The fewer elements from target found in arr, the more insertions we need.

2. Optimizing with Longest Increasing Subsequence (LIS)

   • If we map target[i] to its index in target, the problem reduces to finding the Longest Increasing Subsequence (LIS) in arr when mapped to target indices.

   • The number of elements not in this LIS needs to be inserted.

3. Efficient Approach using Hash Map + Binary Search

   • First, map each element in target to its index.

   • Convert arr into an index sequence (ignoring elements not in target).

   • Find the LIS of this index sequence using binary search + patience sorting (O(n log n)).

---

3. Steps to Solve the Problem

1. Create a map (indexMap) from target[i] → i (to track positions of elements in target).

2. Convert arr into an index sequence based on target (ignore numbers not in target).

3. Find the Longest Increasing Subsequence (LIS) in this sequence using binary search (O(n log n)).

4. Calculate insertions needed:

   • If LIS_length = k, then we need to insert target.length - k elements.

---

4. JavaScript Solution

function minOperations(target, arr) {
    // Step 1: Create a mapping of target values to their indices
    const indexMap = new Map();
    for (let i = 0; i < target.length; i++) {
        indexMap.set(target[i], i);
    }

    // Step 2: Convert arr into an index sequence based on target
    let indexSequence = [];
    for (let num of arr) {
        if (indexMap.has(num)) {
            indexSequence.push(indexMap.get(num));
        }
    }

    // Step 3: Find the Longest Increasing Subsequence (LIS) in indexSequence
    function lengthOfLIS(nums) {
        let lis = [];
        for (let num of nums) {
            let pos = binarySearch(lis, num);
            if (pos < lis.length) {
                lis[pos] = num; // Replace element to maintain increasing order
            } else {
                lis.push(num); // Append if larger
            }
        }
        return lis.length;
    }

    function binarySearch(lis, target) {
        let left = 0, right = lis.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (lis[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // Step 4: Compute result
    let lisLength = lengthOfLIS(indexSequence);
    return target.length - lisLength;
}

---

5. Dry Run with Example

Input:

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

Step 1: Mapping target indices

indexMap = { 5: 0, 1: 1, 3: 2 }

Step 2: Convert arr to index sequence

arr = [9,4,2,3,4,1,5,3]  
indexSequence = [2, 1, 0, 2] // (only numbers in target)

Step 3: Compute LIS of indexSequence

LIS = [0, 2] (length = 2)

Step 4: Compute result

target.length - lisLength = 3 - 2 = 1

So, minimum insertions required = 1.

---

6. Time Complexity Analysis

1. Building the indexMap → O(n)

2. Converting arr into an index sequence → O(m)

3. Finding LIS using binary search (Patience Sorting) → O(m log m)

Thus, the overall time complexity is O(m log m) + O(n), which is O(m log m) in the worst case.

---

7. Summary

✅ Mapped target indices for faster lookup
✅ Transformed arr into a sequence of target indices
✅ Used LIS with binary search for optimal solution
✅ Achieved efficient O(m log m) solution

🚀 Final Answer: target.length - LIS_length