Problem Description

Given two integer arrays, target and arr, your goal is to make target a subsequence of arr using the minimum number of insert operations. In each operation, you can insert any integer at any position in arr. You are not allowed to delete or modify elements in arr.

A subsequence means you can remove some (or no) elements from arr so that the remaining elements, in order, are exactly equal to target.

• Both target and arr contain unique integers.
• Each element in target must appear in the same order in arr for it to be a subsequence.
• You must not reuse elements in arr; each element can be used at most once in forming the subsequence.
• Return the minimum number of insert operations needed.

Thought Process

The first idea that comes to mind is to check, for each element in target, whether it exists in arr in the required order. If not, we need to insert it. However, scanning through arr many times is inefficient.

A brute-force approach would be to try all possible insertions, but that quickly becomes infeasible for large arrays. Instead, we realize that the problem is similar to finding the Longest Common Subsequence (LCS) between the two arrays, since the more elements of target that already appear in order in arr, the fewer insertions we need.

However, since both arrays contain unique elements, we can optimize LCS using a mapping and a Longest Increasing Subsequence (LIS) approach.

Solution Approach

• Step 1: Map elements in target to their indices
  Since all elements are unique, we can create a hash map from each value in target to its position. This allows us to quickly look up the intended order of elements.
• Step 2: Transform arr into a sequence of indices
  Iterate through arr. For each element that is also in target, replace it with its index from the mapping. This gives us a new array representing the order in which target’s elements appear in arr.
• Step 3: Find the Longest Increasing Subsequence (LIS)
  The LIS of this index array tells us the largest subset of target that appears in arr in order. The elements not in this LIS are the ones we need to insert.
• Step 4: Calculate the answer
  The minimum number of insertions required is len(target) - len(LIS).

We use a hash map for fast lookups (O(1)), and a binary search-based LIS algorithm for efficiency (O(n log n)), making the solution scalable.

Example Walkthrough

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

1. Map target values to indices: {5:0, 1:1, 3:2}
2. Replace each element in arr with its index in target (if it exists):
   arr becomes [ ] (since only 3 is in target at index 2), so index array is [2]
3. LIS of [2] is of length 1 (just [2])
4. So, minimum insertions = 3 (length of target) - 1 = 2
5. Explanation: We need to insert 5 and 1 at appropriate positions to make target a subsequence.

Time and Space Complexity

• Brute-force approach: Checking all subsequences or all insertion possibilities is exponential, O(2^n), and not feasible.
• Optimized approach:
  • Mapping target values: O(n)
  • Transforming arr: O(m), where m is length of arr
  • Finding LIS: O(m log m) using patience sorting/binary search
  • Total time: O(n + m log m)
  • Space: O(n + m) for the map and index array

This is efficient even for large inputs.

Code Implementation

from bisect import bisect_left

class Solution:
    def minOperations(self, target, arr):
        pos = {num: i for i, num in enumerate(target)}
        idx = [pos[num] for num in arr if num in pos]
        # Find LIS on idx
        lis = []
        for x in idx:
            i = bisect_left(lis, x)
            if i == len(lis):
                lis.append(x)
            else:
                lis[i] = x
        return len(target) - len(lis)
      

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        unordered_map<int, int> pos;
        for (int i = 0; i < target.size(); ++i)
            pos[target[i]] = i;
        vector<int> idx;
        for (int num : arr)
            if (pos.count(num))
                idx.push_back(pos[num]);
        vector<int> lis;
        for (int x : idx) {
            auto it = lower_bound(lis.begin(), lis.end(), x);
            if (it == lis.end())
                lis.push_back(x);
            else
                *it = x;
        }
        return target.size() - lis.size();
    }
};
      

import java.util.*;

class Solution {
    public int minOperations(int[] target, int[] arr) {
        Map<Integer, Integer> pos = new HashMap<>();
        for (int i = 0; i < target.length; ++i)
            pos.put(target[i], i);
        List<Integer> idx = new ArrayList<>();
        for (int num : arr)
            if (pos.containsKey(num))
                idx.add(pos.get(num));
        List<Integer> lis = new ArrayList<>();
        for (int x : idx) {
            int i = Collections.binarySearch(lis, x);
            if (i < 0) i = -(i + 1);
            if (i == lis.size())
                lis.add(x);
            else
                lis.set(i, x);
        }
        return target.length - lis.size();
    }
}
      

var minOperations = function(target, arr) {
    const pos = new Map();
    for (let i = 0; i < target.length; ++i) pos.set(target[i], i);
    const idx = [];
    for (const num of arr) {
        if (pos.has(num)) idx.push(pos.get(num));
    }
    const lis = [];
    for (const x of idx) {
        let l = 0, r = lis.length;
        while (l < r) {
            let m = (l + r) >> 1;
            if (lis[m] < x) l = m + 1;
            else r = m;
        }
        if (l === lis.length) lis.push(x);
        else lis[l] = x;
    }
    return target.length - lis.length;
};
      

Summary

By recognizing that this problem is about minimizing insertions to form a subsequence, we efficiently reduce it to finding the Longest Common Subsequence (LCS). Because the arrays have unique elements, we can map arr to target indices and use a Longest Increasing Subsequence (LIS) algorithm for speed. This approach is both elegant and efficient, leveraging hash maps and binary search to achieve optimal performance.