Minimum Operations to Make a Subsequence LeetCode solution in Java

1
class Solution {
2
  public int minOperations(int[] target, int[] arr) {
3
    int n = target.length;
4
    Map<Integer, Integer> map = new HashMap<>();
5

6
    for (int i = 0; i < n; i++) {
7
      map.put(target[i], i);
8
    }
9

10
    List<Integer> array = new ArrayList<>();
11

12
    for (int i = 0; i < arr.length; i++) {
13
      if (!map.containsKey(arr[i])) {
14
        continue;
15
      }
16

17
      array.add(map.get(arr[i]));
18
    }
19

20
    int maxLen = 0;
21
    int[] tails = new int[n + 1];
22

23
    for (int i = 0; i < n; i++) {
24
      tails[i] = -1;
25
    }
26

27
    for (int num : array) {
28
      int index = findMinIndex(tails, maxLen, num);
29

30
      if (tails[index] == -1) {
31
        maxLen++;
32
      }
33
      tails[index] = num;
34
    }
35

36
    return n - maxLen;
37
  }
38

39
  public int findMinIndex(int[] tails, int n, int val) {
40
    int low = 0;
41
    int ans = n;
42
    int high = n - 1;
43

44
    while (low <= high) {
45
      int mid = (high + low) / 2;
46

47
      if (tails[mid] >= val) {
48
        ans = mid;
49
        high = mid - 1;
50
      } else {
51
        low = mid + 1;
52
      }
53
    }
54
    return ans;
55
  }
56
}