Minimum Operations to Make a Subsequence

• The core idea is that minimizing insertions is equivalent to maximizing the number of elements from target that are already present in arr in the correct relative order. This is the definition of the Longest Common Subsequence (LCS).
• However, a standard O(m*n) LCS algorithm is too slow. We can optimize by using the fact that target contains distinct elements.
• This allows us to reframe the problem as finding the Longest Increasing Subsequence (LIS).

1. Map target values to indices: Create a HashMap to store each number in target and its corresponding index. This lets us quickly check if a number from arr is in target and what its relative order should be.
2. Create an index sequence: Iterate through arr. For each number that also exists in target, find its index from the map and add it to a new list, let's call it indices.
3. Find LIS of indices: The problem is now reduced to finding the length of the LIS of this indices list. An increasing subsequence of these indices corresponds to elements from target appearing in the correct relative order within arr.
4. Calculate LIS with O(N^2) DP:
   • Create a dp array of the same size as indices, where dp[i] stores the length of the LIS ending at indices[i].
   • Initialize all dp values to 1.
   • Iterate through the indices list from the second element (i=1). For each element, iterate through all preceding elements (j < i).
   • If indices[i] > indices[j], it means we can extend the subsequence ending at j. Update dp[i] with max(dp[i], 1 + dp[j]).
   • The maximum value in the dp array is the length of the LIS.
5. Calculate result: The number of required insertions is target.length - length(LIS).

The minimum number of operations is target.length - length(LCS(target, arr)). Since target has distinct elements, we can simplify the LCS problem. We first create a map from each element in target to its index. Then, we iterate through arr and form a new list, indices, containing the indices of elements that are present in both arr and target. The length of the LCS is equal to the length of the Longest Increasing Subsequence (LIS) of this indices list. This approach calculates the LIS length using a straightforward but slow O(N^2) dynamic programming solution.

1import java.util.HashMap;2import java.util.ArrayList;3import java.util.List;4import java.util.Arrays;5 6class Solution {7    public int minOperations(int[] target, int[] arr) {8        HashMap<Integer, Integer> targetMap = new HashMap<>();9        for (int i = 0; i < target.length; i++) {10            targetMap.put(target[i], i);11        }12 13        List<Integer> indices = new ArrayList<>();14        for (int num : arr) {15            if (targetMap.containsKey(num)) {16                indices.add(targetMap.get(num));17            }18        }19 20        if (indices.isEmpty()) {21            return target.length;22        }23 24        int[] dp = new int[indices.size()];25        Arrays.fill(dp, 1);26        int maxLis = 1;27 28        for (int i = 1; i < indices.size(); i++) {29            for (int j = 0; j < i; j++) {30                if (indices.get(i) > indices.get(j)) {31                    dp[i] = Math.max(dp[i], 1 + dp[j]);32                }33            }34            maxLis = Math.max(maxLis, dp[i]);35        }36 37        return target.length - maxLis;38    }39}

1. Map target values to indices: Just like the previous approach, create a HashMap to store each number in target and its corresponding index. This takes O(m) time.
2. Process arr to find LIS directly: Instead of creating an intermediate indices list, we can compute the LIS on the fly. We use an efficient O(N log N) algorithm.
3. Find LIS with Binary Search (Patience Sorting):
   • Initialize an empty list, sub, which will store the smallest tail of all increasing subsequences of a certain length. The length of sub will be the length of the LIS.
   • Iterate through each number num in arr.
   • If num is not in the targetMap, ignore it.
   • Get the index idx = targetMap.get(num).
   • Perform a binary search on the sub list to find the first element that is greater than or equal to idx. This is the position where idx can replace an existing element to form an increasing subsequence of the same length but with a smaller tail, or where it can be inserted to extend the LIS.
   • If the binary search finds that idx is larger than all elements in sub, it means we can extend the longest subsequence found so far. Append idx to sub.
   • Otherwise, replace the element at the found position with idx.
4. Calculate result: After iterating through arr, the size of the sub list is the length of the LCS. The final answer is target.length - sub.size().

This solution refines the previous approach by using a much faster algorithm for finding the LIS length. The initial steps of mapping target elements to indices are the same. The core improvement is in the LIS calculation. We maintain a list, sub, that represents the tails of potential increasing subsequences. For each index from arr, we use binary search to find its place in sub. If the index is larger than any tail in sub, it extends the LIS. Otherwise, it replaces the smallest tail that is greater than or equal to it, creating a new potential LIS of the same length with a more favorable (smaller) tail.

1import java.util.HashMap;2import java.util.ArrayList;3import java.util.List;4 5class Solution {6    public int minOperations(int[] target, int[] arr) {7        HashMap<Integer, Integer> targetMap = new HashMap<>();8        for (int i = 0; i < target.length; i++) {9            targetMap.put(target[i], i);10        }11 12        List<Integer> sub = new ArrayList<>();13        for (int num : arr) {14            if (!targetMap.containsKey(num)) {15                continue;16            }17            int index = targetMap.get(num);18            19            // Binary search to find the insertion point for 'index' in 'sub'20            int left = 0, right = sub.size();21            while (left < right) {22                int mid = left + (right - left) / 2;23                if (sub.get(mid) < index) {24                    left = mid + 1;25                } else {26                    right = mid;27                }28            }29 30            if (left == sub.size()) {31                // If index is greater than all elements in sub, extend the subsequence32                sub.add(index);33            } else {34                // Replace the element at 'left' to potentially form a better subsequence35                sub.set(left, index);36            }37        }38 39        return target.length - sub.size();40    }41}