Minimum Operations to Make a Subsequence
Problem
You are given target, an array of distinct integers, and another array arr (which may repeat values). In one operation you may insert any integer at any position of arr. Return the minimum number of such insertions needed so that target becomes a subsequence of arr. A subsequence keeps the original relative order but may skip elements. The answer always exists because you can always insert all of target.
target = [1, 3, 5, 2], arr = [3, 1, 5, 2, 3]1arr the values 1, 5, 2 already appear in target order, so they need no work. Only 3 must be inserted, giving 4 − 3 = 1 operation.import bisect
def min_operations(target, arr):
pos = {v: i for i, v in enumerate(target)}
tails = []
for x in arr:
if x not in pos:
continue
idx = pos[x]
j = bisect.bisect_left(tails, idx)
if j == len(tails):
tails.append(idx)
else:
tails[j] = idx
return len(target) - len(tails)function minOperations(target, arr) {
const pos = new Map();
target.forEach((v, i) => pos.set(v, i));
const tails = [];
for (const x of arr) {
if (!pos.has(x)) continue;
const idx = pos.get(x);
let lo = 0, hi = tails.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < idx) lo = mid + 1;
else hi = mid;
}
if (lo === tails.length) tails.push(idx);
else tails[lo] = idx;
}
return target.length - tails.length;
}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> tails = new ArrayList<>();
for (int x : arr) {
if (!pos.containsKey(x)) continue;
int idx = pos.get(x);
int lo = 0, hi = tails.size();
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (tails.get(mid) < idx) lo = mid + 1;
else hi = mid;
}
if (lo == tails.size()) tails.add(idx);
else tails.set(lo, idx);
}
return target.length - tails.size();
}
}int minOperations(vector<int>& target, vector<int>& arr) {
unordered_map<int, int> pos;
for (int i = 0; i < (int)target.size(); i++) pos[target[i]] = i;
vector<int> tails;
for (int x : arr) {
auto it = pos.find(x);
if (it == pos.end()) continue;
int idx = it->second;
auto lb = lower_bound(tails.begin(), tails.end(), idx);
if (lb == tails.end()) tails.push_back(idx);
else *lb = idx;
}
return (int)target.size() - (int)tails.size();
}Explanation
We can only insert into arr — we never delete. So whatever part of target already lines up inside arr (in the right order) is free, and everything else must be inserted. To spend the fewest operations, we want to keep the largest chunk of target that already appears as a subsequence of arr. The answer is then len(target) − (that largest chunk).
The clever step is a relabeling. Because target has distinct values, give each value its index in target: in the example 1→0, 3→1, 5→2, 2→3. Now scan arr, throw away any value not in target, and replace the rest by their target index. arr = [3, 1, 5, 2, 3] becomes the index sequence [1, 0, 2, 3, 1].
A subset of target is in correct target order exactly when its indices are increasing. So "largest chunk of target that is a subsequence of arr" turns into "longest strictly increasing subsequence (LIS) of that index list". In [1, 0, 2, 3, 1] the LIS is [0, 2, 3] with length 3 — those are the values 1, 5, 2 in target order.
Computing the LIS with patience sorting keeps it fast: maintain a tails array where tails[k] is the smallest possible tail of an increasing run of length k+1. For each index, binary-search for the first tail that is not smaller and overwrite it (or append if it extends every run). The final length of tails is the LIS length.
Here len(target) = 4 and the LIS length is 3, so the answer is 4 − 3 = 1: we only need to insert the single missing value 3.