# 1713. Minimum Operations to Make a Subsequence

• Time: $O(n\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public: int minOperations(vector& target, vector& arr) { vector indices; unordered_map numToIndex; for (int i = 0; i < target.size(); ++i) numToIndex[target[i]] = i; for (const int a : arr) if (const auto it = numToIndex.find(a); it != numToIndex.end()) indices.push_back(it->second); return target.size() - lengthOfLIS(indices); } private: // Same as 300. Longest Increasing Subsequence int lengthOfLIS(vector& nums) { // tail[i] := the min tail of all increasing subseqs having length i + 1 // It's easy to see that tail must be an increasing array. vector tail; for (const int num : nums) if (tail.empty() || num > tail.back()) tail.push_back(num); else tail[firstGreaterEqual(tail, num)] = num; return tail.size(); } private: int firstGreaterEqual(const vector& A, int target) { return lower_bound(A.begin(), A.end(), target) - A.begin(); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution { public int minOperations(int[] target, int[] arr) { List indices = new ArrayList<>(); Map numToIndex = new HashMap<>(); for (int i = 0; i < target.length; ++i) numToIndex.put(target[i], i); for (final int a : arr) if (numToIndex.containsKey(a)) indices.add(numToIndex.get(a)); return target.length - lengthOfLIS(indices); } // Same as 300. Longest Increasing Subsequence private int lengthOfLIS(List nums) { // tail[i] := the min tail of all increasing subseqs with length i + 1 // It's easy to see that tail must be an increasing array. List tail = new ArrayList<>(); for (final int num : nums) if (tail.isEmpty() || num > tail.get(tail.size() - 1)) tail.add(num); else tail.set(firstGreaterEqual(tail, num), num); return tail.size(); } private int firstGreaterEqual(List A, int target) { int l = 0; int r = A.size(); while (l < r) { final int m = (l + r) / 2; if (A.get(m) >= target) r = m; else l = m + 1; } return l; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def minOperations(self, target: List[int], arr: List[int]) -> int: indices = [] numToIndex = {num: i for i, num in enumerate(target)} for a in arr: if a in numToIndex: indices.append(numToIndex[a]) return len(target) - self._lengthOfLIS(indices) # Same as 300. Longest Increasing Subsequence def _lengthOfLIS(self, nums: List[int]) -> int: # tail[i] := the min tail of all increasing subseqs having length i + 1 # It's easy to see that tail must be an increasing array. tail = [] for num in nums: if not tail or num > tail[-1]: tail.append(num) else: tail[bisect.bisect_left(tail, num)] = num return len(tail)