classSolution{public:intminOperations(vector<int>&target,vector<int>&arr){vector<int>indices;unordered_map<int,int>numToIndex;for(inti=0;i<target.size();++i)numToIndex[target[i]]=i;for(constinta:arr)if(constautoit=numToIndex.find(a);it!=numToIndex.end())indices.push_back(it->second);returntarget.size()-lengthOfLIS(indices);}private:// Same as 300. Longest Increasing SubsequenceintlengthOfLIS(vector<int>&nums){// tails[i] := the minimum tail of all the increasing subsequences having// length i + 1vector<int>tails;for(constintnum:nums)if(tails.empty()||num>tails.back())tails.push_back(num);elsetails[firstGreaterEqual(tails,num)]=num;returntails.size();}private:intfirstGreaterEqual(constvector<int>&arr,inttarget){returnranges::lower_bound(arr,target)-arr.begin();}};
classSolution{publicintminOperations(int[]target,int[]arr){List<Integer>indices=newArrayList<>();Map<Integer,Integer>numToIndex=newHashMap<>();for(inti=0;i<target.length;++i)numToIndex.put(target[i],i);for(finalinta:arr)if(numToIndex.containsKey(a))indices.add(numToIndex.get(a));returntarget.length-lengthOfLIS(indices);}// Same as 300. Longest Increasing SubsequenceprivateintlengthOfLIS(List<Integer>nums){// tails[i] := the minimum tail of all the increasing subsequences with// length i + 1List<Integer>tails=newArrayList<>();for(finalintnum:nums)if(tails.isEmpty()||num>tails.get(tails.size()-1))tails.add(num);elsetails.set(firstGreaterEqual(tails,num),num);returntails.size();}privateintfirstGreaterEqual(List<Integer>arr,inttarget){finalinti=Collections.binarySearch(arr,target);returni<0?-i-1:i;}}
1 2 3 4 5 6 7 8 910111213141516171819202122
classSolution:defminOperations(self,target:list[int],arr:list[int])->int:indices=[]numToIndex={num:ifori,numinenumerate(target)}forainarr:ifainnumToIndex:indices.append(numToIndex[a])returnlen(target)-self._lengthOfLIS(indices)# Same as 300. Longest Increasing Subsequencedef_lengthOfLIS(self,nums:list[int])->int:# tails[i] := the minimum tail of all the increasing subsequences having# length i + 1tails=[]fornuminnums:ifnottailsornum>tails[-1]:tails.append(num)else:tails[bisect.bisect_left(tails,num)]=numreturnlen(tails)
Thanks for stopping by! If you find this site helpful, consider buying me some protein powder to keep me fueled! π