Minimum Operations to Make a Subsequence LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> ans;
4

5
  void bin(int lo, int hi, int num) {
6
    if (lo == hi) {
7
      ans[lo] = num;
8
      return;
9
    }
10
    int mid = (lo + hi) / 2;
11
    if (ans[mid] < num)
12
      bin(mid + 1, hi, num);
13
    else
14
      bin(lo, mid, num);
15
  }
16

17
  int minOperations(vector<int> &target, vector<int> &arr) {
18
    unordered_map<int, int> idx;
19
    for (int i = 0; i < target.size(); i++) {
20
      idx[target[i]] = i;
21
    }
22

23
    for (int i = 0; i < arr.size(); i++) {
24
      if (idx.find(arr[i]) == idx.end()) continue;
25
      int num = idx[arr[i]];
26
      if (ans.size() == 0 || num > ans.back()) {
27
        ans.push_back(num);
28
      } else {
29
        bin(0, ans.size() - 1, num);
30
      }
31
    }
32

33
    return (target.size() - ans.size());
34
  }
35
};