Count Good Triplets in an Array LeetCode solution in Java

1
class Solution {
2
  public long goodTriplets(int[] nums1, int[] nums2) {
3
    int n = nums1.length;
4
    int indices[] = new int[n];
5
    for (int i = 0; i < n; i++) {
6
      indices[nums2[i]] = i;
7
    }
8
    int B[] = new int[n];
9
    for (int i = 0; i < n; i++) {
10
      B[i] = indices[nums1[i]];
11
      B[i]++;
12
    }
13
    Fenw L = new Fenw(n + 1);
14
    long[] left = new long[n + 1];
15
    long[] right = new long[n + 1];
16
    for (int i = 1; i <= n; i++) {
17
      left[i] = L.sum(B[i - 1] - 1);
18
      L.update(B[i - 1], 1);
19
    }
20
    Fenw R = new Fenw(n + 1);
21
    for (int i = n; i > 0; i--) {
22
      right[i] = R.sum(n) - R.sum(B[i - 1]);
23
      R.update(B[i - 1], 1);
24
    }
25
    long ans = 0l;
26
    for (int i = 0; i <= n; i++) {
27
      ans += left[i] * right[i];
28
    }
29
    return ans;
30
  }
31
}
32

33
class Fenw {
34
  long[] farr;
35
  int n;
36

37
  Fenw(int n) {
38
    this.n = n;
39
    farr = new long[n + 1];
40
  }
41

42
  void update(int index, int val) {
43
    int c = 0;
44
    for (int i = index; i <= n; i += (i & -i)) {
45
      c++;
46
      farr[i] += val;
47
    }
48
  }
49

50
  long sum(int index) {
51
    long ans = 0l;
52
    for (int i = index; i > 0; i -= (i & -i)) {
53
      ans += farr[i];
54
    }
55
    return ans;
56
  }
57
}