diff options
Diffstat (limited to 'count_good_triplet_arr.py')
-rw-r--r-- | count_good_triplet_arr.py | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/count_good_triplet_arr.py b/count_good_triplet_arr.py new file mode 100644 index 0000000..ec42ec0 --- /dev/null +++ b/count_good_triplet_arr.py @@ -0,0 +1,38 @@ +# 2179. Count Good Triplets in an Array +import bisect + +""" +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 +three distinct values which are present in increasing order by position in +both '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)'. return the total +number of good triplets. +""" + + +class Solution(object): + def goodTriplets(self, nums1, nums2): + """ + :type nums1: List[int] + :type nums2: List[int] + :rtype: int + """ + arr, n = {}, len(nums1) + for i, j in enumerate(nums1): + arr[j] = i + ans, stk = 0, [] + for i in nums2: + idx = arr[i] + left = bisect.bisect_left(stk, idx) + right = (n - 1 - idx) - (len(stk) - left) + ans += left * right + bisect.insort(stk, idx) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.goodTriplets(nums1=[2, 0, 1, 3], nums2=[0, 1, 2, 3])) + print(obj.goodTriplets(nums1=[4, 0, 1, 3, 2], nums2=[4, 1, 0, 2, 3])) |