Minimum Operations to Make a Subsequence — Solution
Minimum Operations to Make a Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Operations to Make a Subsequence is a hard coding problem on arrays, hash table and greedy, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Greedy, Binary Search
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
target holds distinct integers; arr is any integer array (it may repeat values).
In one operation you insert a single integer anywhere in arr (at the front, at the end, or between two elements).
Return the minimum number of operations needed so that target becomes a subsequence of arr — its elements appear in arr in the same order, not necessarily contiguously.
Example 1
Input: target = [5,1,3], arr = [9,4,2,3,4]
Output: 2
Explanation: Insert 5 and 1 before the 3: `[5,9,4,1,2,3,4]`.
Example 2
Input: target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
Output: 3
Example 3
Input: target = [2,7], arr = [2,7,2]
Output: 0
Constraints
1 <= target.length, arr.length <= 10^51 <= target[i], arr[i] <= 10^9target contains no duplicates
Hints for Minimum Operations to Make a Subsequence
Hint 1
Whatever part of
targetalready appears in order insidearrcan stay; everything else must be inserted. So the answer istarget.lengthminus the longest common subsequence.Hint 2
Because
targetis distinct, replace each element ofarrby its position intarget(dropping values not intarget).Hint 3
A common subsequence is now a strictly increasing subsequence of those positions — find the longest one in
O(n log n)with patience sorting and binary search.
How to solve Minimum Operations to Make a Subsequence
The answer is |target| - LCS(target, arr). With distinct target values, the LCS equals the longest strictly increasing subsequence of the target-positions of arr's elements, which the binary-search LIS computes in O(m log m).
Approach
- Map every value of
targetto its index. - Walk
arr; skip values not intarget, and turn the rest into their target indices. - Maintain
tails, wheretails[len - 1]is the smallest possible last index of an increasing run of lengthlen; for each indexp, binary-search the first tail>= pand replace it (or appendp). - Return
target.length - tails.length.
Why it works
Elements of target that are matched in order to elements of arr need no insertion, and the rest need exactly one each, so maximising the matched part is the whole problem. Matching in order means the chosen arr elements have strictly increasing target positions — the LIS. The tails array is sorted, and replacing the first tail >= p keeps each length's best ending, so its final length is the LIS length.
Complexity
- Time —
O(n + m log m) - Space —
O(n + m)
Pitfalls
- The quadratic LCS table is far too big for 10^5 × 10^5 — the distinctness of
targetis what makes the LIS reduction possible. - Use strict increase (lower bound): a repeated value in
arrmaps to the same position and cannot be matched twice. - Values of
arrthat are absent fromtargetare simply ignored.
Reference solution
Python
from typing import List
import bisect
def minOperations(target: List[int], arr: List[int]) -> int:
pos = {v: i for i, v in enumerate(target)}
tails = []
for v in arr:
p = pos.get(v)
if p is None:
continue
k = bisect.bisect_left(tails, p)
if k == len(tails):
tails.append(p)
else:
tails[k] = p
return len(target) - len(tails)Java
public static 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);
int[] tails = new int[arr.length];
int len = 0;
for (int v : arr) {
Integer p = pos.get(v);
if (p == null) continue;
int lo = 0, hi = len;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (tails[mid] < p) lo = mid + 1; else hi = mid;
}
tails[lo] = p;
if (lo == len) len++;
}
return target.length - len;
}C++
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 v : arr) {
auto f = pos.find(v);
if (f == pos.end()) continue;
int p = f->second;
auto it = lower_bound(tails.begin(), tails.end(), p);
if (it == tails.end()) tails.push_back(p); else *it = p;
}
return (int)target.size() - (int)tails.size();
}JavaScript
var minOperations = function(target, arr) {
var pos = new Map();
for (var i = 0; i < target.length; i++) pos.set(target[i], i);
var tails = [];
for (var j = 0; j < arr.length; j++) {
var p = pos.get(arr[j]);
if (p === undefined) continue;
var lo = 0, hi = tails.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (tails[mid] < p) lo = mid + 1; else hi = mid;
}
if (lo === tails.length) tails.push(p); else tails[lo] = p;
}
return target.length - tails.length;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets