Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 15

Description

Count Good Triplets in an Array

You are given two 0-indexed arrays nums1 and nums2 of length n, both of which are permutations of [0, 1, ..., n - 1].

A good triplet is a set of 3 distinct values which are present in increasing order by position both in nums1 and nums2. In other words, if we consider pos1v as the index of the value v in nums1 and pos2v as the index of the value v in nums2, then a good triplet will be a set (x, y, z) where 0 <= x, y, z <= n - 1, such that pos1x < pos1y < pos1z and pos2x < pos2y < pos2z.

Return the total number of good triplets.

Example 1:

Input: nums1 = [2,0,1,3], nums2 = [0,1,2,3]
Output: 1
Explanation: 
There are 4 triplets (x,y,z) such that pos1x < pos1y < pos1z. They are (2,0,1), (2,0,3), (2,1,3), and (0,1,3). 
Out of those triplets, only the triplet (0,1,3) satisfies pos2x < pos2y < pos2z. Hence, there is only 1 good triplet.

Example 2:

Input: nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
Output: 4
Explanation: The 4 good triplets are (4,0,3), (4,0,2), (4,1,3), and (4,1,2).

Constraints:

• n == nums1.length == nums2.length
• 3 <= n <= 105
• 0 <= nums1[i], nums2[i] <= n - 1
• nums1 and nums2 are permutations of [0, 1, ..., n - 1].

Solution

inline constexpr int lowbit(int x) {
  return x & -x;
}
class BITS {
  int size = 0;
  vector<int> container;
public:
  BITS(int n): container(n), size(n) {}
  void add(int x, int val) {
    while(x < size) {
      container[x] += val;
      x += lowbit(x);
    }
  }

  int sum(int x) {
    int result = 0;
    while(x) {
      result += container[x];
      x -= lowbit(x);
    }
    return result;
  }
};
class Solution {
public:
  long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
    int len = nums1.size();

    vector<int> pos2(len);
    for(int i = 0; i < len; ++i) {
      pos2[nums2[i]] = i;
    }
    vector<int> indexMapping(len);
    for(int i = 0; i < len; ++i) {
      indexMapping[pos2[nums1[i]]] = i;
    }

    BITS bit(len + 1);
    long long answer = 0;
    for(int val = 0; val < len; ++val) {
      int pos = indexMapping[val];
      int left = bit.sum(pos + 1);
      bit.add(pos + 1, 1);
      int right = (len - 1 - pos) - (val - left);
      answer += 1LL * left * right;
    }
    return answer;
  }
};

// Accepted
// 148/148 cases passed (17 ms)
// Your runtime beats 88.78 % of cpp submissions
// Your memory usage beats 84.62 % of cpp submissions (87.9 MB)